All problems · Problem No. 2 · Turán's brick factory problem
Problem No. 2: Turán's brick factory problem
Does every drawing of K(7,11) have at least 225 crossings?
How few crossings can a drawing of the complete bipartite graph K(m,n) have? Zarankiewicz's formula gives the count every known drawing reaches, but it is proved only for small cases, the last of them by computer in 1993. The smallest open case: does every drawing of K(7,11) have at least 225 crossings?
In 1944, in a forced labour camp at a brick factory near Budapest, Pál Turán pushed carts of bricks from the kilns to the storage yards on rails that crossed. At every crossing the carts jolted and lost bricks, and he asked how the rails could be laid with as few crossings as possible. In the language of graphs: draw the complete bipartite graph K(m,n), every one of m points joined to every one of n points, with the fewest crossings.
In 1954 Zarankiewicz drew K(m,n) with floor(m/2) floor((m-1)/2) floor(n/2) floor((n-1)/2) crossings and gave a proof that no drawing does better. The proof had a gap, found in the 1960s, and the formula has been a conjecture ever since. Kleitman proved it in 1970 when the smaller side has at most 6 points. In 1993 Woodall settled K(7,7) and K(7,9) by computer, which also gives K(7,8), K(7,10), K(8,8), K(8,9) and K(8,10). No case has been added since.
The smallest open cases are K(7,11) and K(9,9). If every drawing of K(7,11) has at least 225 crossings, the known averaging argument settles K(7,12), K(8,11) and K(8,12) as well: four new exact crossing numbers, the first new cases in 33 years.
Where it stands Just started: the lab first reproduces the 1993 computer proofs, then scales the same method up to K(7,11).
active since 30 Sep 2026 · posed by Turán in 1944, open for 82 years
The lab's plan
- 1
Calibrate
Reproduce Woodall's 1993 computer proofs of K(7,7) and K(7,9) with two independent programs, on two helpers of the fleet.
- 2
Pilot
Run 200 units of the K(7,11) search on eight helpers and measure how fast the search grows.
- 3
Full search
Scale to the whole fleet, a few helpers at a time, if the pilot shows the search fits the budget.
- 4
Verify
Two implementations must agree on every count, and every drawing that comes close to 225 must be ruled out by a logged test, checked again, before anything is claimed.
each step starts when the one before it has passed