3
$\begingroup$

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 ?

  • 0
    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.2012-02-06

2 Answers 2

1

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

  • 0
    I am familiar with the crossing number theorem. This question is actually an exercise after the theorem.2011-12-08
1

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