Liczba 4 cykli

Odpowiedzi:

19

Tak, to jest znane. Dla d=Ω(n1/2) z dostatecznie dużą utajonego stałej, każdy n wykres -node średniego stopnia d ma Ω(d4) całkowite C4 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 .

GMB
źródło