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

Не путать с методом Турана в аналитической теории чисел.

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

Пример $n$- граф вершин , не содержащий ни одного $(r+1)$-вершинный щелчок $K_{r+1}$ может быть сформирован путем разделения множества $n$ вершины в $r$ части одинакового или почти равного размера и соединяющие две вершины ребром, если они принадлежат двум разным частям. Полученный граф является графом Турана. $T(n,r)$. Теорема Турана утверждает, что граф Турана имеет наибольшее количество ребер среди всех K _{r +1} -вершинами , свободными от графов с n .

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

Заявление

Теорема Турана утверждает, что каждый граф $G$ с $n$ вершины, не содержащие $K_{r+1}$ поскольку подграф имеет не более такого же количества ребер, как граф Турана $T(n,r)$. За фиксированную стоимость $r$, этот график имеет $$\left(1-{\frac {1}{r}}+o(1)\right){\frac {n^{2}}{2}}$$ребра, используя обозначение Little-O . Интуитивно это означает, что, как $n$ становится больше, доля ребер, входящих в $T(n,r)$ становится все ближе и ближе к $1-{\frac {1}{r}}$. Многие из следующих доказательств дают только верхнюю оценку $\left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}$.

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

Айгнер и Циглер (2018) перечисляют пять различных доказательств теоремы Турана. Многие доказательства сводятся к случаю, когда граф является полным многодольным графом , и показывают, что число ребер максимально, когда существуют $r$ части по размерам как можно ближе к равным.

Индукция

(Индукция по n) Пример множеств $A$ и $B$ для $r=3$.

(Вершина максимальной степени) Удаление ребер внутри $A$ и рисуем края между $A$ и $B$.

Это было оригинальное доказательство Турана. Возьмите $K_{r+1}$-бесплатный график на $n$ вершины с максимальным числом ребер. Найдите $K_{r}$ (существующее по максимальности) и разобьем вершины на множество $A$ принадлежащий $r$ вершины в $K_{r}$ и набор $B$ принадлежащий $n-r$ другие вершины.

Теперь можно связать ребра выше следующим образом:

• Есть точно ${\binom {r}{2}}$ края внутри $A$.
• Есть максимум $(r-1)|B|=(r-1)(n-r)$ края между $A$ и $B$, поскольку ни одна вершина в $B$ можно подключиться ко всем $A$.
• Количество ребер внутри $B$ не более чем число ребер $T(n-r,r)$ по индуктивной гипотезе.

Добавление этих границ дает результат.

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

Это доказательство принадлежит Полу Эрдешу . Возьмите вершину $v$ наибольшей степени. Рассмотрим набор $A$ вершин, не смежных с $v$ и набор $B$ вершин, смежных с $v$.

Теперь удалите все края внутри $A$ и нарисуйте все края между $A$ и $B$. Это увеличивает количество ребер в соответствии с нашим предположением о максимальности и сохраняет граф $K_{r+1}$-бесплатно. Сейчас, $B$ является $K_{r}$-free, поэтому тот же аргумент можно повторить $B$.

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

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

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

Позволять $S_{1},S_{2},\ldots ,S_{r}$ — независимые множества многодольного графа. Поскольку две вершины имеют ребро между собой тогда и только тогда, когда они не находятся в одном независимом множестве, количество ребер равно

$$\sum _{i\neq j}\left|S_{i}\right|\left|S_{j}\right|={\frac {1}{2}}\left(n^{2}-\sum _{i}\left|S_{i}\right|^{2}\right),$$

где левая часть следует из прямого счета, а правая часть следует из дополнительного счета. Чтобы показать $\left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}$ оценить, применив неравенство Коши–Шварца к ${\textstyle \sum \limits _{i}\left|S_{i}\right|^{2}}$ члена в правой части достаточно, так как ${\textstyle \sum \limits _{i}\left|S_{i}\right|=n}$.

Чтобы доказать оптимальность графа Турана, можно утверждать, что не существует двух $S_{i}$ отличаются по размеру более чем на единицу. В частности, предположив, что мы имеем $\left|S_{i}\right|\geq \left|S_{j}\right|+2$ для некоторых $i\neq j$, перемещая одну вершину из $S_{j}$ к $S_{i}$ (и соответствующая корректировка ребер) увеличит значение суммы. В этом можно убедиться, изучив изменения по обе стороны приведенного выше выражения для количества ребер или заметив, что степень перемещенной вершины увеличивается.

лагранжиан

