Zarankiewicz's conjecture asserts that the graph crossing number 
of the complete
bipartite graph 
satisfies
 |
(1)
|
for all positive integers 
and 
, where 
is the floor function.
Zarankiewicz's (1954) proposed proof contained an error
(Guy 1969), although his construction establishes the upper
bound 
.
The problem addressed by the conjecture is sometimes known as the brick factory problem, since it was described by Turán (1977) as follows: "We worked near Budapest,
in a brick factory. There were some kilns where the bricks were made and some open
storage yards where the bricks were stored. All the kilns were connected to all the
storage yards. The bricks were carried on small wheeled trucks to the storage yards.
All we had to do was to put the bricks on the trucks at the kilns, push the trucks
to the storage yards, and unload them there. We had a reasonable piece rate for the
trucks, and the work itself was not difficult; the trouble was at the crossings.
The trucks generally jumped the rails there, and the bricks fell out from them, in
short this caused a lot of trouble and loss of time which was precious to all of
us. We were all sweating and cursing at such occasions, I too; but 'nolens volens'
the idea occurred to me that this loss of time could have been minimized if the number
of crossings of the rails had been minimized. But what is the minimum number of crossings?
I realized after several days that the actual situation could have been improved,
but the exact solution of the general problem with 
kilns and 
storage yards seemed to be very difficult. The problem occurred
to me again at my first visit to Poland where I met Zarankiewicz. I mentioned to
him my 'brick-factory' problem and Zarankiewicz thought he had solved it. But Gerhard
Ringel found a gap in his published proof, which nobody has been able to fill so
far--in spite of much effort. This problem has also become a notoriously difficult
unsolved problem."
The conjecture has been established for all 
. Woodall (1993) verified it for 
and 
, including 
. The smallest unsettled cases at that time were
and 
.
The table below gives established crossing numbers.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 3 | 1 | 2 | 4 | 6 | 9 | ||
| 4 | 4 | 8 | 12 | 18 | |||
| 5 | 16 | 24 | 36 | ||||
| 6 | 36 | 54 | |||||
| 7 | 81 |
Richter and Širáň (1996) computed the crossing number of the complete bipartite graph 
as
 |
(2)
|
Kleitman (1970) showed that the crossing numbers for 
,
,
,
and 
satisfy
 |
(3)
|
giving the specific equations
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
for all positive 
.
OpenAI (2026) announced a proof that 
for all positive integers 
and 
. The release attributes the argument to an unreleased internal
OpenAI model and supplies a Lean formalization of the full formula.
As of Oct. 7, 2026, VibeMathed (2026) had read the formal statement but had
not independently rebuilt it, and independent specialist verification of the complete
proof had not been reported.
For equal part sizes, Balogh et al. (2026) proved the asymptotic lower bound
 |
(8)
|
Their corresponding rectilinear crossing number bound is 
.
and 
." 2004. 
." J. Combin. Th. 9, 315-323, 1970.Kővari,
T.; Sós, V. T.; and Turán, P. "On a Problem of K. Zarankiewicz."
Colloq. Math. 3, 50-57, 1954.Numberphile. "The Brick
Factory Problem." May 31, 2023. 
in a Surface." J. Graph Th. 21, 51-54,
1996.Richter, R. B. and Thomassen, C. "Relations Between Crossing
Numbers of Complete and Complete Bipartite Graphs." Amer. Math. Monthly 104,
131-137, 1997.Turán, P. "A Note of Welcome." J.
Graph Th. 1, 7-9, 1977.VibeMathed. "Zarankiewicz's Crossing-Number
Conjecture (Turán's Brick Factory Problem)." Oct. 7, 2026.