Введение

Теория экстремальных графов, ограничивающая число ребер в графах без клик

В теории графов теорема Турана ограничивает количество ребер, которые могут содержаться в неориентированном графе, не имеющем полного подграфа заданного размера. Это один из центральных результатов экстремальной теории графов – области, изучающей наибольшие или наименьшие графы с заданными свойствами, и является частным случаем задачи о запрещенных подграфах, касающейся максимального числа ребер в графе, не содержащем заданный подграф. Пример графа с *n* вершинами, не содержащего клику с *k* вершинами, может быть построен путем разбиения множества из *n* вершин на *k* частей равного или почти равного размера и соединения двух вершин ребром, если они принадлежат разным частям. Полученный граф называется графом Турана. Теорема Турана утверждает, что граф Турана имеет наибольшее число ребер среди всех графов с *n* вершинами, не содержащих клику с *k+1* вершиной. Теорема Турана и графы Турана, представляющие ее экстремальный случай, были впервые описаны и исследованы венгерским математиком Палом Тураном в 1941 году. Частный случай теоремы для графов, не содержащих треугольники, известен как теорема Мантеля; она была сформулирована в 1907 году голландским математиком Виллемом Мантелем.

Заявление

Теорема Турана утверждает, что любой граф с вершинами, не содержащий в качестве подграфа, имеет не более краев, чем граф Турана. Для фиксированного значения , этот граф имеет краев, используя малую о-нотацию. Интуитивно это означает, что с ростом , доля краев, содержащихся в , приближается к . Многие из последующих доказательств дают только верхнюю оценку .

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

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

Максимальная вершина

Это доказательство принадлежит Полу Эрдошу. Выберем вершину с наибольшей степенью. Рассмотрим множество вершин, не смежных с , и множество вершин, смежных с . Теперь удалим все ребра внутри и добавим все ребра между и . Это увеличивает количество ребер, согласно нашему предположению о максимальности, и сохраняет граф -свободным. Теперь -свободен, поэтому тот же аргумент можно повторить для . Повторяя этот аргумент, в конечном итоге получим граф той же формы, что и граф Турана, который представляет собой набор независимых множеств с ребрами между каждой парой вершин из разных независимых множеств. Простое вычисление показывает, что количество ребер в этом графе максимизируется, когда размеры всех независимых множеств максимально близки друг к другу.

Полная многосторонняя оптимизация

Это доказательство, как и доказательство симметризации Зикова, сводится к случаю, когда граф является полным многодольным графом, и показывает, что число ребер максимизируется, когда существуют независимые множества размеров, максимально близких друг к другу. Этот шаг можно выполнить следующим образом: пусть – независимые множества многодольного графа. Поскольку две вершины соединены ребром тогда и только тогда, когда они не принадлежат одному и тому же независимому множеству, число ребер равно

где левая часть получается прямым подсчетом, а правая – с использованием принципа включений-исключений. Чтобы доказать оценку, достаточно применить неравенство Коши — Буняковского — Шварца к слагаемому в правой части, поскольку
Для доказательства оптимальности графа Турана можно утверждать, что разница в размерах любых двух не превышает единицу. В частности, если у нас есть для некоторого , то перемещение одной вершины из в (и соответствующая корректировка ребер) увеличит значение суммы. Это можно увидеть, рассмотрев изменения обеих частей вышеприведенного выражения для числа ребер, или заметив, что степень перемещенной вершины увеличится.

Лагранжский

Это доказательство принадлежит им. Они начинают с рассмотрения свободного графа с вершинами, помеченными , и рассматривают максимизацию функции по всем неотрицательным , сумма которых равна . Эта функция известна как Лагранжиан графа и его ребер. Идея их доказательства заключается в том, что если оба отличны от нуля, а вершины не смежны в графе, то функция линейна относительно . Следовательно, можно заменить либо на , либо на , не уменьшая значение функции. Таким образом, существует точка с не более чем отличными от нуля переменными, в которой функция достигает максимума. Теперь, неравенство Коши — Буняковского — Шварца дает, что максимальное значение не превышает . Подставляя для всех , получаем, что максимальное значение не меньше , что и дает требуемую оценку.

Теорема Мантеля

