Теорема Турана - Turáns theorem

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

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

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

Теорема Турана и Графики Турана в крайнем случае, были впервые описаны и изучены Венгерский математик Пал Туран в 1941 г.^[1] В особый случай теоремы для графы без треугольников известен как Теорема Мантеля; это было высказано в 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}}.}$

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

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

Айгнер и Циглер (2018) перечислите пять различных доказательств теоремы Турана.^[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)}$-вершинный подграф дает результат.^[1][3]

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

Доказательство Нога Алон и Джоэл Спенсер, из их книги Вероятностный метод, считает случайная перестановка вершин ${\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})}$. Некоторые алгебраические манипуляции с этим неравенством с помощью Неравенство Коши – Шварца и лемма о рукопожатии доказывает результат.^[3] Видеть Метод условных вероятностей § Теорема Турана для большего.

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

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

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

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

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

Смотрите также

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

Рекомендации

1. Туран, Пол (1941), «Об одной экстремальной задаче теории графов», Matematikai és Fizikai Lapok (на венгерском), 48: 436–452
2. Mantel, W. (1907), "Проблема 28 (Решение Х. Гувентака, В. Мантела, Дж. Тейшейры де Маттеса, Ф. Шу и В. А. Витхоффа)", Wiskundige Opgaven, 10: 60–61
3. Айгнер, Мартин; Циглер, Гюнтер М. (2018), "Глава 41: Теорема Турана о графах", Доказательства из КНИГИ (6-е изд.), Springer-Verlag, стр. 285–289, Дои:10.1007/978-3-662-57265-8_41, ISBN  978-3-662-57265-8
4. Эрдёш, Пал (1970), "Turán Pál gráf tételéről" [К теореме Турана о графах] (PDF), Математикай Лапок (на венгерском), 21: 249–251, МИСТЕР  0307975
5. Моцкин, Т.С.; Штраус, Э. (1965), «Максимумы для графов и новое доказательство теоремы Турана», Канадский математический журнал, 17: 533–540, Дои:10.4153 / CJM-1965-053-6, МИСТЕР  0175813
6. Бонди, Дж. А. (1971), «Панциклические графы I», Журнал комбинаторной теории, Серия B, 11 (1): 80–84, Дои:10.1016/0095-8956(71)90016-5
7. Эрдеш, Пол; Гудман, А.В.; Поза, Луи (1966), «Представление графа множеством пересечений» (PDF), Канадский математический журнал, 18 (1): 106–112, Дои:10.4153 / CJM-1966-014-3, МИСТЕР  0186575