## You are here

Homeproof of crossing lemma

## Primary tabs

# proof of crossing lemma

Euler’s formula implies the linear lower bound $\crn(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, $\crn(G_{p})-m_{p}+3n_{p}\geq 0$. The expectation is clearly

$E(\crn(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}\crn(G)$, we get an inequality that bounds the crossing number of $G$ from below,

$\crn(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

$\crn(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

$\crn(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.

## Mathematics Subject Classification

05C10*no label found*05C80

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections