Liczba 4 cykli

Niech $C_4$ będzie cyklem z czterema wierzchołkami. Aby uzyskać dowolny wykres $G$ z $n$ wierzchołkami i krawędziami m, powiedz $m>n\sqrt n$ , ileistnieje$C_4$? Czy jest na to dolna granica?

Tak, to jest znane. Dla $d = \Omega(n^{1/2})$ z dostatecznie dużą utajonego stałej, każdy $n$ wykres -node średniego stopnia $d$ ma $\Omega(d^4)$ całkowite $C_4$ s. Jest to najlepiej możliwe, ponieważ jest realizowane przez losowy wykres.

Najwcześniejsze odniesienie, o którym jestem tego świadomy, to „przesycone kostkami wykresy i powiązane problemy” autorstwa Erdosa i Simonovitsa, o których twierdzi się bez dowodu. Istnieje wiele dowodów, z góry mojej głowy, patrz Lemma 3 tutaj .