It has applications in VLSI design and combinatorial geometry, and was discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi[1] and by Leighton.
[2] The crossing number inequality states that, for an undirected simple graph G with n vertices and e edges such that e > 7n, the crossing number cr(G) obeys the inequality The constant 29 is the best known to date, and is due to Ackerman.
(This distinction is necessary since some authors assume that in a proper drawing no two edges cross more than once.
)[6] The motivation of Leighton in studying crossing numbers was for applications to VLSI design in theoretical computer science.
[2] Later, Székely (1997) realized that this inequality yielded very simple proofs of some important theorems in incidence geometry.
If there were more incidences than the Szemerédi–Trotter bound, this graph would necessarily have more crossings than the total number of pairs of lines, an impossibility.
The inequality can also be used to prove Beck's theorem, that if a finite point set does not have a linear number of collinear points, then it determines a quadratic number of distinct lines.
[7] Similarly, Tamal Dey used it to prove upper bounds on geometric k-sets.
[8] We first give a preliminary estimate: for any graph G with n vertices and e edges, we have To prove this, consider a diagram of G which has exactly cr(G) crossings.
To obtain the actual crossing number inequality, we now use a probabilistic argument.
We let 0 < p < 1 be a probability parameter to be chosen later, and construct a random subgraph H of G by allowing each vertex of G to lie in H independently with probability p, and allowing an edge of G to lie in H if and only if its two vertices were chosen to lie in H. Let eH, nH and crH denote the number of edges, vertices and crossings of H, respectively.
Similarly, each of the edges in G has a probability p2 of remaining in H since both endpoints need to stay in H, therefore E[eH] = p2e.
Therefore, and we have Now if we set p = 4n/e < 1 (since we assumed that e > 4n), we obtain after some algebra A slight refinement of this argument allows one to replace 64 by 33.75 for e > 7.5n.
[3] For graphs with girth larger than 2r and e ≥ 4n, Pach, Spencer & Tóth (2000) demonstrated an improvement of this inequality to[9] Adiprasito showed a generalization to higher dimensions:[10] If