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

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

Утверждение для графов Турана

Экстремальное число 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 независимыми вершинами:

${\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 ); то есть,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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