Turán's brick factory problem

Last updated September 18, 2022

A drawing method found by Kazimierz Zarankiewicz has been conjectured to give the correct answer for every complete bipartite graph, and the statement that this is true has come to be known as the Zarankiewicz crossing number conjecture. The conjecture remains open, with only some special cases solved.^[2]

Origin and formulation

During World War II, Hungarian mathematician Pál Turán was forced to work in a brick factory, pushing wagon loads of bricks from kilns to storage sites. The factory had tracks from each kiln to each storage site, and the wagons were harder to push at the points where tracks crossed each other. Turán was inspired by this situation to ask how the factory might be redesigned to minimize the number of crossings between these tracks.^[1]

Mathematically, this problem can be formalized as asking for a graph drawing of a complete bipartite graph, whose vertices represent kilns and storage sites, and whose edges represent the tracks from each kiln to each storage site. The graph should be drawn in the plane with each vertex as a point, each edge as a curve connecting its two endpoints, and no vertex placed on an edge that it is not incident to. A crossing is counted whenever two edges that are disjoint in the graph have a nonempty intersection in the plane. The question is then, what is the minimum number of crossings in such a drawing?^[2]^[3]

Turán's formulation of this problem is often recognized as one of the first studies of the crossing numbers of graphs.^[4] (Another independent formulation of the same concept occurred in sociology, in methods for drawing sociograms,^[5] and a much older puzzle, the three utilities problem, can be seen as a special case of the brick factory problem with three kilns and three storage facilities.^[6]) Crossing numbers have since gained greater importance, as a central object of study in graph drawing ^[7] and as an important tool in VLSI design^[8] and discrete geometry.^[9]

Upper bound

Both Zarankiewicz and Kazimierz Urbanik saw Turán speak about the brick factory problem in different talks in Poland in 1952,^[3] and independently published attempted solutions of the problem, with equivalent formulas for the number of crossings.^[10]^[11] As both of them showed, it is always possible to draw the complete bipartite graph $K m,n$ (a graph with $m$ vertices on one side, $n$ vertices on the other side, and $mn$ edges connecting the two sides) with a number of crossings equal to

\operatorname {cr} (K_{m,n})\leq {\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-1}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {m}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {m-1}{2}}{\biggr \rfloor }.

The construction is simple: place $m$ vertices on the $x$ -axis of the plane, avoiding the origin, with equal or nearly-equal numbers of points to the left and right of the $y$ -axis. Similarly, place $n$ vertices on the $y$ -axis of the plane, avoiding the origin, with equal or nearly-equal numbers of points above and below the $x$ -axis. Then, connect every point on the $x$ -axis by a straight line segment to every point on the $y$ -axis.^[3]

However, their proofs that this formula is optimal, that is, that there can be no drawings with fewer crossings, were erroneous. The gap was not discovered until eleven years after publication, nearly simultaneously by Gerhard Ringel and Paul Kainen.^[12] Nevertheless, it is conjectured that Zarankiewicz's and Urbanik's formula is optimal. This has come to be known as the Zarankiewicz crossing number conjecture. Although some special cases of it are known to be true, the general case remains open.^[2]

Lower bounds

Since $K m,n$ and $K n,m$ are isomorphic, it is enough to consider the case where $m \leq n$ . In addition, for $m \leq 2$ Zarankiewicz's construction gives no crossings, which of course cannot be bested. So the only nontrivial cases are those for which $m$ and $n$ are both $\geq 3$ .

Zarankiewicz's attempted proof of the conjecture, although invalid for the general case of $K m, n$ , works for the case $m = 3$ . It has since been extended to other small values of $m$ , and the Zarankiewicz conjecture is known to be true for the complete bipartite graphs $K m,n$ with $m \leq 6$ .^[13] The conjecture is also known to be true for $K 7,7$ , $K 7,8$ , and $K 7,9$ .^[14] If a counterexample exists, that is, a graph $K m,n$ requiring fewer crossings than the Zarankiewicz bound, then in the smallest counterexample both $m$ and $n$ must be odd.^[13]

For each fixed choice of $m$ , the truth of the conjecture for all $K m,n$ can be verified by testing only a finite number of choices of $n$ .^[15] More generally, it has been proven that every complete bipartite graph requires a number of crossings that is (for sufficiently large graphs) at least 83% of the number given by the Zarankiewicz bound. Closing the gap between this lower bound and the upper bound remains an open problem.^[16]

Rectilinear crossing numbers

If edges are required to be drawn as straight line segments, rather than arbitrary curves, then some graphs need more crossings than they would when drawn with curved edges. However, the upper bound established by Zarankiewicz for the crossing numbers of complete bipartite graphs can be achieved using only straight edges. Therefore, if the Zarankiewicz conjecture is correct, then the complete bipartite graphs have rectilinear crossing numbers equal to their crossing numbers.^[17]

Related Research Articles

The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges.

