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

Екстремальна теорія графів — це гілка теорії графів. Екстремальна теорія графів вивчає екстремальні (максимальні або мінімальні) властивості графів, які задовольняють певним умовам. Екстремальність може стосуватися різних інваріантів графів, таких як порядок, розмір або обхват. В абстрактнішому сенсі, теорія вивчає, як глобальні властивості графу впливають на локальні підструктури графу.

Граф Турана T(n, r) є прикладом екстремального графу. Граф має найбільше можливе число ребер для графів з n вершинами без (r+1)-клік. На малюнку наведено граф T(13,4).

Приклади

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

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

Історія

Екстремальна теорія графів, в найстрогішому сенсі, є гілкою теорії графів, яку люблять і розвивають в Угорщині.

(Bollobás, 2004)

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

Щільність графу

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

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

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

$\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₄, має

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

ребер.

Умови мінімального степеня

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

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

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

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

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

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

Див. також

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

Література

• Béla Bollobás. Extremal Graph Theory. — New York : Dover Publications, 2004. — ISBN 978-0-486-43596-1.
• Béla Bollobás. Modern Graph Theory. — Berlin, New York : Springer-Verlag, 1998. — С. 103–144. — ISBN 978-0-387-98491-9.
• Reinhard Diestel. [1] — 4th. — Berlin, New York : Springer-Verlag, 2010. — С. 169–198. — ISBN 978-3-642-14278-9. Архівовано з джерела 29 грудня 2020
  • Рейнгард Дистель. Теория графов. — Новосибирск : Изд-во Ин-та математики, 2002. — ISBN 5-86134-101-X УДК 519.17.
• M. Simonovits. Slides from the Chorin summer school lectures, 2006.. Архівовано з джерела 29 листопада 2021. Процитовано 4 січня 2021.