Crossing number inequality

The crossing number inequality states that, for an undirected simple graph with vertices and edges such that , the crossing number obeys the inequality :\operatorname{cr}(G) \geq \frac{e^3}{29 n^2}. The constant is the best known to date, and is due to Ackerman. For earlier results with weaker constants see and . The constant can be lowered to , but at the expense of replacing with the worse constant of . It is important to distinguish between the crossing number and the pairwise crossing number . As noted by , the pairwise crossing number \text{pair-cr}(G) \leq \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. Similarly, Tamal Dey used it to prove upper bounds on geometric k-sets. ==Proof==

We first give a preliminary estimate: for any graph with vertices and edges, we have : \operatorname{cr}(G) \geq e - 3n. To prove this, consider a diagram of which has exactly crossings. Each of these crossings can be removed by removing an edge from . Thus we can find a graph with at least edges and vertices with no crossings, and is thus a planar graph. But from Euler's formula we must then have , and the claim follows. (In fact we have for ). To obtain the actual crossing number inequality, we now use a probabilistic argument. We let be a probability parameter to be chosen later, and construct a random subgraph of by allowing each vertex of to lie in independently with probability , and allowing an edge of to lie in if and only if its two vertices were chosen to lie in . Let and denote the number of edges, vertices and crossings of , respectively. Since is a subgraph of , the diagram of contains a diagram of . By the preliminary crossing number inequality, we have :\operatorname{cr}_H \geq e_H - 3n_H. Taking expectations we obtain :\mathbf{E}[\operatorname{cr}_H] \geq \mathbf{E}[e_H] - 3 \mathbf{E}[n_H]. Since each of the vertices in had a probability of being in , we have . Similarly, each of the edges in has a probability of remaining in since both endpoints need to stay in , therefore . Finally, every crossing in the diagram of has a probability of remaining in , since every crossing involves four vertices. To see this consider a diagram of with 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 . The diagram we have got may be not optimal in terms of number of crossings, but it obviously has at least crossings. Therefore, : p^4 \operatorname{cr}(G) \geq \mathbf{E} [ \operatorname{cr}_H ] and we have : p^4 \operatorname{cr}(G) \geq p^2 e - 3 p n. Now if we set (since we assumed that ), we obtain after some algebra : \operatorname{cr}(G) \geq \frac{e^3}{64 n^2}. A slight refinement of this argument allows one to replace by for . ==Variations==

For graphs with girth larger than and , demonstrated an improvement of this inequality to :\operatorname{cr}(G) \geq c_r\frac{e^{r+2}}{n^{r+1}}. Adiprasito showed a generalization to higher dimensions: If \Delta is a simplicial complex that is mapped piecewise-linearly to \mathbf{R}^{2d}, and it has f_d(\Delta)\ \ d -dimensional faces and f_{d-1}(\Delta)\ \ (d-1) -dimensional faces such that f_d(\Delta)> (d+3)f_{d-1}(\Delta) , then the number of pairwise intersecting d-dimensional faces is at least :\frac{f_d^{d+2}(\Delta)}{(d+3)^{d+2}f_{d-1}^{d+1}(\Delta)}. ==References==