Ekstremalne grafy Turana / Delta 5 (420), str. 4-5

Paweł Naroski w swoim artykule "Pajęcza Rapsodia", Delta 5 (420), str. 4-5, daje czytelnikowi pierwszy smak ekstremalnej teorii grafów, której twórcą był Pál Turán. Można dojść do niej naturalnie, rozpatrując wcześniejszą teorię Ramseya. W teorii Ramseya zadajemy pytania typu: czy dla danego naturalnego n każde pokolorowanie krawędzi pełnego n-wierzchołkowego grafu na czerwono i zielono tworzy 3-wierzchołkową klikę czerwoną lub 4-wierzchołkową klikę zieloną? To pytanie akurat jest proste - odpowiedź brzmi TAK dla każdego n ≥ 9, oraz NIE dla n = 1 ... 8. Mimo odpowiedzi na pytanie typu Ramseya, wciąż może nas ciekawić ile maksimum krawędzi da się pomalować w grafie o n ≥ 9 wierzchołkach, bez stworzenia 3-kliki czerwonej ani 4-kliki zielonej. I to jest właśnie pytanie typu Turána. Najprostsze i mimo wszystko ciekawe pytanie Turána dotyczy nie dwóch (lub więcej) kolorów, lecz jednego (co w przypadku Ramseya prowadzi do trywialności). Właśnie jednokolorowym przypadkiem zajmuje się w swoim artykule Naroski. W przypadku jednokolorowym zamiast o grafie danego koloru mówimy po prostu o grafie. Okazuje się (co wiedziano i przed Turánem), że:

TWIERDZENIE (Mantel, 1906) Graf o n wierzchołkach, niezawierający 3-kliki (trójkąta), może mieć maksimum floor(n/2) ⋅ ceiling(n/2) krawędzi.

Z obowiązku reporterskiego :-) wspomnę o usterce w dowodzie w "Pajęcza Rapsodia". Cytuję (str. 4, pierwszy paragraf od dołu):

Taki [n-wierzchołkowy] graf musi zawierać węzeł, z którego wychodzi mniej niż n/2 krawędzi. Rzeczywiście! Weźmy dwa połączone krawędzią węzły. [...] z któregoś z nich wychodzi mniej niż n/2 krawędzi

To jednak jest nieprawdą: niech n=4 wierzchołkami będą 0 1 2 3, oraz krawędziami

{0 1}, {1 2}, {2 3}

Za połączone węzły przyjmijmy 1 2. Z każdego z nich wychodzą dokładnie n/2 = 2 krawędzie, wbrew tezie z artykułu.

Artykuł wszystko jedno jest pożyteczny!

A usterkę możemy usunąć nastepująco, przez poprawienie cytowanego argumentu:

Taki [n-wierzchołkowy] graf musi zawierać węzeł, z którego wychodzi nie więcej niż floor(n/2) krawędzi. Rzeczywiście! Weźmy dwa połączone krawędzią węzły. [...] z któregoś z nich wychodzi nie więcej niż floor(n/2) krawędzi

Dalej indukcja biegnie gładko, tyle że wymaga dwóch przypadków:

ZAKOŃCZENIE DOWODU: Pozostałe wierzchołki tworzą graf beztrójkątowy o co najwyżej floor((n-1)/2) ⋅ ceiling((n-1)/2) krawędziach. Więc cały graf ma ich nie wiecej niż

t := floor((n-1)/2) ⋅ ceiling((n-1)/2) + floor(n/2)

Dla n parzystego otrzymujemy:

t = (n/2 - 1) ⋅ n/2 + n/2 = (n/2) ⋅ n/2 = floor(n/2) ⋅ ceiling(n/2)

Dla n nieparzystego:

t = ((n-1)/2) ⋅ (n-1)/2 + (n-1)/2 = ((n-1)/2) ⋅ (n+1)/2
= floor(n/2) ⋅ ceiling(n/2)

KONIEC DOWODU