Теорема Турана

Теорема Турана — это фундаментальный результат экстремальной теории графов, устанавливающий максимальное количество рёбер в графе на заданном числе вершин, не содержащем полный подграф \(K_{r+1}\) (клику размера \(r+1\)). Теорема была доказана венгерским математиком Палом Тураном в 1941 году и является одним из краеугольных камней комбинаторики.

Формулировка

Пусть \(G\) — граф на \(n\) вершинах, не содержащий полного подграфа на \(r+1\) вершине (\(K_{r+1}\)). Тогда максимальное возможное число рёбер в таком графе равно \[ \left(1 - \frac{1}{r}\right) \frac{n^2}{2} + O(n), \] а точное максимальное число достигается на графе Турана \(T(n, r)\).

Граф Турана \(T(n, r)\) — это полный \(r\)-дольный граф, доли которого имеют размеры, отличающиеся не более чем на 1. Иными словами, вершины разбиваются на \(r\) как можно более равных частей, и рёбра проводятся между любыми двумя вершинами из разных долей. Внутри каждой доли рёбер нет.

Формула для точного числа рёбер в \(T(n, r)\): \[ e(T(n, r)) = \left(1 - \frac{1}{r}\right) \frac{n^2}{2} - \frac{s(r-s)}{2r}, \] где \(n = qr + s\) (\(0 \le s < r\)), то есть \(s\) — остаток от деления \(n\) на \(r\).

История

Пал Туран (1910–1976) был одним из ведущих венгерских математиков XX века, работавшим в области теории чисел, комбинаторики и анализа. В 1940 году, во время Второй мировой войны, он был интернирован в трудовой лагерь. По его собственным воспоминаниям, именно в лагере, наблюдая за кирпичной кладкой, он задумался о задаче: как расположить максимальное количество кирпичей, чтобы ни один ряд не содержал полного квадрата из четырёх кирпичей? Эта задача привела его к формулировке теоремы. Результат был опубликован в 1941 году в статье «On an extremal problem in graph theory» (Matematikai és Fizikai Lapok, 48: 436–452).

Доказательство

Существует несколько способов доказательства теоремы Турана. Наиболее известное — индуктивное доказательство с удалением вершины.

Идея индукции

1. База: Для \(n \le r\) граф без \(K_{r+1}\) может быть полным, и число рёбер равно \(\binom{n}{2}\), что не превосходит правой части формулы.
2. Шаг: Пусть \(G\) — граф на \(n\) вершинах без \(K_{r+1}\) с максимальным числом рёбер. Выберем вершину \(v\) максимальной степени \(\Delta\). Тогда её соседи образуют граф без \(K_r\) (иначе вместе с \(v\) получилась бы \(K_{r+1}\)). По индукционному предположению, число рёбер между соседями не превосходит \(e(T(\Delta, r-1))\). Остальные рёбра — это рёбра, инцидентные \(v\) (их \(\Delta\)), и рёбра, соединяющие соседей \(v\) с несоседями \(v\) (их не более \((n-1-\Delta)\Delta\)). Суммируя и оптимизируя по \(\Delta\), получаем требуемое.

Другой подход — метод усреднения (среднее арифметическое и среднее квадратическое) или перестановочное неравенство (Zarankiewicz).

Следствия и обобщения

Теорема Турана — общий случай

Теорема обобщается на запрет любого подграфа \(H\) с хроматическим числом \(\chi(H) = r+1\). В этом случае максимальное число рёбер в графе на \(n\) вершинах без \(H\) асимптотически равно \(\left(1 - \frac{1}{r}\right) \frac{n^2}{2}\). Это — теорема Эрдёша — Стоуна (1946).

Теорема Турана для гиперграфов

Существуют обобщения на \(k\)-однородные гиперграфы (теорема Турана для гиперграфов), но точные экстремальные конструкции известны лишь для немногих случаев.

Применение в теории Рамсея

Теорема Турана используется для получения нижних оценок чисел Рамсея \(R(r+1, s)\): если граф без \(K_{r+1}\) имеет много рёбер, то в нём обязательно есть большой независимый набор вершин.

Примеры

Граф Турана \(T(7, 3)\)

Разобьём 7 вершин на 3 доли: 3, 2 и 2 вершины. Рёбра — между всеми парами из разных долей. Число рёбер: \[ 3\cdot2 + 3\cdot2 + 2\cdot2 = 6 + 6 + 4 = 16. \] Любой граф на 7 вершинах без треугольника (\(K_3\)) имеет не более 16 рёбер. Максимум достигается на \(T(7,3)\).

Граф Турана \(T(10, 4)\)

Доли: 3, 3, 2, 2. Рёбра: \(3\cdot3 + 3\cdot2 + 3\cdot2 + 3\cdot2 + 3\cdot2 + 2\cdot2 = 9 + 6 + 6 + 6 + 6 + 4 = 37\). Это максимум для графа без \(K_5\) на 10 вершинах.

Значение

Теорема Турана положила начало экстремальной теории графов — области, изучающей максимальные и минимальные значения графовых инвариантов при заданных ограничениях. Она применяется в:

• Теории кодирования — для оценки размеров кодов с запрещёнными конфигурациями.
• Компьютерных науках — в задачах о максимальном потоке, кластеризации и анализе социальных сетей.
• Комбинаторной геометрии — в задачах о расположении точек и прямых.

Интересные факты

• Теорема Турана является частным случаем теоремы Эрдёша — Стоуна, которая даёт асимптотику для любого запрещённого подграфа с хроматическим числом больше 2.
• Для \(r=2\) теорема Турана превращается в теорему Мантеля (1907): граф без треугольника на \(n\) вершинах имеет не более \(\lfloor n^2/4 \rfloor\) рёбер, и максимум достигается на полном двудольном графе \(K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}\).
• Граф Турана \(T(n, r)\) является максимальным по включению графом без \(K_{r+1}\): добавление любого ребра создаёт клику \(K_{r+1}\).

Источники

• Turán, P. (1941). «On an extremal problem in graph theory». Matematikai és Fizikai Lapok, 48: 436–452.
• Diestel, R. (2017). Graph Theory. Springer.
• Bollobás, B. (1998). Modern Graph Theory. Springer.
• А. А. Зыков. (1987). Основы теории графов. Наука.