Это доказательство принадлежит Моцкину и Штраусу (1965) . Они начинают с рассмотрения $K_{r+1}$ свободный граф с помеченными вершинами $1,2,\ldots ,n$, и учитывая максимизацию функции $$f(x_{1},x_{2},\ldots ,x_{n})=\sum _{i,j\ {\text{adjacent}}}x_{i}x_{j}$$над всеми неотрицательными $x_{1},x_{2},\ldots ,x_{n}$ с суммой $1$. Эта функция известна как лагранжиан графа и его ребер.

Идея их доказательства состоит в том, что если $x_{i},x_{j}$ оба ненулевые, в то время как $i,j$ не являются соседними на графике, функция $$f(x_{1},\ldots ,x_{i}-t,\ldots ,x_{j}+t,\ldots ,x_{n})$$линейна по $t$. Следовательно, можно либо заменить $(x_{i},x_{j})$ с любым $(x_{i}+x_{j},0)$ или $(0,x_{i}+x_{j})$ без уменьшения значения функции. Следовательно, существует точка с не более чем $r$ ненулевые переменные, в которых функция максимизируется.

Теперь неравенство Коши – Шварца дает, что максимальное значение не превосходит ${\frac {1}{2}}\left(1-{\frac {1}{r}}\right)$. Подключение $x_{i}={\frac {1}{n}}$ для всех $i$ дает, что максимальное значение не менее ${\frac {|E|}{n^{2}}}$, давая желаемую границу.

Вероятностный метод

Ключевое утверждение этого доказательства было независимо обнаружено Каро и Вэем. Это доказательство принадлежит Ноге Алону и Джоэлу Спенсеру из их книги «Вероятностный метод» . Доказательство показывает, что каждый граф со степенями $d_{1},d_{2},\ldots ,d_{n}$ имеет независимый набор размеров, по крайней мере $$S={\frac {1}{d_{1}+1}}+{\frac {1}{d_{2}+1}}+\cdots +{\frac {1}{d_{n}+1}}.$$Доказательство пытается найти такое независимое множество следующим образом:

• Рассмотрим случайную перестановку вершин $K_{r+1}$-свободный график
• Выберите каждую вершину, которая не примыкает ни к одной из предшествующих ей вершин.

Вершина степени $d$ входит в это с вероятностью ${\frac {1}{d+1}}$, поэтому этот процесс дает в среднем $S$ вершины выбранного множества.

(Симметризация Зыкова) Пример первого шага.

Применение этого факта к графу дополнений и ограничение размера выбранного множества с помощью неравенства Коши – Шварца доказывает теорему Турана. Дополнительную информацию см. в разделе «Метод условных вероятностей» § Теорема Турана .

(Симметризация Зыкова) Пример второго шага.

Zykov Symmetrization

Айгнер и Циглер называют последнее из пяти доказательств «самым прекрасным из всех». Его происхождение неясно, но этот подход часто называют симметризацией Зыкова, поскольку он использовался в доказательстве Зыковым обобщения теоремы Турана. . Это доказательство проводится путем принятия $K_{r+1}$-свободный граф и применяя шаги, чтобы сделать его более похожим на граф Турана, одновременно увеличивая количество ребер.

В частности, учитывая $K_{r+1}$-свободный граф, применяются следующие шаги:

• Если $u,v$ являются несмежными вершинами и $u$ имеет более высокую степень, чем $v$, заменять $v$ с копией $u$. Повторяйте это до тех пор, пока все несмежные вершины не будут иметь одинаковую степень.
• Если $u,v,w$ являются вершинами с $u,v$ и $v,w$ несмежный, но $u,w$ соседние, затем замените оба $u$ и $w$ с копиями $v$.

Все эти шаги сохраняют график $K_{r+1}$ бесплатно при увеличении количества ребер.

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

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

Частный случай теоремы Турана для $r=2$ теорема Мантеля: максимальное количество ребер в $n$-вершинный без треугольников граф $\lfloor n^{2}/4\rfloor .$ Другими словами, необходимо удалить почти половину ребер в $K_{n}$ чтобы получить граф без треугольников.

Усиленная форма теоремы Мантеля утверждает, что любой гамильтонов граф с по крайней мере $n^{2}/4$ ребра должны быть либо полным двудольным графом $K_{n/2,n/2}$ или он должен быть панциклическим : он не только содержит треугольник, но также должен содержать циклы всех других возможных длин, вплоть до количества вершин в графе.

