Crossing Numbers Turn Useful (11w5144)

The Banff International Research Station will host the "Crossing Numbers Turn Useful" workshop from August 21st to August 26th, 2011.

In 1945, while in a forced labor camp, Paul Turan's work involved taking trainloads of bricks from kilns to shipping yards. The cars were pushed from the kilns to the yards along a set of tracks. Unfortunately, a car of bricks pushed along a track that crossed a second track was likely to derail, causing unneccessary delay in transferring the brick--and a lot of extra work for the labourers who had to restack them. Reflecting on his mathematical training, Turan wondered, "How can we connect every kiln to every shipping yard so that the total number of track-crossings is as small as possible?" "Turan's Brickyard Problem" sounds simple and, indeed, is easy if the number of kilns or shipping yards is small. But it is not so easy to answer if the number of kilns and shipping yards are large, in fact, the exact answer remains unknown. The informal nature of the problem led it to being dismissed by many mathematicians; however, as more people examined the problem it became connected with the geometry of numbers and with probabilistic questions about sets in a plane. In short, the answer became related to many more questions than the one initially asked.

The subsequent rapid growth in computers and their ubiquitous applications made the problem even more important. Instead of thinking
of kilns connected to shipping yards, we have processors connected by wires reflecting lines of communication. Wires in computers should not
cross unnecessarily; the consequences can be shocking. Computer designers refer to these kiln/shipping configurations as "hairballs,"
reflecting their unattractive tangled nature.
This workshop will bring together experts from around the world who study such lay-out problems from both their theoretical side and from
their practical applications. Issues important to each perspective should enhance those studied by the other.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).