# crossing number question

Prove that there exists constant k such that, for all $5v < e$ there is a subgraph of the complete graph of $v$ vertics with crossing number less or equal than $k e^3/v^2$.

Any hints for a way to apply probabilistic argument ?

-
For an excellent survey and discussion of issues related to geometric incidences and crossings, look at the paper by Janos Pach and Micha Sharir entitled Geometric Incidences, in the book: Towards a Theory of Geometric Graphs, Volume 342, Contemporary Mathematics, American Mathematical Society, 2004. –  Joseph Malkevitch Feb 6 '12 at 17:03

You can take $c$ copies of a complete graph $K_m$. Choose $c$ and $m$ so that $$cm \approx v$$ and $$c {m \choose 2} \approx e.$$ The crossing number of $K_m$ is $\Theta(m^4)$, so the crossing number of this graph is bounded above by $O(cm^4)$. (The implied constant is absolute.) On the other hand, $$e^3 / v^2 \approx c m^4 / 4.$$