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?
Respuestas
¿Demasiados anuncios?
igi
Puntos
1055
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.$$
