Теорема о четной цепи

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

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

Нерешенная задача по математике :

Существуют ли графы без циклов (для отличных от , , или ), имеющие ребра?${\displaystyle 2k}$${\displaystyle к}$${\displaystyle 2}$${\displaystyle 3}$${\displaystyle 5}$${\displaystyle \Омега (n^{1+1/k})}$

(еще нерешенные проблемы по математике)

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

Для k, отличных от 2, 3 или 5, неизвестно , существуют ли графы, не имеющие 2 k -цикла, но имеющие Ω( n ^{1 + 1/ k} ) ребер, что соответствует верхней границе Эрдёша. ^[5] Известна только более слабая граница, согласно которой число ребер может быть Ω( n ^{1 + 2/(3 k − 3)} ) для нечетных значений k или Ω( n ^{1 + 2/(3 k − 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},}$

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

${\displaystyle 4\left({\frac {n}{5}}\right)^{6/5}\approx 0.5798n^{6/5}.}$

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

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