Numero de 4 ciclos

Respuestas:

19

Sí, esto se sabe. Para con una constante implícita suficientemente grande, cualquier gráfico de nodos de grado promedio tiene total s. Esto es lo mejor posible porque se realiza mediante un gráfico aleatorio.d=Ω(n1/2)ndΩ(d4)C4

La referencia más temprana que conozco para esto es "Gráficos con sobresaturados de cubos y problemas relacionados" de Erdos y Simonovits, donde se afirma sin pruebas. Hay muchas pruebas por ahí, en la parte superior de mi cabeza, vea el Lema 3 aquí .

GMB
fuente