Теорема Эрдеша – Стоуна - Erdős–Stone theorem - Wikipedia

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

Экстремальные функции графов Турана

Экстремальная функция ex (п; ЧАС) определяется как максимальное количество ребер в графе порядка п не содержащий подграфа, изоморфного ЧАС. Теорема Турана утверждает, что ex (п; K_р) = т_р − 1(п), порядок График Турана, и что граф Турана является единственным экстремальным графом. Теорема Эрдеша – Стоуна распространяет это на графы, не содержащие K_р(т) полный р-дольный граф с т вершин в каждом классе (эквивалентно График Турана Т(rt,р)):

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

Экстремальные функции произвольных недвудольных графов

Если ЧАС - произвольный граф, хроматическое число является р > 2, то ЧАС содержится в K_р(т) в любое время т как минимум такой же большой, как самый большой цветовой класс в р-крашивание ЧАС, но он не содержится в графе Турана Т(п,р - 1) (поскольку каждый подграф этого графа Турана может быть раскрашен р - 1 цвет), откуда следует, что экстремальная функция для ЧАС не меньше, чем количество ребер в Т(п,р - 1) и не более чем равна экстремальной функции при K_р(т); то есть,

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

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

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

Доказано несколько версий теоремы, более точно характеризующих соотношение п, р, т и о(1) срок. Определите обозначение^[3] s_{р, ε}(п) (при 0 <ε <1 / (2 (р - 1))) быть величайшим т такой, что каждый граф порядка п и размер

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

содержит K_р(т).

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

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

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

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

Примечания

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