Теорема о четной схеме

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

История

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

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

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

существуют ли

2k

-бесцикловые графики (для

k

кроме

2

,

3

, или

5

), которые имеют

\Omega (n^{1+1/k})

края?

(еще нерешенные задачи по математике)

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

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

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

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

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

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

n^{1+1/k}\left({\frac {1}{2}}+o(1)\right).

^[6]

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

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

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

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

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

n^{1+1/k}\left(k-1+o(1)\right).

^[5]

Ссылки

^ Эрдеш, П. (1964), «Экстремальные задачи теории графов» (PDF) , Теория графов и ее приложения (Proc. Sympos. Smolenice, 1963) , Publ. Дом Чехословацкой академии. Sci., Прага, стр. 29–36, MR 0180500 .
^ Jump up to: ^а ^б Бонди, JA ; Симоновиц, М. (1974), «Циклы четной длины в графах» (PDF) , Журнал комбинаторной теории , серия B, 16 : 97–105, doi : 10.1016/0095-8956(74)90052-5 , MR 0340095 .
^ Jump up to: ^а ^б Фюреди, Золтан; Наор, Асаф; Верстраете, Жак (2006), «О числе Турана для шестиугольника», Advance in Mathematics , 203 (2): 476–496, doi : 10.1016/j.aim.2005.04.011 , MR 2227729 .
^ Jump up to: ^а ^б ^с Лазебник Ф.; Устименко В.А.; Волдар, AJ (1994), «Свойства некоторых семейств $графов без 2 k$ -циклов», Журнал комбинаторной теории , серия B, 60 (2): 293–298, doi : 10.1006/jctb.1994.1020 , MR 1271276 .
^ Jump up to: ^а ^б Пихурко, Олег (2012), «Заметка о функции Турана четных циклов» (PDF) , Proceedings of the American Mathematical Society , 140 (11): 3687–3692, doi : 10.1090/S0002-9939-2012-11274- 2 , МР 2944709 .
^ Эрдеш, П .; Симоновиц, М. (1982), «Результаты компактности в экстремальной теории графов» (PDF) , Combinatorica , 2 (3): 275–288, doi : 10.1007/BF02579234 , MR 0698653 , заархивировано из оригинала (PDF) в 2016 г. 04.03 , получено 6.11.2015 .

[1] Эрдеш, П. (1964), «Экстремальные задачи теории графов» (PDF) , Теория графов и ее приложения (Proc. Sympos. Smolenice, 1963) , Publ. Дом Чехословацкой академии. Sci., Прага, стр. 29–36, MR 0180500 .

[bs74-2] Jump up to: ^а ^б Бонди, JA ; Симоновиц, М. (1974), «Циклы четной длины в графах» (PDF) , Журнал комбинаторной теории , серия B, 16 : 97–105, doi : 10.1016/0095-8956(74)90052-5 , MR 0340095 .

[fnv06-3] Jump up to: ^а ^б Фюреди, Золтан; Наор, Асаф; Верстраете, Жак (2006), «О числе Турана для шестиугольника», Advance in Mathematics , 203 (2): 476–496, doi : 10.1016/j.aim.2005.04.011 , MR 2227729 .

[luw94-4] Jump up to: ^а ^б ^с Лазебник Ф.; Устименко В.А.; Волдар, AJ (1994), «Свойства некоторых семейств $графов без 2 k$ -циклов», Журнал комбинаторной теории , серия B, 60 (2): 293–298, doi : 10.1006/jctb.1994.1020 , MR 1271276 .

[p12-5] Jump up to: ^а ^б Пихурко, Олег (2012), «Заметка о функции Турана четных циклов» (PDF) , Proceedings of the American Mathematical Society , 140 (11): 3687–3692, doi : 10.1090/S0002-9939-2012-11274- 2 , МР 2944709 .

[6] Эрдеш, П .; Симоновиц, М. (1982), «Результаты компактности в экстремальной теории графов» (PDF) , Combinatorica , 2 (3): 275–288, doi : 10.1007/BF02579234 , MR 0698653 , заархивировано из оригинала (PDF) в 2016 г. 04.03 , получено 6.11.2015 .

[1]

[2]

[3]

[4]

[5]

[6]