Екстремальна теорія графів

Наприклад, простим питанням екстремальної теорії графів є питання «Які ациклічні графи з n вершинами мають найбільше число ребер?» Екстремальними графами для цього питання будуть дерева з n вершинами, що мають n − 1 ребер[2]. Більш загальне типове питання таке: якщо дано властивість графу P, інваріант u[3] і набір графів H, ми хочемо знайти найменше значення m, таке, що будь-який граф з H, який має u, більше, ніж m, має властивість P. У прикладі вище H було множиною графів з n вершинами, P було властивістю «бути циклом», а u було числом ребер у графі. Таким чином, будь-який граф з n вершинами і більш ніж з n − 1 ребрами, повинен містити цикл.

Деякі функціональні результати в екстремальній теорії графів — це питання згаданих вище видів. Наприклад, на питання, як багато ребер графу з n вершинами має бути в графі, щоб він обов'язково містив як підграф кліку розміру k, відповідає теорема Турана. Якщо замість клік в аналогічному питанні запитують про повні багаточасткові графи, відповідь дає теорема Ердеша — Стоуна.

Екстремальна теорія графів виникла 1941 року, коли Туран довів свою теорему, яка визначає графи порядку n, що не містять повного графу K_k порядку k, і екстремальні відносно розміру (тобто з якомога меншим числом ребер)[4]. Наступним ключовим роком став 1975, коли Семереді довів свою теорему, важливий інструмент для атаки на екстремальні задачі[4].

Типовий результат екстремальної теорії графів — теорема Турана. Теорема відповідає на таке питання: яке максимально можливе число ребер в неорієнтованому графі G з n вершинами, що не містить K₃ (трьох вершин A, B, C з ребрами AB, AC, BC, тобто трикутника) як підграфу? Повний двочастковий граф, у якому частки відрізняються максимум на 1, є єдиним екстремальних графом з цією властивістю. Граф містить

${\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor }$

ребер. Подібні питання ставилися для різних інших підграфів H замість K₃. Наприклад, задача Заранкієвича запитує про найбільший (за числом ребер) граф, який не містить підграфом фіксованого повного двочасткового графу, а теорема про парні контури запитує про найбільший граф, який не містить парних циклів фіксованої довжини. Туран також знайшов (унікальний) найбільший граф, що не містить K_k, який названо його ім'ям, а саме граф Турана. Цей граф є повним об'єднанням «k-1» незалежних множин і має максимум

${\displaystyle \left\lfloor {\frac {(k-2)n^{2}}{2(k-1)}}\right\rfloor =\left\lfloor \left(1-{\frac {1}{k-1}}\right){\frac {n^{2}}{2}}\right\rfloor }$

ребер. Найбільший граф з n вершинами, що не містить C₄, має

${\displaystyle \left({\frac {1}{2}}+o(1)\right)n^{3/2}}$

ребер.

Згадані теореми дають умови для появи невеликих об'єктів усередині (можливо) великого графу. Як протилежні екстремуми можна шукати умову, яка змушує існування структури, що покриває всі вершини. Але граф з

${\displaystyle {\binom {n-1}{2}}}$

ребрами може мати ізольовані вершини, хоча майже всі можливі ребра присутні в графі, що означає, що навіть дуже щільні графи можуть не мати цікавої для нас структуру, яка покриває всі вершини. Проста умова, що спирається на підрахунок ребер, не дає інформації, як ребра розподілені в графі, так що часто така умова дає нецікаві результати для дуже великих структур. Замість цього ми вводимо поняття мінімального степеня. Мінімальний степінь графу G визначається як

${\displaystyle \delta (G)=\min _{v\in G}d(v).}$

Завдання великого мінімального степеня видаляє заперечення, що можуть існувати «патологічні» вершини. Якщо мінімальний степінь графу G дорівнює 1, наприклад, не може бути ізольованих вершин (навіть якщо G містить дуже мало ребер).

Класичним результатом є теорема Дірака, яка стверджує, що будь-який граф G з n вершинами і мінімальним степенем, не менше n/2, містить гамільтонів цикл.

• Теорія Рамсея