# proof of crossing lemma

Euler’s formula implies the linear lower bound $\mathrm{cr}(G)\ge 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, $\mathrm{cr}({G}_{p})-{m}_{p}+3{n}_{p}\ge 0$. The expectation is clearly

$$E(\mathrm{cr}({G}_{p})-{m}_{p}+3{n}_{p})\ge 0.$$ |

Since $E({n}_{p})=pn$, $E({m}_{p})={p}^{2}m$ and $E({X}_{p})={p}^{4}\mathrm{cr}(G)$, we get an inequality that bounds the crossing number of $G$ from below,

$$\mathrm{cr}(G)\ge {p}^{-2}m-3{p}^{-3}n.$$ |

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

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

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

$$\mathrm{cr}(G)\ge \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 |