Namespaces
Variants
Actions

Difference between revisions of "Zarankiewicz crossing number conjecture"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 30 formulas out of 31 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 31 formulas, 30 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|partial}}
 
''Turán brick factory problem''
 
''Turán brick factory problem''
  
 
P. Turán [[#References|[a6]]] tells about how he posed the following problem while in a forced labour camp in World War II:  "There were some kilns where the bricks were made and some open storage yards where the bricks were stored. All the kilns were connected by rail with all storage yards. … the trouble was only at crossings. The trucks generally jumped the rails there, and the bricks fell out of them; in short this caused a lot of trouble and loss of time … 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?"  
 
P. Turán [[#References|[a6]]] tells about how he posed the following problem while in a forced labour camp in World War II:  "There were some kilns where the bricks were made and some open storage yards where the bricks were stored. All the kilns were connected by rail with all storage yards. … the trouble was only at crossings. The trucks generally jumped the rails there, and the bricks fell out of them; in short this caused a lot of trouble and loss of time … 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?"  
  
Recall that a drawing of a finite [[Graph|graph]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z1300401.png" /> on the plane consists of placing the vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z1300402.png" /> on the plane and drawing the edges of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z1300403.png" /> using continuous curves of the plane, connecting corresponding vertices as endpoints of the curve such that no curve has a vertex as an internal point and no point is an internal point of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z1300404.png" /> curves. The crossing number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z1300405.png" /> of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z1300406.png" /> is the minimum number of intersection points among the curves representing edges, over all possible drawings of the graph. It is not hard to see that the crossing number can always be realized by a drawing with the following properties:
+
Recall that a drawing of a finite [[Graph|graph]] $G$ on the plane consists of placing the vertices of $G$ on the plane and drawing the edges of $G$ using continuous curves of the plane, connecting corresponding vertices as endpoints of the curve such that no curve has a vertex as an internal point and no point is an internal point of $3$ curves. The crossing number $\text{cr} ( G )$ of a graph $G$ is the minimum number of intersection points among the curves representing edges, over all possible drawings of the graph. It is not hard to see that the crossing number can always be realized by a drawing with the following properties:
  
 
i) there is no self-crossing of edges;
 
i) there is no self-crossing of edges;
Line 15: Line 23:
 
Put in the technical terms above, Zarankiewicz' crossing number conjecture, or Turán's brick factory problem, is as follows:  "what is the crossing number crKn,m of the complete bipartite graph Kn,m?"  
 
Put in the technical terms above, Zarankiewicz' crossing number conjecture, or Turán's brick factory problem, is as follows:  "what is the crossing number crKn,m of the complete bipartite graph Kn,m?"  
  
Place <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z1300407.png" /> vertices to negative positions on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z1300408.png" />-axis, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z1300409.png" /> vertices to positive positions on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004010.png" />-axis, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004011.png" /> vertices to negative positions on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004012.png" />-axis, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004013.png" /> vertices to positive positions on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004014.png" />-axis, and draw <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004015.png" /> edges by straight line segments to obtain a drawing of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004016.png" />. It is not hard to check that the following formula gives the number of crossings in this particular drawing:
+
Place $\lfloor n / 2 \rfloor$ vertices to negative positions on the $x$-axis, $\lceil n / 2 \rceil $ vertices to positive positions on the $x$-axis, $\lfloor m/ 2 \rfloor$ vertices to negative positions on the $y$-axis, $[ m / 2 ]$ vertices to positive positions on the $y$-axis, and draw <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004015.png"/> edges by straight line segments to obtain a drawing of $K _ { n , m}$. It is not hard to check that the following formula gives the number of crossings in this particular drawing:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004017.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
\begin{equation} \tag{a1} \left\lfloor \frac { n } { 2 } \right\rfloor \left\lfloor \frac { n - 1 } { 2 } \right\rfloor \left\lfloor \frac { m } { 2 } \right\rfloor \left\lfloor \frac { m - 1 } { 2 } \right\rfloor. \end{equation}
  
K. Zarankiewicz [[#References|[a10]]] and K. Urbaník [[#References|[a7]]] independently claimed and published that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004018.png" /> was actually equal to (a1), their argument was reprinted in a book, cited, and used in follow-up papers. However, P. Kainen and G. Ringel discovered a flaw in the argument and the flaw has withstood all attempts for correction (up till 2000). R. Guy deserves much credit for rectifying this confused state of art, see [[#References|[a2]]] and [[#References|[a3]]].
+
K. Zarankiewicz [[#References|[a10]]] and K. Urbaník [[#References|[a7]]] independently claimed and published that $\operatorname { cr } ( K _ { n  , m} )$ was actually equal to (a1), their argument was reprinted in a book, cited, and used in follow-up papers. However, P. Kainen and G. Ringel discovered a flaw in the argument and the flaw has withstood all attempts for correction (up till 2000). R. Guy deserves much credit for rectifying this confused state of art, see [[#References|[a2]]] and [[#References|[a3]]].
  
D.J. Kleitman showed that (a1) holds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004019.png" /> [[#References|[a4]]] and also proved that the smallest counterexample to the Zarankiewicz conjecture must occur for odd <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004021.png" />. D.R. Woodall [[#References|[a9]]] used an elaborate computer search to show that (a1) holds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004023.png" />. Thus, the smallest unsettled instances of Zarankiewicz's conjecture are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004025.png" />. It is known that
+
D.J. Kleitman showed that (a1) holds for $m \leq 6$ [[#References|[a4]]] and also proved that the smallest counterexample to the Zarankiewicz conjecture must occur for odd $n$ and $m$. D.R. Woodall [[#References|[a9]]] used an elaborate computer search to show that (a1) holds for $K _ { 7  , 7}$ and $K _ { 7  , 9}$. Thus, the smallest unsettled instances of Zarankiewicz's conjecture are $K _ { 7  , 11}$ and $K _ { 9  , 9}$. It is known that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004026.png" /></td> </tr></table>
+
\begin{equation*} c = \operatorname { lim } _ { n \rightarrow \infty } \operatorname { cr } ( K _ { n , n } ) \left( \begin{array} { l } { n } \\ { 2 } \end{array} \right) ^ { - 2 } \end{equation*}
  
exists; however, the value of the limit is not known (as of 2000) [[#References|[a5]]]. Woodall's result for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004027.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004028.png" /> by a standard counting argument, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004029.png" /> follows from the drawing shown. If (a1) always holds, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004030.png" />.
+
exists; however, the value of the limit is not known (as of 2000) [[#References|[a5]]]. Woodall's result for $K _ { 7  , 9}$ implies $4 / 21 \leq c$ by a standard counting argument, while $c \leq 1 / 4$ follows from the drawing shown. If (a1) always holds, then $c = 1 / 4$.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Pach,  G. Tóth,  "Which crossing number is it anyway?" , ''Proc. 39th Ann. Symp. Foundation of Computer Sci.'' , IEEE Press  (1998)  pp. 617–626</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.K. Guy,  "The decline and fall of Zarankiewicz's theorem"  F. Harary (ed.) , ''Proof Techniques in Graph Theory'' , Acad. Press  (1969)  pp. 63–69</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.K. Guy,  "# 21749"  ''Math. Rev.'' , '''58'''  (1974)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.J. Kleitman,  "The crossing number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/z/z130/z130040/z13004031.png" />"  ''J. Combin. Th.'' , '''9'''  (1970)  pp. 315–323</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R.B. Richter,  C. Thomassen,  "Relations between crossing numbers of complete and complete bipartite graphs"  ''Amer. Math. Monthly'' , '''104'''  (1997)  pp. 131–137</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  P. Turán,  "A note of welcome"  ''J. Graph Th.'' , '''1'''  (1977)  pp. 7–9</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  K. Urbaník,  "Solution du problème posé par P. Turán"  ''Colloq. Math.'' , '''3'''  (1955)  pp. 200–201</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  A.T. White,  L.W. Beineke,  "Topological graph theory"  L.W. Beineke (ed.)  R.J. Wilson (ed.) , ''Selected Topics in Graph Theory'' , Acad. Press  (1978)  pp. 15–50</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  D.R. Woodall,  "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture"  ''J. Graph Th.'' , '''17'''  (1993)  pp. 657–671</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  K. Zarankiewicz,  "On a problem of P. Turán concerning graphs"  ''Fundam. Math.'' , '''41'''  (1954)  pp. 137–145</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  J. Pach,  G. Tóth,  "Which crossing number is it anyway?" , ''Proc. 39th Ann. Symp. Foundation of Computer Sci.'' , IEEE Press  (1998)  pp. 617–626</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  R.K. Guy,  "The decline and fall of Zarankiewicz's theorem"  F. Harary (ed.) , ''Proof Techniques in Graph Theory'' , Acad. Press  (1969)  pp. 63–69</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  R.K. Guy,  "# 21749"  ''Math. Rev.'' , '''58'''  (1974)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  D.J. Kleitman,  "The crossing number of $K _ { 5  ,\, n }$"  ''J. Combin. Th.'' , '''9'''  (1970)  pp. 315–323</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  R.B. Richter,  C. Thomassen,  "Relations between crossing numbers of complete and complete bipartite graphs"  ''Amer. Math. Monthly'' , '''104'''  (1997)  pp. 131–137</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  P. Turán,  "A note of welcome"  ''J. Graph Th.'' , '''1'''  (1977)  pp. 7–9</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  K. Urbaník,  "Solution du problème posé par P. Turán"  ''Colloq. Math.'' , '''3'''  (1955)  pp. 200–201</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  A.T. White,  L.W. Beineke,  "Topological graph theory"  L.W. Beineke (ed.)  R.J. Wilson (ed.) , ''Selected Topics in Graph Theory'' , Acad. Press  (1978)  pp. 15–50</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  D.R. Woodall,  "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture"  ''J. Graph Th.'' , '''17'''  (1993)  pp. 657–671</td></tr><tr><td valign="top">[a10]</td> <td valign="top">  K. Zarankiewicz,  "On a problem of P. Turán concerning graphs"  ''Fundam. Math.'' , '''41'''  (1954)  pp. 137–145</td></tr></table>

Revision as of 17:00, 1 July 2020

Turán brick factory problem

P. Turán [a6] tells about how he posed the following problem while in a forced labour camp in World War II: "There were some kilns where the bricks were made and some open storage yards where the bricks were stored. All the kilns were connected by rail with all storage yards. … the trouble was only at crossings. The trucks generally jumped the rails there, and the bricks fell out of them; in short this caused a lot of trouble and loss of time … 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?"

Recall that a drawing of a finite graph $G$ on the plane consists of placing the vertices of $G$ on the plane and drawing the edges of $G$ using continuous curves of the plane, connecting corresponding vertices as endpoints of the curve such that no curve has a vertex as an internal point and no point is an internal point of $3$ curves. The crossing number $\text{cr} ( G )$ of a graph $G$ is the minimum number of intersection points among the curves representing edges, over all possible drawings of the graph. It is not hard to see that the crossing number can always be realized by a drawing with the following properties:

i) there is no self-crossing of edges;

ii) edges with the same endpoint do not cross;

iii) intersection points among the curves representing edges are crossing points, i.e. the curves do not touch each other; and

iv) any two edges intersect at most once. For variations in the definition of crossing numbers, see [a1].

Put in the technical terms above, Zarankiewicz' crossing number conjecture, or Turán's brick factory problem, is as follows: "what is the crossing number crKn,m of the complete bipartite graph Kn,m?"

Place $\lfloor n / 2 \rfloor$ vertices to negative positions on the $x$-axis, $\lceil n / 2 \rceil $ vertices to positive positions on the $x$-axis, $\lfloor m/ 2 \rfloor$ vertices to negative positions on the $y$-axis, $[ m / 2 ]$ vertices to positive positions on the $y$-axis, and draw edges by straight line segments to obtain a drawing of $K _ { n , m}$. It is not hard to check that the following formula gives the number of crossings in this particular drawing:

\begin{equation} \tag{a1} \left\lfloor \frac { n } { 2 } \right\rfloor \left\lfloor \frac { n - 1 } { 2 } \right\rfloor \left\lfloor \frac { m } { 2 } \right\rfloor \left\lfloor \frac { m - 1 } { 2 } \right\rfloor. \end{equation}

K. Zarankiewicz [a10] and K. Urbaník [a7] independently claimed and published that $\operatorname { cr } ( K _ { n , m} )$ was actually equal to (a1), their argument was reprinted in a book, cited, and used in follow-up papers. However, P. Kainen and G. Ringel discovered a flaw in the argument and the flaw has withstood all attempts for correction (up till 2000). R. Guy deserves much credit for rectifying this confused state of art, see [a2] and [a3].

D.J. Kleitman showed that (a1) holds for $m \leq 6$ [a4] and also proved that the smallest counterexample to the Zarankiewicz conjecture must occur for odd $n$ and $m$. D.R. Woodall [a9] used an elaborate computer search to show that (a1) holds for $K _ { 7 , 7}$ and $K _ { 7 , 9}$. Thus, the smallest unsettled instances of Zarankiewicz's conjecture are $K _ { 7 , 11}$ and $K _ { 9 , 9}$. It is known that

\begin{equation*} c = \operatorname { lim } _ { n \rightarrow \infty } \operatorname { cr } ( K _ { n , n } ) \left( \begin{array} { l } { n } \\ { 2 } \end{array} \right) ^ { - 2 } \end{equation*}

exists; however, the value of the limit is not known (as of 2000) [a5]. Woodall's result for $K _ { 7 , 9}$ implies $4 / 21 \leq c$ by a standard counting argument, while $c \leq 1 / 4$ follows from the drawing shown. If (a1) always holds, then $c = 1 / 4$.

References

[a1] J. Pach, G. Tóth, "Which crossing number is it anyway?" , Proc. 39th Ann. Symp. Foundation of Computer Sci. , IEEE Press (1998) pp. 617–626
[a2] R.K. Guy, "The decline and fall of Zarankiewicz's theorem" F. Harary (ed.) , Proof Techniques in Graph Theory , Acad. Press (1969) pp. 63–69
[a3] R.K. Guy, "# 21749" Math. Rev. , 58 (1974)
[a4] D.J. Kleitman, "The crossing number of $K _ { 5 ,\, n }$" J. Combin. Th. , 9 (1970) pp. 315–323
[a5] R.B. Richter, C. Thomassen, "Relations between crossing numbers of complete and complete bipartite graphs" Amer. Math. Monthly , 104 (1997) pp. 131–137
[a6] P. Turán, "A note of welcome" J. Graph Th. , 1 (1977) pp. 7–9
[a7] K. Urbaník, "Solution du problème posé par P. Turán" Colloq. Math. , 3 (1955) pp. 200–201
[a8] A.T. White, L.W. Beineke, "Topological graph theory" L.W. Beineke (ed.) R.J. Wilson (ed.) , Selected Topics in Graph Theory , Acad. Press (1978) pp. 15–50
[a9] D.R. Woodall, "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture" J. Graph Th. , 17 (1993) pp. 657–671
[a10] K. Zarankiewicz, "On a problem of P. Turán concerning graphs" Fundam. Math. , 41 (1954) pp. 137–145
How to Cite This Entry:
Zarankiewicz crossing number conjecture. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Zarankiewicz_crossing_number_conjecture&oldid=50374
This article was adapted from an original article by Łászló A. Székely (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article