Английская Википедия:Crossing number inequality
Шаблон:Short description In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the minimum number of edge crossings in a plane drawing of a given graph, as a function of the number of edges and vertices of the graph. It states that, for graphs where the number Шаблон:Mvar of edges is sufficiently larger than the number Шаблон:Mvar of vertices, the crossing number is at least proportional to Шаблон:Math.
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]
Statement and history
The crossing number inequality states that, for an undirected simple graph Шаблон:Mvar with Шаблон:Mvar vertices and Шаблон:Mvar edges such that Шаблон:Math, the crossing number Шаблон:Math obeys the inequality
- <math>\operatorname{cr}(G) \geq \frac{e^3}{29 n^2}.</math>
The constant Шаблон:Math is the best known to date, and is due to Ackerman.[3] For earlier results with weaker constants see Шаблон:Harvtxt and Шаблон:Harvtxt.[4][5] The constant Шаблон:Math can be lowered to Шаблон:Math, but at the expense of replacing Шаблон:Math with the worse constant of Шаблон:Math.
It is important to distinguish between the crossing number Шаблон:Math and the pairwise crossing number Шаблон:Math. As noted by Шаблон:Harvtxt, the pairwise crossing number <math>\text{pair-cr}(G) \leq \text{cr}(G)</math> refers to the minimum number of pairs of edges that each determine one crossing, whereas the crossing number simply refers to the minimum number of crossings. (This distinction is necessary since some authors assume that in a proper drawing no two edges cross more than once.)[6]
Applications
The motivation of Leighton in studying crossing numbers was for applications to VLSI design in theoretical computer science.[2]
Later, Шаблон:Harvtxt realized that this inequality yielded very simple proofs of some important theorems in incidence geometry. For instance, the Szemerédi–Trotter theorem, an upper bound on the number of incidences that are possible between given numbers of points and lines in the plane, follows by constructing a graph whose vertices are the points and whose edges are the segments of lines between incident points. 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]
Proof
We first give a preliminary estimate: for any graph Шаблон:Mvar with Шаблон:Mvar vertices and Шаблон:Mvar edges, we have
- <math>\operatorname{cr}(G) \geq e - 3n.</math>
To prove this, consider a diagram of Шаблон:Mvar which has exactly Шаблон:Math crossings. Each of these crossings can be removed by removing an edge from Шаблон:Mvar. Thus we can find a graph with at least Шаблон:Math edges and Шаблон:Mvar vertices with no crossings, and is thus a planar graph. But from Euler's formula we must then have Шаблон:Math, and the claim follows. (In fact we have Шаблон:Math for Шаблон:Math).
To obtain the actual crossing number inequality, we now use a probabilistic argument. We let Шаблон:Math be a probability parameter to be chosen later, and construct a random subgraph Шаблон:Mvar of Шаблон:Mvar by allowing each vertex of Шаблон:Mvar to lie in Шаблон:Mvar independently with probability Шаблон:Mvar, and allowing an edge of Шаблон:Mvar to lie in Шаблон:Mvar if and only if its two vertices were chosen to lie in Шаблон:Mvar. Let Шаблон:Mvar and Шаблон:Math denote the number of edges, vertices and crossings of Шаблон:Mvar, respectively. Since Шаблон:Mvar is a subgraph of Шаблон:Mvar, the diagram of Шаблон:Mvar contains a diagram of Шаблон:Mvar. By the preliminary crossing number inequality, we have
- <math>\operatorname{cr}_H \geq e_H - 3n_H.</math>
Taking expectations we obtain
- <math>\mathbf{E}[\operatorname{cr}_H] \geq \mathbf{E}[e_H] - 3 \mathbf{E}[n_H].</math>
Since each of the Шаблон:Mvar vertices in Шаблон:Mvar had a probability Шаблон:Mvar of being in Шаблон:Mvar, we have Шаблон:Math. Similarly, each of the edges in Шаблон:Mvar has a probability Шаблон:Math of remaining in Шаблон:Mvar since both endpoints need to stay in Шаблон:Mvar, therefore Шаблон:Math. Finally, every crossing in the diagram of Шаблон:Mvar has a probability Шаблон:Math of remaining in Шаблон:Mvar, since every crossing involves four vertices. To see this consider a diagram of Шаблон:Mvar with Шаблон:Math crossings. We may assume that any two edges in this diagram with a common vertex are disjoint, otherwise we could interchange the intersecting parts of the two edges and reduce the crossing number by one. Thus every crossing in this diagram involves four distinct vertices of Шаблон:Mvar. Therefore, Шаблон:Math and we have
- <math> p^4 \operatorname{cr}(G) \geq p^2 e - 3 p n.</math>
Now if we set Шаблон:Math (since we assumed that Шаблон:Math), we obtain after some algebra
- <math> \operatorname{cr}(G) \geq \frac{e^3}{64 n^2}.</math>
A slight refinement of this argument allows one to replace Шаблон:Math by Шаблон:Math for Шаблон:Math.[3]
Variations
For graphs with girth larger than Шаблон:Math and Шаблон:Math, Шаблон:Harvtxt demonstrated an improvement of this inequality to[9]
- <math>\operatorname{cr}(G) \geq c_r\frac{e^{r+2}}{n^{r+1}}.</math>
Adiprasito showed a generalization to higher dimensions:[10] If <math>\Delta</math> is a simplicial complex that is mapped piecewise-linearly to <math>\mathbf{R}^{2d}</math>, and it has <math>f_d(\Delta)\ \ d </math>-dimensional faces and <math>f_{d-1}(\Delta)\ \ (d-1) </math>-dimensional faces such that <math>f_d(\Delta)> (d+3)f_{d-1}(\Delta) </math>, then the number of pairwise intersecting <math>d</math>-dimensional faces is at least
- <math>\frac{f_d^{d+2}(\Delta)}{(d+3)^{d+2}f_{d-1}^{d+1}(\Delta)}.</math>
References
