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

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

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

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

${\ displaystyle {\ mbox {ex}} (n; K_ {r} (t)) = \ left ({\ frac {r-2} {r-1}} + o (1) \ right) {n \ выберите 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 \ select 2}.}$

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

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

Было доказано несколько версий теоремы, более точно характеризующих соотношение n , r , t и члена o (1) . Определим обозначение 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 был найден Боллобашем и Эрдешем: для любых данных r и ε существуют константы c ₁ ( r , ε) и c ₂ ( r , ε) такие, что c ₁ ( r , ε) журнал  n  <  s _{r , ε} ( n ) <  c ₂ ( r , ε) журнал  n . Затем Хватал и Семереди определили характер зависимости от r и ε с точностью до константы:

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

Примечания