Kazimierz Zarankiewicz was a Polish mathematician and Professor at the Warsaw University of Technology who was interested primarily in topology and graph theory.

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph $is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.$

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgraphs of a given size. It belongs to the field of extremal graph theory, a branch of combinatorics, and is named after the Polish mathematician Kazimierz Zarankiewicz, who proposed several special cases of the problem in 1951.

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In mathematics, the Cheeger constant of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected networks of computers, card shuffling. The graph theoretical notion originated after the Cheeger isoperimetric constant of a compact Riemannian manifold.

In graph theory, the crossing number $cr(G)$ of a graph $G$ is the lowest number of edge crossings of a plane drawing of the graph $G$ . For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.

In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number of a graph G = (V, E) is the minimum number of bicliques, needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes biclique cover. The bipartite dimension of G is often denoted by the symbol d(G).

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph $, find the maximal number of edges in an -vertex graph which does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph .$

In combinatorial mathematics, the Albertson conjecture is an unproven relationship between the crossing number and the chromatic number of a graph. It is named after Michael O. Albertson, a professor at Smith College, who stated it as a conjecture in 2007; it is one of his many conjectures in graph coloring theory. The conjecture states that, among all graphs requiring $colors, the complete graph is the one with the smallest crossing number. Equivalently, if a graph can be drawn with fewer crossings than, then, according to the conjecture, it may be colored with fewer than colors.$

In graph theory, the graph bandwidth problem is to label the $n$ vertices $v i$ of a graph $G$ with distinct integers $so that the quantity is minimized . The problem may be visualized as placing the vertices of a graph at distinct integer points along the x -axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement .$

In the mathematical field of graph theory, the intersection number of a graph $is the smallest number of elements in a representation of as an intersection graph of finite sets. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of cliques needed to cover all of the edges of .$

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.

In graph theory, the thickness of a graph $G$ is the minimum number of planar graphs into which the edges of $G$ can be partitioned. That is, if there exists a collection of $k$ planar graphs, all having the same set of vertices, such that the union of these planar graphs is $G$ , then the thickness of $G$ is at most $k$ . In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph $G$ .

In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.

In graph theory, a branch of mathematics, a $t$ -biclique-free graph is a graph that has no $2t$ -vertex complete bipartite graph $K t, t$ as a subgraph. A family of graphs is biclique-free if there exists a number $t$ such that the graphs in the family are all $t$ -biclique-free. The biclique-free graph families form one of the most general types of sparse graph family. They arise in incidence problems in discrete geometry, and have also been used in parameterized complexity.

Crossing Numbers of Graphs is a book in mathematics, on the minimum number of edge crossings needed in graph drawings. It was written by Marcus Schaefer, a professor of computer science at DePaul University, and published in 2018 by the CRC Press in their book series Discrete Mathematics and its Applications.

References

1 2 Turán, P. (1977), "A note of welcome", Journal of Graph Theory , 1: 7–9, doi:10.1002/jgt.3190010105 .
1 2 3 Pach, János; Sharir, Micha (2009), "5.1 Crossings—the Brick Factory Problem", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 126–127.
1 2 3 Beineke, Lowell; Wilson, Robin (2010), "The early history of the brick factory problem", The Mathematical Intelligencer , 32 (2): 41–48, doi:10.1007/s00283-009-9120-4, MR 2657999, S2CID 122588849 .
↑ Foulds, L. R. (1992), Graph Theory Applications, Universitext, Springer, p. 71, ISBN 9781461209331 .
↑ Bronfenbrenner, Urie (1944), "The graphic presentation of sociometric data", Sociometry, 7 (3): 283–289, doi:10.2307/2785096, JSTOR 2785096, The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines.
↑ Bóna, Miklós (2011), A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific, pp. 275–277, ISBN 9789814335232 . Bóna introduces the puzzle (in the form of three houses to be connected to three wells) on p. 275, and writes on p. 277 that it "is equivalent to the problem of drawing $K 3,3$ on a plane surface without crossings".
↑ Schaefer, Marcus (2014), "The graph crossing number and its variants: a survey", The Electronic Journal of Combinatorics : #DS21
↑ Leighton, T. (1983), Complexity Issues in VLSI, Foundations of Computing Series, Cambridge, MA: MIT Press
↑ Székely, L. A. (1997), "Crossing numbers and hard Erdős problems in discrete geometry", Combinatorics, Probability and Computing , 6 (3): 353–358, doi:10.1017/S0963548397002976, MR 1464571
↑ Zarankiewicz, K. (1954), "On a problem of P. Turan concerning graphs", Fundamenta Mathematicae , 41: 137–145, doi: 10.4064/fm-41-1-137-145 , MR 0063641 .
↑ Urbaník, K. (1955), "Solution du problème posé par P. Turán", Colloq. Math., 3: 200–201. As cited by Székely, László A. (2001) [1994], "Zarankiewicz crossing number conjecture", Encyclopedia of Mathematics , EMS Press
↑ Guy, Richard K. (1969), "The decline and fall of Zarankiewicz's theorem", Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, pp. 63–69, MR 0253931 .
1 2 Kleitman, Daniel J. (1970), "The crossing number of $K 5, n$ ", Journal of Combinatorial Theory , 9: 315–323, doi: 10.1016/s0021-9800(70)80087-4 , MR 0280403 .
↑ Woodall, D. R. (1993), "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture", Journal of Graph Theory , 17 (6): 657–671, doi:10.1002/jgt.3190170602, MR 1244681 .
↑ Christian, Robin; Richter, R. Bruce; Salazar, Gelasio (2013), "Zarankiewicz's conjecture is finite for each fixed $m$ ", Journal of Combinatorial Theory , Series B, 103 (2): 237–247, doi:10.1016/j.jctb.2012.11.001, MR 3018068 .
↑ de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. (2006), "Improved bounds for the crossing numbers of $K m,n$ and $K n$ ", SIAM Journal on Discrete Mathematics , 20 (1): 189–202, arXiv: math/0404142 , doi:10.1137/S0895480104442741, MR 2257255, S2CID 1509054 .
↑ Kainen, Paul C. (1968), "On a problem of P. Erdős", Journal of Combinatorial Theory , 5 (4): 374–377, doi: 10.1016/s0021-9800(68)80013-4 , MR 0231744

