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

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

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

Теорему Турана, и графики ТУРАН давая ее крайний случай, впервые были описаны и изучены венгерский математик Пал Туран в 1941 году ^[1] частный случай теоремы для треугольника свободных графов известен как теорема Mantel в ; это было высказано в 1907 году голландским математиком Виллемом Мантелом. ^[2]

Заявление [ править ]

Теорема Турана утверждает, что каждый граф с вершинами, который не содержит в качестве подграфа, имеет количество ребер, не более${\displaystyle G}$${\displaystyle n}$${\displaystyle K_{r+1}}$

${\displaystyle {\frac {r-1}{r}}\cdot {\frac {n^{2}}{2}}=\left(1-{\frac {1}{r}}\right)\cdot {\frac {n^{2}}{2}}.}$

Та же формула дает количество ребер в графе Турана , поэтому она эквивалентна формулировке теоремы Турана в форме, которая среди простых графов с -вершинами без -клик имеет максимальное количество ребер. ^[3]${\displaystyle T(n,r)}$${\displaystyle n}$${\displaystyle (r+1)}$${\displaystyle T(n,r)}$

Доказательства [ править ]

Айгнер и Зиглер (2018) перечисляют пять различных доказательств теоремы Турана. ^[3]

Оригинальное доказательство Турана использует индукцию по количеству вершин. Для данного графа без -вершинников с более чем вершинами и максимальным числом ребер доказательство находит клику (которая должна существовать по максимальности), удаляет ее и применяет индукцию к оставшемуся -вершинному подграфу. Каждая вершина оставшегося подграфа может быть смежной не более чем с вершинами клики, и суммирование числа ребер, полученных таким образом, с индуктивным числом ребер в подграфе -вершине дает результат. ^{[1] [3]}${\displaystyle n}$${\displaystyle K_{r+1}}$${\displaystyle r}$${\displaystyle K_{r}}$${\displaystyle (n-r)}$${\displaystyle r-1}$${\displaystyle (n-r)(r-1)}$${\displaystyle (n-r)}$

Другое доказательство Пола Эрдеша находит вершину максимальной степени из -свободного графа и использует ее для построения нового графа на том же наборе вершин, удаляя ребра между любой парой несоседей и добавляя ребра между всеми парами соседа. и не сосед. Новый граф остается -свободным и имеет по крайней мере столько же ребер. Рекурсивное повторение той же конструкции на подграфе соседей в конечном итоге дает граф в той же форме, что и граф Турана (набор независимых множеств, с ребрами между каждыми двумя вершинами из разных независимых множеств), и простое вычисление показывает, что количество рёбра этого графа максимизируются, когда размеры всех независимых множеств максимально близки к равным. ^[3]${\displaystyle v}$${\displaystyle K_{r+1}}$${\displaystyle v}$${\displaystyle K_{r+1}}$${\displaystyle v}$${\displaystyle p}$^[4]

Моцкин и Страус (1965) доказывают теорему Турана, используя вероятностный метод , ища дискретное распределение вероятностей на вершинах данного -свободного графа, которое максимизирует ожидаемое количество ребер в случайно выбранном индуцированном подграфе , причем каждая вершина включена в подграф. независимо с заданной вероятностью. Для распределения с вероятностью для вершины это ожидаемое число равно . Любое такое распределение может быть изменено путем многократного сдвига вероятности между парами несмежных вершин, чтобы ожидаемое значение не уменьшалось, а единственные вершины с ненулевой вероятностью принадлежали клике, из чего следует, что максимальное ожидаемое значение равно наиболее${\displaystyle K_{r+1}}$${\displaystyle p_{i}}$${\displaystyle v_{i}}$${\displaystyle \textstyle \sum _{(v_{i},v_{j})\in E(G)}p_{i}p_{j}}$${\displaystyle (r-1)/2r}$. Следовательно, ожидаемое значение для равномерного распределения, которое в точности равно количеству ребер, разделенных на , также не больше , а само количество ребер не больше . ^{[3] [5]}${\displaystyle 1/n^{2}}$${\displaystyle (r-1)/2r}$${\displaystyle n^{2}(r-1)/2r}$

Доказательство Ноги Алон и Джоэла Спенсера из их книги «Вероятностный метод» рассматривает случайную перестановку вершин -свободного графа и наибольшую клику, образованную префиксом этой перестановки. Вычисляя вероятность того, что любая данная вершина будет включена, как функцию ее степени, можно показать, что ожидаемый размер этой клики равен , где - степень вершины . Должна существовать клика хотя бы такого размера, значит . Некоторые алгебраические манипуляции с этим неравенством с использованием неравенства Коши – Шварца и леммы о подтверждении связи доказывают результат. ^[3] См.${\displaystyle K_{r+1}}$${\displaystyle \textstyle \sum 1/(n-d_{i})}$${\displaystyle d_{i}}$${\displaystyle v_{i}}$${\displaystyle \textstyle r\geq \sum 1/(n-d_{i})}$Метод условных вероятностей § Теорема Турана подробнее.

Айгнер и Зиглер называют последнее из пяти доказательств «самым прекрасным из всех»; его происхождение неясно. Он основан на лемме о том, что для максимально- свободного графа несмежность является транзитивным отношением , так как если бы противное и были несмежными и были смежными, можно было бы построить -свободный граф с большим количеством ребер, удалив одно или две из этих трех вершин и заменяя их копиями одной из оставшихся вершин. Поскольку несмежность также является симметричной и рефлексивной (никакая вершина не смежна сама с собой), она образует отношение эквивалентности, классы эквивалентности которого${\displaystyle K_{r+1}}$${\displaystyle (u,v)}$${\displaystyle (v,w)}$${\displaystyle (u,w)}$${\displaystyle K_{r+1}}$придают любому максимальному графу ту же форму, что и граф Турана. Как и во втором доказательстве, простой расчет показывает, что количество ребер максимизируется, когда размеры всех независимых множеств максимально близки к равным. ^[3]

Теорема Мантеля [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]