Еще одно усиление теоремы Мантеля гласит, что края каждого $n$-вершинный граф может быть покрыт не более чем $\lfloor n^{2}/4\rfloor$ клики , которые являются либо ребрами, либо треугольниками. графа Как следствие, число пересечений (минимальное количество клик, необходимое для покрытия всех его ребер) не превосходит $\lfloor n^{2}/4\rfloor$.

Обобщения

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

Теорема Турана показывает, что наибольшее число ребер в $K_{r+1}$-свободный граф $\left(1-{\frac {1}{r}}+o(1)\right){\frac {n^{2}}{2}}$. Теорема Эрдеша – Стоуна находит количество ребер до a. $o(n^{2})$ ошибка во всех остальных графиках:

(Эрдёш – Стоун) Предположим, $H$ это граф с хроматическим числом $\chi (H)$. Максимально возможное количество ребер в графе, где $H$ не появляется как подграф $$\left(1-{\frac {1}{\chi (H)-1}}+o(1)\right){\frac {n^{2}}{2}}$$где $o(1)$ константа зависит только от $H$.

Видно, что граф Турана $T(n,\chi (H)-1)$ не может содержать никаких копий $H$, поэтому граф Турана устанавливает нижнюю границу. Как $K_{r+1}$ имеет хроматическое число $r+1$, теорема Турана представляет собой частный случай, когда $H$ это $K_{r+1}$.

Общий вопрос о том, сколько ребер можно включить в граф без копии некоторого $H$ — проблема запрещенного подграфа .

Максимизация других величин

Другим естественным расширением теоремы Турана является следующий вопрос: если в графе нет $K_{r+1}$с, сколько копий $K_{a}$ может ли оно иметь? Теорема Турана — это случай, когда $a=2$. Теорема Зыкова отвечает на этот вопрос:

(Теорема Зыкова) Граф на $n$ вершины без $K_{r+1}$s и максимально возможное количество $K_{a}$s - граф Турана $T(n,r)$

Впервые это было показано Зыковым (1949) с использованием симметризации Зыкова. . Поскольку граф Турана содержит $r$ детали размером около ${\frac {n}{r}}$, количество $K_{a}$это в $T(n,r)$ вокруг ${\binom {r}{a}}\left({\frac {n}{r}}\right)^{a}$. В статье Алона и Шихельмана в 2016 году дается следующее обобщение, похожее на обобщение Эрдоша-Стоуна теоремы Турана:

(Алон-Шихельман, 2016) $H$ быть графом с хроматическим числом $\chi (H)>a$. Максимально возможное количество $K_{a}$s на графике без копии $H$ является $(1+o(1)){\binom {\chi (H)-1}{a}}\left({\frac {n}{\chi (H)-1}}\right)^{a}.$

Как и в случае Эрдеша – Стоуна, граф Турана $T(n,\chi (H)-1)$ достигает желаемого количества копий $K_{a}$.

Регион Edge-Clique

Теорема Турана утверждает, что если граф имеет плотность гомоморфизма ребер строго выше $1-{\frac {1}{r-1}}$, он имеет ненулевое количество $K_{r}$с. Можно задать гораздо более общий вопрос: если вам известна плотность ребер графа, что вы можете сказать о плотности $K_{r}$с?

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

Для заданной плотности краев $d$, строительство крупнейшего $K_{r}$ плотность следующая:

Возьмите несколько вершин $N$ приближается к бесконечности. Выберите набор из ${\sqrt {d}}N$ вершин и соединить две вершины тогда и только тогда, когда они входят в выбранный набор.

Это дает $K_{r}$ плотность $d^{k/2}.$ Конструкция для самых маленьких $K_{r}$ плотность следующая:

Возьмем число вершин, приближающееся к бесконечности. Позволять $t$ быть целым числом таким, что $1-{\frac {1}{t-1}}<d\leq 1-{\frac {1}{t}}$. Возьмите $t$-частичный граф, в котором все части, кроме единственной наименьшей части, имеют одинаковый размер, а размеры частей выбираются так, чтобы общая плотность ребер была равна $d$.

Для $d\leq 1-{\frac {1}{r-1}}$, это дает график, который $(r-1)$-раздельно и, следовательно, не дает $K_{r}$с.

Нижняя оценка была доказана Разборовым (2008). для случая треугольников, а позже был обобщен Райхером (2016) на все клики. . Верхняя оценка является следствием теоремы Краскала–Катона. .

См. также

• Теорема Эрдеша-Стоуна , обобщение теоремы Турана от запрещенных клик до запрещенных графов Турана.