External links

Weisstein, Eric W., "Zarankiewicz's Conjecture", MathWorld

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[turan-1] 1 2 Turán, P. (1977), "A note of welcome", Journal of Graph Theory , 1: 7–9, doi:10.1002/jgt.3190010105 .

[ps-2] 1 2 3 Pach, János; Sharir, Micha (2009), "5.1 Crossings—the Brick Factory Problem", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 126–127.

[early-3] 1 2 3 Beineke, Lowell; Wilson, Robin (2010), "The early history of the brick factory problem", The Mathematical Intelligencer , 32 (2): 41–48, doi:10.1007/s00283-009-9120-4, MR 2657999, S2CID 122588849 .

[foulds-4] Foulds, L. R. (1992), Graph Theory Applications, Universitext, Springer, p. 71, ISBN 9781461209331 .

[bron-5] Bronfenbrenner, Urie (1944), "The graphic presentation of sociometric data", Sociometry, 7 (3): 283–289, doi:10.2307/2785096, JSTOR 2785096, The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines.

[bona-6] Bóna, Miklós (2011), A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific, pp. 275–277, ISBN 9789814335232 . Bóna introduces the puzzle (in the form of three houses to be connected to three wells) on p. 275, and writes on p. 277 that it "is equivalent to the problem of drawing $K 3,3$ on a plane surface without crossings".

[variants-7] Schaefer, Marcus (2014), "The graph crossing number and its variants: a survey", The Electronic Journal of Combinatorics : #DS21

[leighton-8] Leighton, T. (1983), Complexity Issues in VLSI, Foundations of Computing Series, Cambridge, MA: MIT Press

[szekely-9] Székely, L. A. (1997), "Crossing numbers and hard Erdős problems in discrete geometry", Combinatorics, Probability and Computing , 6 (3): 353–358, doi:10.1017/S0963548397002976, MR 1464571

[z-10] Zarankiewicz, K. (1954), "On a problem of P. Turan concerning graphs", Fundamenta Mathematicae , 41: 137–145, doi: 10.4064/fm-41-1-137-145 , MR 0063641 .

[urbanik-11] Urbaník, K. (1955), "Solution du problème posé par P. Turán", Colloq. Math., 3: 200–201. As cited by Székely, László A. (2001) [1994], "Zarankiewicz crossing number conjecture", Encyclopedia of Mathematics , EMS Press

[fall-12] Guy, Richard K. (1969), "The decline and fall of Zarankiewicz's theorem", Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, pp. 63–69, MR 0253931 .

[kleitman-13] 1 2 Kleitman, Daniel J. (1970), "The crossing number of $K 5, n$ ", Journal of Combinatorial Theory , 9: 315–323, doi: 10.1016/s0021-9800(70)80087-4 , MR 0280403 .

[woodall-14] Woodall, D. R. (1993), "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture", Journal of Graph Theory , 17 (6): 657–671, doi:10.1002/jgt.3190170602, MR 1244681 .

[crs-15] Christian, Robin; Richter, R. Bruce; Salazar, Gelasio (2013), "Zarankiewicz's conjecture is finite for each fixed $m$ ", Journal of Combinatorial Theory , Series B, 103 (2): 237–247, doi:10.1016/j.jctb.2012.11.001, MR 3018068 .

[kmprs-16] Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. (2006), "Improved bounds for the crossing numbers of $K m,n$ and $K n$ ", SIAM Journal on Discrete Mathematics , 20 (1): 189–202, arXiv: math/0404142 , doi:10.1137/S0895480104442741, MR 2257255, S2CID 1509054 .

[jct-17] Kainen, Paul C. (1968), "On a problem of P. Erdős", Journal of Combinatorial Theory , 5 (4): 374–377, doi: 10.1016/s0021-9800(68)80013-4 , MR 0231744

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]