Anzahl von 4 Zyklen

Sei ein Zyklus mit vier Eckpunkten. Für einen beliebigen Graphen mit Ecken und m Kanten gilt: , wie viele existieren? Gibt es dafür eine Untergrenze?$C_4$$G$$n$$m>n\sqrt n$$C_4$

Ja, das ist bekannt. Für mit einer ausreichend großen impliziten konstant, jede -node Graph der durchschnittlichen Grad besitzt insgesamt s. Dies ist am besten möglich, da es durch einen zufälligen Graphen realisiert wird.$d = \Omega(n^{1/2})$$n$$d$$\Omega(d^4)$$C_4$

Die früheste mir bekannte Referenz dafür ist "Cube-Supersaturated Graphs and Related Problems" von Erdos und Simonovits, wo sie ohne Beweis behauptet wird. Es gibt viele Beweise da draußen, von oben gesehen, siehe Lemma 3 hier .