Lesson 6

From the just-proven theorem it follows that \(\operatorname{cr}(K_{6}) \ge 3\) and that \(\operatorname{cr}(K_{n}) = \Omega(n^{2})\).

The following theorem significantly strengthens this estimate. It is proven using the probabilistic method. Let us recall the idea of this method: to prove that an object with a desired property exists, we take a random object and prove that it has this property with nonzero probability. Here we will prove that there does not exist a too-good drawing of a dense graph in the plane. To do this, we proceed as follows: suppose that such a good drawing exists, then using the probabilistic method we will show that this drawing has a part that is already too good to be true.

Theorem (Leighton; Ajtai, Chvátal, Newborn, Szemerédi). Let \(G(V,E)\) be a graph such that \(|E| \ge 4|V|\). Then \[\operatorname{cr}(G) \ge \frac{|E|^3}{64|V|^2}\ .\] In particular, \(\operatorname{cr}(K_{n}) = \Theta(n^{4})\).

Proof. Take an optimal drawing of \(G\) and consider a random subgraph \(H\) of \(G\): include each vertex in \(H\) (independently) with probability \(p\), the value of \(p\) will be chosen later. If we keep only the vertices and edges of \(H\) from the original drawing \(G\), we get some drawing \(T_{H}\) of the graph \(H\), which need not be optimal. Therefore, by the inequality \[\operatorname{cr}(G) \ge |E(G)|-3|V(G)|+6\] we get: \[\operatorname{cr}(T_{H}) \ge \operatorname{cr}(H) \ge |E(H)|-3|V(H)| \ .\] All parts of this inequality are random variables; let us take their expectations: \[\begin{equation*}\operatorname{E}[\operatorname{cr}(T_{H})] \ge \operatorname{E}[|E(H)|]-3\operatorname{E}[|V(H)|] \ .\end{equation*}\] Now we estimate these expectations: \(\operatorname{E}[|V(H)|]=p|V(G)|\), since each vertex survives with probability \(p\); \(\operatorname{E}[|E(H)|]=p^{2}|E(G)|\), since each edge survives with probability \(p^{2}\); finally, \(\operatorname{E}[\operatorname{cr}(T_{H})]=p^{4}\operatorname{cr}(G)\), since each crossing survives with probability \(p^{4}\). In the last estimate it is important that in the optimal drawing of \(G\) no two edges with a common endpoint cross (and so each crossing involves four rather than three vertices), and that no two edges cross more than once (hence, the number of crossings can be written as a sum over all pairs of edges). Substituting the obtained estimates into the inequality above: \[p^{4}\operatorname{cr}(G) \ge p^{2}|E(G)|-3p|V(G)|.\] Divide by \(p^{4}\): \[\operatorname{cr}(G) \ge \frac{|E(G)|}{p^2}-\frac{3|V(G)|}{p^3}\ .\] Choosing \(p=\frac{4|V|}{|E|}\), we obtain the desired estimate (it is important that under the theorem's condition this number is a valid probability).◼