В экстремальной теории графов , то Эрдеш-Стоун теорема является асимптотическим результатом обобщающего теоремы Турана к связанному числу ребер в Н свободном от графика для неполного графа H . Она названа в честь Пола Эрдеша и Артура Стоуна , которые доказали ее в 1946 году [1], и была описана как «фундаментальная теорема экстремальной теории графов». [2]
Экстремальные функции графов Турана
Экстремальная функция ех ( п ; Н ) определяется как максимальное число ребер в графе порядка п , не содержащий подграф , изоморфный H . Теорема Турана гласит, что ex ( n ; K r ) = t r - 1 ( n ), порядок графа Турана , и что граф Турана является единственным экстремальным графом. Теорема Эрдеша – Стоуна распространяет это на графы, не содержащие K r ( t ), полный r -раздельный граф с t вершинами в каждом классе (эквивалентно графу Турана T ( rt , r )):
Экстремальные функции произвольных недвудольных графов
Если H - произвольный граф, хроматическое число которого r > 2, то H содержится в K r ( t ) всякий раз, когда t не меньше самого большого цветового класса в r- раскраске H , но не содержится в граф Турана T ( n , r - 1) (поскольку каждый подграф этого графа Турана может быть раскрашен в r - 1 цвет). Отсюда следует, что экстремальная функция для H не меньше, чем количество ребер в T ( n , r - 1), и не более чем равна экстремальной функции для K r ( t ); это,
Однако для двудольных графов H теорема не дает точной оценки экстремальной функции. Известно, что для двудольных графов H ex ( n ; H ) = o ( n 2 ), а для общих двудольных графов известно немногое. Подробнее об экстремальных функциях двудольных графов см. В задаче Заранкевича .
Количественные результаты
Было доказано несколько версий теоремы, более точно характеризующих соотношение n , r , t и члена o (1) . Определим обозначение [3] s r , ε ( n ) (для 0 <ε <1 / (2 ( r - 1))) как наибольшее t такое, что каждый граф порядка n и размера
содержит K r ( t ).
Эрдеш и Стоун доказали, что
для достаточно большого n . Правильный порядок s r , ε ( n ) в терминах n был найден Боллобашем и Эрдешем: [4] для любых заданных r и ε существуют константы c 1 ( r , ε) и c 2 ( r , ε), такие как что c 1 ( r , ε) log n < s r , ε ( n ) < c 2 ( r , ε) log n . Затем Хватал и Семереди [5] определили характер зависимости от r и ε с точностью до константы:
- для достаточно больших n .
Заметки
- ^ Erdős, П .; Стоун, AH (1946). «О структуре линейных графов» . Бюллетень Американского математического общества . 52 (12): 1087–1091. DOI : 10.1090 / S0002-9904-1946-08715-7 .
- ^ Боллобаш, Бела (1998). Современная теория графов . Нью-Йорк: Springer-Verlag . С. 120 . ISBN 0-387-98491-7.
- ^ Боллобаш, Бела (1995). «Экстремальная теория графов». В Р.Л. Грэхеме ; М. Грётчель ; Л. Ловас (ред.). Справочник по комбинаторике . Эльзевир . п. 1244. ISBN 0-444-88002-X.
- ^ Боллобаш, Б .; Эрдеш, П. (1973). «О структуре реберных графов». Бюллетень Лондонского математического общества . 5 (3): 317–321. DOI : 10.1112 / БЛМ / 5.3.317 .
- ^ Chvátal, V .; Семереди, Э. (1981). «О теореме Эрдеша-Стоуна». Журнал Лондонского математического общества . 23 (2): 207–214. DOI : 10,1112 / jlms / s2-23.2.207 .