I want to prove the Crossing Number lemma for multigraph below by using probability method (The result for simple graph can be used)
Lemma: Given a multigraph $G$ with $n$ vertices, $e$ edges, and a maximum edge multiplicity of $m$, and $e > 5mn$. Prove that: $cr(G) \geq \frac{e^3}{m.n^2}$ with $cr(G)$ is crossing number.

There some hint as a sketch from the book as you need: First, delete edges independently with probability $1 - \frac{1}{k}$ and then delete all the remaining multiple edges. Call this resulting graph G'. Calculate the probability $p_e$ that a fixed edge e remains in G'. Now compare the expected number of edges and crossings in G' with the number in the original graph and use Lemma of Crossing Number for simple graph. Finally, use Jensen’s inequality with $f(x) = x^a$, which says that $E[x^a] \geq (E[x])^a$ for a ≥ 1.

Thanks for your help



You must log in to answer this question.

Browse other questions tagged .