Теорема о четной схеме - Even circuit theorem

В экстремальная теория графов, то теорема о четной схеме является результатом Пол Эрдёш согласно которому п-вершинный граф, не имеющий простого цикла длины 2k может иметь только О(п^{1 + 1/k}) края. Например, графы без четырех циклов имеют О(п^3/2) рёбер, 6-цикловые графы имеют О(п^4/3) края и т. д.

История

Результат был заявлен без доказательств Эрдёшем в 1964 году.^[1] Бонди и Симоновиц (1974) опубликовал первое доказательство и усилил теорему, чтобы показать, что для п-вершинные графы с Ω(п^{1 + 1/k}) края, все равные длины цикла между 2k и 2кн^1/k происходить.^[2]

Нижние границы

Нерешенная проблема в математике: Есть ли там ${ displaystyle 2k}$-безцикловые графы (для ${ displaystyle k}$ Кроме как ${ displaystyle 2}$, ${ displaystyle 3}$, или же ${ displaystyle 5}$) который имеет ${ Displaystyle Омега (п ^ {1 + 1 / к})}$ края? (больше нерешенных задач по математике)

Оценка теоремы Эрдеша точна с точностью до постоянных множителей для некоторых малых значенийk: за k = 2, 3 или 5, существуют графы с Ω (п^{1 + 1/k}) края, у которых нет 2k-цикл.^[2][3][4]

Неизвестно для k кроме 2, 3 или 5, существуют ли графы, не имеющие 2k-цикл, но есть Ω (п^{1 + 1/k}) ребра, соответствующие верхней границе Эрдеша.^[5] Известна только более слабая оценка, согласно которой количество ребер может бытьΩ (п^{1 + 2/(3k − 3)})для нечетных значений k, или жеΩ (п^{1 + 2/(3k − 4)})для четных значений k.^[4]

Постоянные факторы

Поскольку 4-цикл - это полный двудольный граф максимальное количество ребер в 4-цикличном графе можно рассматривать как частный случай Проблема заранкевича о запрещенных полных двудольных графах, и теорему о четных схемах для этого случая можно рассматривать как частный случай теоремы Кевари – Соша – Турана. Точнее, в этом случае известно, что максимальное количество ребер в графе без 4 циклов равно

${ displaystyle n ^ {3/2} left ({ frac {1} {2}} + o (1) right).}$

Эрдеш и Симоновиц (1982) предположил, что, в общем, максимальное количество ребер в 2k-безциклический граф

${ displaystyle n ^ {1 + 1 / k} left ({ frac {1} {2}} + o (1) right).}$^[6]

Однако более поздние исследователи обнаружили, что существуют графы без 6-циклов и графы без 10-циклов с числом ребер, которое на постоянный коэффициент больше, чем эта предполагаемая оценка, опровергнув гипотезу. Точнее, максимальное количество ребер в 6-цикличном графе лежит между границами

${ displaystyle 0.5338n ^ {4/3} leq operatorname {ex} (n, C_ {6}) leq 0.6272n ^ {4/3},}$

куда бывший(п,грамм) обозначает максимальное количество ребер в п-вершинный граф, не имеющий подграфа, изоморфного грамм.^[3]Максимальное количество ребер в графе без 10 циклов может быть не менее^[4]

${ displaystyle 4 left ({ frac {n} {5}} right) ^ {6/5} приблизительно 0,5798n ^ {6/5}.}$

Наилучшая проверенная верхняя граница количества ребер для 2kбезцикловые графики для произвольных значений k, является

${ displaystyle n ^ {1 + 1 / k} left (k-1 + o (1) right).}$^[5]

Рекомендации