pregunta sobre el número de cruce

Question

Demuestre que existe una constante k tal que, para todo $5v < e$ existe un subgrafo del gráfico completo de $v$ verticales con número de cruce menor o igual que $k e^3/v^2$ .

¿Alguna pista para aplicar el argumento probabilístico?

Answer 1

Es posible que quieras mirar la desigualdad del número de cruce de esto enlace .

Answer 2

Este no es un argumento probabilístico, pero creo que responde a la pregunta.

Puede tomar $c$ copias de un gráfico completo $K_m$ . Elija $c$ y $m$ para que $$cm \approx v$$ y $$c {m \choose 2} \approx e.$$ El número de cruce de $K_m$ es $\Theta(m^4)$ por lo que el número de cruces de este gráfico está acotado por encima de $O(cm^4)$ . (La constante implícita es absoluta.) Por otro lado, $$e^3 / v^2 \approx c m^4 / 4.$$