Niech będzie cyklem z czterema wierzchołkami. Aby uzyskać dowolny wykres z wierzchołkami i krawędziami m, powiedz , ileistnieje? Czy jest na to dolna granica?
graph-theory
graph-minor
Shahrzad Haddadan
źródło
źródło
Odpowiedzi:
Tak, to jest znane. Dlad=Ω(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 .
źródło