Crossing number inequality

Template: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 Template:Mvar of edges is sufficiently larger than the number Template:Mvar of vertices, the crossing number is at least proportional to Template:Math.

It has applications in VLSI design and combinatorial geometry, and was discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi and by Leighton.

Statement and history

The crossing number inequality states that, for an undirected simple graph Template:Mvar with Template:Mvar vertices and Template:Mvar edges such that Template:Math, the crossing number Template:Math obeys the inequality

$\mathrm{cr}(G)\ge \frac{e^3}{29n^2}.$

The constant Template:Math is the best known to date, and is due to Ackerman. For earlier results with weaker constants see Template:Harvtxt and Template:Harvtxt. The constant Template:Math can be lowered to Template:Math, but at the expense of replacing Template:Math with the worse constant of Template:Math.

It is important to distinguish between the crossing number Template:Math and the pairwise crossing number Template:Math. As noted by Template:Harvtxt, the pairwise crossing number $\text{pair-cr}(G)\le \text{cr}(G)$ 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.)

Applications

The motivation of Leighton in studying crossing numbers was for applications to VLSI design in theoretical computer science.

Later, Template: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. Similarly, Tamal Dey used it to prove upper bounds on geometric k-sets.

Proof

We first give a preliminary estimate: for any graph Template:Mvar with Template:Mvar vertices and Template:Mvar edges, we have

$\mathrm{cr}(G)\ge e-3n.$

To prove this, consider a diagram of Template:Mvar which has exactly Template:Math crossings. Each of these crossings can be removed by removing an edge from Template:Mvar. Thus we can find a graph with at least Template:Math edges and Template:Mvar vertices with no crossings, and is thus a planar graph. But from Euler's formula we must then have Template:Math, and the claim follows. (In fact we have Template:Math for Template:Math).

To obtain the actual crossing number inequality, we now use a probabilistic argument. We let Template:Math be a probability parameter to be chosen later, and construct a random subgraph Template:Mvar of Template:Mvar by allowing each vertex of Template:Mvar to lie in Template:Mvar independently with probability Template:Mvar, and allowing an edge of Template:Mvar to lie in Template:Mvar if and only if its two vertices were chosen to lie in Template:Mvar. Let Template:Mvar and Template:Math denote the number of edges, vertices and crossings of Template:Mvar, respectively. Since Template:Mvar is a subgraph of Template:Mvar, the diagram of Template:Mvar contains a diagram of Template:Mvar. By the preliminary crossing number inequality, we have

${\mathrm{cr}}_H\ge e_H-3n_H.$

Taking expectations we obtain

$𝐄[{\mathrm{cr}}_H]\ge 𝐄[e_H]-3𝐄[n_H].$

Since each of the Template:Mvar vertices in Template:Mvar had a probability Template:Mvar of being in Template:Mvar, we have Template:Math. Similarly, each of the edges in Template:Mvar has a probability Template:Math of remaining in Template:Mvar since both endpoints need to stay in Template:Mvar, therefore Template:Math. Finally, every crossing in the diagram of Template:Mvar has a probability Template:Math of remaining in Template:Mvar, since every crossing involves four vertices. To see this consider a diagram of Template:Mvar with Template: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 Template:Mvar. The diagram we have got may be not optimal in terms of number of crossings, but it obviously has at least Template:Math crossings. Therefore,

$p^4\mathrm{cr}(G)\ge 𝐄[{\mathrm{cr}}_H]$

and we have

$p^4\mathrm{cr}(G)\ge p^{2}e-3pn.$

Now if we set Template:Math (since we assumed that Template:Math), we obtain after some algebra

$\mathrm{cr}(G)\ge \frac{e^3}{64n^2}.$

A slight refinement of this argument allows one to replace Template:Math by Template:Math for Template:Math.

Variations

For graphs with girth larger than Template:Math and Template:Math, Template:Harvtxt demonstrated an improvement of this inequality to

$\mathrm{cr}(G)\ge c_r\frac{e^{r+2}}{n^{r+1}}.$

Adiprasito showed a generalization to higher dimensions: If $\mathrm{\Delta }$ is a simplicial complex that is mapped piecewise-linearly to ${𝐑}^{2d}$, and it has $f_d(\mathrm{\Delta })d$-dimensional faces and $f_{d-1}(\mathrm{\Delta })(d-1)$-dimensional faces such that $f_d(\mathrm{\Delta })>(d+3)f_{d-1}(\mathrm{\Delta })$, then the number of pairwise intersecting $d$-dimensional faces is at least

$\frac{f_d^{d+2}(\mathrm{\Delta })}{(d+3{)}^{d+2}{f}_{d-1}^{d+1}(\mathrm{\Delta })}.$