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 ?
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 ?
You may want to look at crossing number inequality of this link.
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.$