Turán's brick factory problem

A man named Pál Turán worked in a brick factory. He had to push heavy wagons on tracks. Some tracks crossed each other. These crossings made the work hard. He wanted to find a better way. He wondered how to have the fewest crossings. This became a math problem. He thought about tracks from kilns to storage sites. He wanted to know the smallest number of crossings possible. People still study this math puzzle today. It is a very famous mystery.

Pál Turán was a mathematician. During World War II, he worked in a brick factory. His job was to push heavy wagons. The factory had tracks for these wagons. Each kiln had tracks to every storage site. Some tracks crossed each other. These crossings made the wagons hard to push. Turán wanted to find a way to fix this. He wanted the fewest crossings possible.

In math, this is a problem about graphs. A graph uses points and lines. In this problem, kilns and storage sites are points. The tracks are lines that connect them. This is called a complete bipartite graph. This means points are in two groups. Lines only connect a point from one group to the other.

Kazimierz Zarankiewicz found a way to draw these graphs. He used a specific formula to count crossings. Many people think his way is the best. This idea is called the Zarankiewicz crossing number conjecture. A conjecture is a math idea that might be true. It has not been proven yet. We know it works for some small groups of points. However, the big mystery remains open today.

Imagine you are pushing a heavy wagon through a factory. The wagon moves along metal tracks on the ground. In one factory, tracks go from every kiln to every storage site. Many tracks cross over each other at different points. These crossings make it very hard to push the heavy wagons. A mathematician named Pál Turán saw this problem during World War II. He wanted to find a way to redesign the factory. He looked for a way to have the fewest crossings possible.

In math, we can turn this factory into a drawing called a graph. A graph uses points and lines to show how things connect. The kilns and storage sites are the points. The tracks are the lines that connect the two groups. This specific type of graph is called a complete bipartite graph. This means we have two separate groups of points. Every point in the first group connects to every point in the second group.

In 1952, a man named Kazimierz Zarankiewicz shared a solution. He and another man named Kazimierz Urbanik both found a way to draw these graphs. They used a math formula to count the crossings. They showed you could place points on two different lines. One group of points goes on a horizontal line. The other group goes on a vertical line. Then, you connect every point on one line to every point on the other.

Even though they found a way to draw the graphs, there was a mistake. Their math proofs were not quite right. Other mathematicians named Gerhard Ringel and Paul Kainen found this error eleven years later. We still believe the formula from Zarankiewicz is the best way. This idea is called the Zarankiewicz crossing number conjecture. A conjecture is a math idea that people think is true but cannot prove yet.

This mystery is still an open problem in math today. We know the formula works for some small groups of points. For example, it is true for graphs with certain small numbers of points. We also know that any such graph must have at least 83% of the crossings from the formula. Scientists use these ideas in things like VLSI design. This helps them design the tiny paths inside computer chips.

Turán's brick factory problem is a famous puzzle in the field of graph drawing. It asks for the minimum number of crossings required to draw a complete bipartite graph on a flat surface. A crossing occurs when two edges intersect at a point that is not one of the vertices. This problem is important because it helps mathematicians understand how to organize connections efficiently. It is a central study in topological graph theory and discrete geometry. Solving such problems is vital for modern technology, such as VLSI design, which involves designing the tiny paths on computer chips.

To understand the mechanism, we must first define the components of the graph. The graph is called a complete bipartite graph. This means the vertices, or points, are divided into two distinct sets. Every single vertex in the first set must connect to every vertex in the second set. These connections are called edges, which can be drawn as curves or straight lines. In a drawing, a crossing is counted whenever two edges that do not share a vertex intersect each other. The goal is to arrange the vertices so that the total number of these intersections is as low as possible.

There are different ways to approach these drawings. One way is using arbitrary curves for the edges. Another way is using rectilinear drawings, where every edge must be a straight line segment. Interestingly, the upper bound discovered by Kazimierz Zarankiewicz can be achieved using only straight edges. This suggests that for these specific graphs, the rectilinear crossing number might be the same as the standard crossing number. If the Zarankiewicz conjecture is ever proven true, it would confirm that straight lines are just as efficient as curves for these graphs.

The problem has a unique history rooted in World War II. The Hungarian mathematician Pál Turán formulated the problem while working in a brick factory. He was tasked with pushing heavy wagons of bricks from kilns to storage sites along metal tracks. The factory had tracks running from every kiln to every storage site. Turán noticed that pushing wagons was much harder at the points where the tracks crossed. He wanted to find a factory design that would minimize these difficult crossings. This real-world struggle led to one of the first major studies of crossing numbers in mathematics.

In 1952, mathematicians Kazimierz Zarankiewicz and Kazimierz Urbanik independently published attempted solutions. They both presented formulas to calculate the number of crossings in these graphs. Their method involved placing vertices on the x-axis and the y-axis of a plane. They suggested placing an equal or nearly equal number of points on either side of the origin on each axis. By connecting every point on the x-axis to every point on the y-axis, they created a specific drawing. While their construction provided a way to reach a certain number of crossings, their mathematical proofs were actually erroneous. This mistake was not discovered until eleven years later by Gerhard Ringel and Paul Kainen.

Today, the formula provided by Zarankiewicz is known as the Zarankiewicz crossing number conjecture. A conjecture is a mathematical statement that is believed to be true but has not yet been proven. We know the conjecture is true for several specific cases. For example, it is proven for complete bipartite graphs where one set has two vertices, such as K_{2,n}. It is also known to be true for cases like K_{3,3}, K_{3,4}, K_{3,5}, and K_{4,5}. For the general case, however, the problem remains open and unsolved.

Mathematical research continues to narrow the gap between what we know and what we suspect. We know that for very large graphs, the number of crossings must be at least 83% of the number suggested by the Zarankiewicz bound. If a counterexample exists that proves the conjecture wrong, researchers believe it would involve a graph where both sets of vertices have an odd number of points. While we cannot yet prove the exact minimum for all graphs, the study of Turán's problem continues to drive progress in how we understand complex networks and connections.