Специальным случаем теоремы Турана является теорема Мантеля: максимальное число ребер в графе на n вершинах, не содержащем треугольников, равно ⌊n²/4⌋. Иными словами, для получения графа, не содержащего треугольников, необходимо удалить почти половину ребер из полного графа на n вершинах. Усиленная форма теоремы Мантеля утверждает, что любой гамильтонов граф с не менее чем ⌊n²/2⌋ ребрами должен быть либо полным двудольным графом Kₙ/₂, либо он должен быть панциклическим: он не только содержит треугольник, но и должен содержать циклы всех других возможных длин до числа вершин в графе. Другое усиление теоремы Мантеля утверждает, что ребра любого графа на n вершинах могут быть покрыты не более чем ⌊n²/3⌋ кликами, которые являются либо ребрами, либо треугольниками. Как следствие, число пересечений графа (минимальное число кличек, необходимое для покрытия всех его ребер) не превосходит ⌊n²/3⌋.

Другие запрещенные подграфы

Теорема Турана показывает, что наибольшее количество ребер в графе, не содержащем определенный подграф, равно… Теорема Эрдеша — Стоуна определяет количество ребер с точностью до погрешности ε во всех остальных графах: (Эрдеша — Стоуна) Пусть G — граф с хроматическим числом χ. Наибольшее возможное количество ребер в графе, в котором H не появляется в качестве подграфа, равно… где константа зависит только от H. Можно заметить, что граф Турана T(n,r) не может содержать копий H, поэтому граф Турана устанавливает нижнюю границу. Поскольку H имеет хроматическое число χ, теорема Турана является частным случаем, в котором H является полным графом K_χ. Общий вопрос о том, сколько ребер может быть включено в граф без копии некоторого подграфа H, является задачей о запрещенном подграфе.

Максимальное увеличение других количеств

Еще одним естественным расширением теоремы Турана является следующий вопрос: если граф не содержит s, то сколько копий s он может иметь? Теорема Турана является частным случаем, когда на этот вопрос отвечает теорема Зикова: (Теорема Зикова) Граф на вершинах, не содержащий s, и имеющий максимально возможное число s, является графом Турана. Это было впервые показано Зиковым (1949) с использованием симметризации Зикова. Поскольку граф Турана состоит из частей размером около , число s в нем составляет около . В статье Алона и Шихельмана (2016) приводится следующее обобщение, аналогичное обобщению теоремы Турана, данному Эрдосом-Стоуном: (Алон, Шихельман, 2016) Пусть H – граф с хроматическим числом χ. Максимально возможное число копий s в графе, не содержащем копию H, равно. Как и в теореме Эрдоса — Стоуна, граф Турана T достигает требуемого числа копий s.

Регион Эдж-Клике

Теорема Турана утверждает, что если граф имеет плотность гомоморфных отображений ребер строго выше , то он содержит ненулевое количество s. Можно задать гораздо более общий вопрос: если задана плотность ребер графа, что можно сказать о плотности s? Сложность ответа на этот вопрос заключается в том, что для заданной плотности может существовать некоторая граница, недостижимая для какого-либо графа, но приближаемая бесконечной последовательностью графов. Для решения этой проблемы часто рассматриваются взвешенные графы или графоны. В частности, графоны содержат предел любой бесконечной последовательности графов. Для заданной плотности ребер конструкция для достижения наибольшей плотности s выглядит следующим образом: возьмите число вершин, стремящееся к бесконечности. Выберите множество из этих вершин и соедините две вершины тогда и только тогда, когда они принадлежат выбранному множеству. Это дает плотность . Конструкция для достижения наименьшей плотности s выглядит следующим образом: возьмите число вершин, стремящееся к бесконечности. Пусть будет целым числом, таким что. Возьмем -разбиение графа, где все части, кроме единственной наименьшей, имеют одинаковый размер, а размеры частей выбираются таким образом, чтобы общая плотность ребер была равна . При этом граф является -разбиенным и, следовательно, не содержит s. Нижняя граница была доказана Разборовым (2008) для случая треугольников, а позднее была обобщена Рейхером (2016) на все клики. Верхняя граница является следствием теоремы Крускала — Катоны.