Теорема Эрдёша–Стоуна

Теорема в экстремальной теории графов

В экстремальной теории графов теорема Эрдёша–Стоуна является асимптотическим результатом, обобщающим теорему Турана для ограничения числа рёбер в графе, свободном от H, для неполного графа H. Она названа в честь Пола Эрдёша и Артура Стоуна , которые доказали её в 1946 году ^[1] , и была описана как «фундаментальная теорема экстремальной теории графов». ^[2]

Заявление для графиков Турана

Экстремальное число ex( n ;  H ) определяется как максимальное число ребер в графе с n вершинами, не содержащем подграф, изоморфный H ; см. задачу о запрещенном подграфе для получения дополнительных примеров задач, включающих экстремальное число. Теорема Турана гласит, что ex( n ;  K _r ) =  t _{r  − 1} ( n ), число ребер графа Турана T ( n , r − 1), и что граф Турана является единственным таким экстремальным графом. Теорема Эрдёша–Стоуна распространяет этот результат на H  =  K _r ( t ), полный r -дольный граф с t вершинами в каждом классе, который является графом, полученным путем взятия K _r и замены каждой вершины на t независимых вершин:

${\displaystyle {\mbox{ex}}(n;K_{r}(t))=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}$

Утверждение для произвольных недвудольных графов

Если H — произвольный граф, хроматическое число которого равно r  > 2, то H содержится в K _r ( t ), когда t по крайней мере так же велико, как наибольший цветовой класс в r -раскраске H , но он не содержится в графе Турана T ( n , r  − 1), поскольку этот граф и, следовательно, каждый из его подграфов могут быть раскрашены в r  − 1 цветов. Из этого следует, что экстремальное число для H по крайней мере так же велико, как число ребер в T ( n , r  − 1), и не более чем равно экстремальной функции для K _r ( t ); то есть,

${\displaystyle {\mbox{ex}}(n;H)=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}$

Однако для двудольных графов H теорема не дает строгой границы экстремальной функции. Известно, что когда H двудольный, ex( n ;  H ) =  o ( n ² ), а для общих двудольных графов известно немного больше. Подробнее об экстремальных функциях двудольных графов см. в задаче Заранкевича .

Плотность Турана

Другой способ описания теоремы Эрдёша–Стоуна — использование плотности Турана графа , которая определяется как . Это определяет экстремальное число с точностью до аддитивного члена ошибки. Его также можно представить следующим образом: если задана последовательность графов , каждый из которых не содержит , такая, что число вершин стремится к бесконечности, плотность Турана является максимально возможным пределом их плотностей ребер. Теорема Эрдёша–Стоуна определяет плотность Турана для всех графов, показывая, что любой граф с хроматическим числом имеет плотность Турана ${\displaystyle H}$ ${\displaystyle \pi (H)=\lim _{n\to \infty }{\frac {{\text{ex}}(n;H)}{n \choose 2}}}$ ${\displaystyle {\text{ex}}(n;H)}$ ${\displaystyle o(n^{2})}$ ${\displaystyle G_{1},G_{2},\dots }$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle r>2}$

${\displaystyle \pi (H)={\frac {r-2}{r-1}}.}$

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

Одно доказательство теоремы Эрдёша–Стоуна использует расширение теоремы Ковари–Шоша–Турана на гиперграфы , а также теорему о перенасыщении , создавая соответствующий гиперграф для каждого графа, который является -свободным, и показывая, что гиперграф имеет некоторое ограниченное число рёбер. В теореме Ковари–Шоша–Турана, среди прочего, говорится, что экстремальное число , полного двудольного графа с вершинами в каждой части, не превышает для константы . Это можно распространить на гиперграфы: определив как -дольный -граф с вершинами в каждой части, затем для некоторой константы . ^{[ необходима цитата ]} ${\displaystyle K_{r}(t)}$ ${\displaystyle K_{2}(t)}$ ${\displaystyle t}$ ${\displaystyle {\text{ex}}(K_{2}(t);n)\leq Cn^{2-1/t}}$ ${\displaystyle C}$ ${\displaystyle K_{s,\dots ,s}^{(r)}}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle {\text{ex}}(K_{s,\dots ,s}^{(r)},n)\leq Cn^{r-s^{1-r}}}$ ${\displaystyle C}$

