# 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

## 2 Answers

You may want to look at crossing number inequality of this link.

-
I am familiar with the crossing number theorem. This question is actually an exercise after the theorem. – ebg9 Dec 8 '11 at 13:23

This is not a probabilistic argument, but I think it answers the question.

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.$$

-