proof of crossing lemma

Euler’s formula implies the linear lower bound $\operatorname{cr}(G)\geq m-3n+6$ , and so it cannot be used directly. What we need is to consider the subgraphs of our graph, apply Euler’s formula on them, and then combine the estimates. The probabilistic method provides a natural way to do that.

Consider a minimal embedding of $G$ . Choose independently every vertex of $G$ with probability $p$ . Let $G_{p}$ be a graph induced by those vertices. By Euler’s formula, $\operatorname{cr}(G_{p})-m_{p}+3n_{p}\geq 0$ . The expectation is clearly

E(\operatorname{cr}(G_{p})-m_{p}+3n_{p})\geq 0.

Since $E(n_{p})=pn$ , $E(m_{p})=p^{2}m$ and $E(X_{p})=p^{4}\operatorname{cr}(G)$ , we get an inequality that bounds the crossing number of $G$ from below,

\operatorname{cr}(G)\geq p^{-2}m-3p^{-3}n.

Now set $p=\frac{4n}{m}$ (which is at most $1$ since $m\geq 4n$ ), and the inequaliy becomes

\operatorname{cr}(G)\geq\frac{1}{64}\frac{m^{3}}{n^{2}}.

Similarly, if $m\geq\frac{9}{2}n$ , then we can set $p=\frac{9n}{2m}$ to get

\operatorname{cr}(G)\geq\frac{4}{243}\frac{m^{3}}{n^{2}}.

References

1 Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK. Springer, 1999.

Title	proof of crossing lemma
Canonical name	ProofOfCrossingLemma
Date of creation	2013-03-22 13:38:46
Last modified on	2013-03-22 13:38:46
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	6
Author	bbukh (348)
Entry type	Proof
Classification	msc 05C10
Classification	msc 05C80
Related topic	ProbabilisticMethod