Теперь для заданного графа с , и некоторого графа с вершинами, который не содержит подграфа, изоморфного , мы определяем -граф с теми же вершинами, что и и гиперребром между вершинами в , если они образуют клику в . Обратите внимание, что если содержит копию , то исходный граф содержит копию , так как каждая пара вершин в различных частях должна иметь ребро. Таким образом, не содержит копий , и поэтому имеет гиперребра, что указывает на наличие копий в . Под пересыщением это означает, что плотность ребер находится в пределах плотности Турана , что по теореме Турана ; таким образом, плотность ребер ограничена сверху . ${\displaystyle H=K_{r}(t)}$ ${\displaystyle r>1,s\geq 1}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle H}$ ${\displaystyle r}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle K_{s,\dots ,s}^{(r)}}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle F}$ ${\displaystyle K_{s,\dots ,s}^{(r)}}$ ${\displaystyle o(n^{r})}$ ${\displaystyle o(n^{r})}$ ${\displaystyle K_{r}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle o(1)}$ ${\displaystyle K_{r}}$ ${\displaystyle {\frac {r-2}{r-1}}}$ ${\displaystyle {\frac {r-2}{r-1}}+o(1)}$

С другой стороны, мы можем достичь этой границы, взяв граф Турана , который не содержит копий, но имеет ребра, показав, что это значение является максимальным, и завершив доказательство. ${\displaystyle T(n,r-1)}$ ${\displaystyle K_{r}(t)}$ ${\displaystyle \left({\frac {r-2}{r-1}}-o(1)\right){n \choose 2}}$

Количественные результаты

Было доказано несколько версий теоремы, которые более точно характеризуют связь n , r , t и члена o (1) . Определим обозначение ^[3] s _{r ,ε} ( n ) (для 0 < ε < 1/(2( r  − 1))) как наибольшее t такое, что любой граф порядка n и размера

${\displaystyle \left({\frac {r-2}{2(r-1)}}+\varepsilon \right)n^{2}}$

содержит K _r ( t ).

Эрдёш и Стоун доказали, что

${\displaystyle s_{r,\varepsilon }(n)\geq \left(\underbrace {\log \cdots \log } _{r-1}\,n\right)^{1/2}}$

для достаточно большого n . Правильный порядок s _{r ,ε} ( n ) в терминах n был найден Боллобашем и Эрдёшем: ^[4] для любых заданных r и ε существуют константы c ₁ ( r , ε) и c ₂ ( r , ε) такие, что c ₁ ( r , ε) log  n  <  s _{r ,ε} ( n ) <  c ₂ ( r , ε) log  n . Затем Хватал и Семереди ^[5] определили характер зависимости от r и ε с точностью до константы:

${\displaystyle {\frac {1}{500\log(1/\varepsilon )}}\log n<s_{r,\varepsilon }(n)<{\frac {5}{\log(1/\varepsilon )}}\log n}$для достаточно большого  n .

Примечания

1. Эрдёш, П.; Стоун , А. Х. (1946). «О структуре линейных графов». Бюллетень Американского математического общества . 52 (12): 1087–1091. doi : 10.1090/S0002-9904-1946-08715-7 .
2. Боллобас, Бела (1998). Современная теория графов . Нью-Йорк: Springer-Verlag . стр. 120. ISBN 0-387-98491-7.
3. Боллобас, Бела (1995). «Экстремальная теория графов». В Р.Л.Грэме ; М. Гретшель ; Л. Ловас (ред.). Справочник по комбинаторике . Эльзевир . п. 1244. ИСБН 0-444-88002-X.
4. Боллобаш, Б.; Эрдёш , П. (1973). «О структуре реберных графов». Бюллетень Лондонского математического общества . 5 (3): 317–321. doi :10.1112/blms/5.3.317.
5. Хватал, В .; Семереди, Э. (1981). «О теореме Эрдеша-Стоуна». Журнал Лондонского математического общества . 23 (2): 207–214. doi : 10.1112/jlms/s2-23.2.207.