Гипотеза Эрдёша — Хайналя
Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа [math]\displaystyle{ H }[/math] пусть [math]\displaystyle{ \mathcal{F}_H }[/math] является семейством графов, не содержащих [math]\displaystyle{ H }[/math] в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа [math]\displaystyle{ \delta_H \gt 0 }[/math] такая, что графы с [math]\displaystyle{ n }[/math] вершинами в [math]\displaystyle{ \mathcal{F}_H }[/math] имеют либо клику, либо независимое множество размером [math]\displaystyle{ \Omega(n^{\delta_H}) }[/math].
Эквивалентное утверждение исходной гипотезы: для любого графа [math]\displaystyle{ H }[/math] не содержащие [math]\displaystyle{ H }[/math] графы содержат произвольно большие совершенные порождённые подграфы.
Графы без больших клик или независимых множеств
Для сравнения, у случайных графов в модели Эрдёша — Реньи с вероятностью рёбер 1/2 как наибольшая клика, так и наибольшее независимое множество много меньше — их размер пропорционален логарифму от [math]\displaystyle{ n }[/math], а не растёт полиномиально. Теорема Рамсея доказывает, что никакой граф не имеет одновременно размер наибольшей клики и размера наибольшего независимого множества меньше логарифмического[1][2]. Из теоремы Рамсея также следует специальный случай гипотезы Эрдёша — Хайналя, когда сам граф [math]\displaystyle{ H }[/math] является кликой или независимым множеством[1].
Частичные результаты
Гипотеза принадлежит Палу Эрдёшу и Андрашу Хайналю, которые доказали её для случая, когда [math]\displaystyle{ H }[/math] является кографом. Они также показали для произвольного графа [math]\displaystyle{ H }[/math], что размер наибольшей клики или независимого множества растёт суперлогарифмично. Более точно, для любого графа [math]\displaystyle{ H }[/math] существует константа [math]\displaystyle{ c }[/math] такая, что не содержащие [math]\displaystyle{ H }[/math] графы с [math]\displaystyle{ n }[/math] вершинами имеют клики или независимые множества, содержащие по меньшей мере [math]\displaystyle{ \exp c\sqrt{\log n} }[/math] вершин[1]. Графы [math]\displaystyle{ H }[/math], для которых гипотеза верна, включают также путь[1][3] с четырьмя вершинами, голову быка[1][4] с пятью вершинами и любой граф, который можно получить из этих графов и кографов с помощью модульного разложения[1][2]. На 2021 год, однако, полностью гипотеза не доказана и остаётся открытой проблемой[5].
Более ранняя формулировка гипотезы, также принадлежащая Эрдёшу и Хайналю, касается частного случая, когда граф [math]\displaystyle{ H }[/math] является граф-циклом с 5 вершинами[3]. Согласно препринту 2021 года, в этом случае гипотеза верна[5]. Не содержащие [math]\displaystyle{ C_5 }[/math] графы включают совершенные графы, которые обязательно имеют либо клику, либо независимое множество с размером, пропорциональном квадратному корню от числа их вершин. Обратно, любая клика или независимое множество само по себе является совершенным графом. По этой причине удобной и симметричной формулировкой гипотезы Эрдёша — Хайналя служит утверждение, что для любого графа [math]\displaystyle{ H }[/math] не содержащие [math]\displaystyle{ H }[/math] графы обязательно содержат порождённый совершенный подграф полиномиального размера[1][6].
Примечания
- ↑ 1,0 1,1 1,2 1,3 1,4 1,5 1,6 Erdős, Hajnal, 1989, с. 37–52.
- ↑ 2,0 2,1 Alon, Pach, Solymosi, 2001, с. 155–170.
- ↑ 3,0 3,1 Gyárfás, 1997, с. 93–98.
- ↑ Chudnovsky, Safra, 2008, с. 1301–1310.
- ↑ 5,0 5,1 Steve Nadis. New Proof Reveals That Graphs With No Pentagons Are Fundamentally Different. Quanta (26 апреля 2021). Дата обращения: 26 апреля 2021. Архивировано 26 апреля 2021 года.
- ↑ Chudnovsky, 2014, с. 178–179.
Литература
- Erdős P., Hajnal A. Ramsey-type theorems // Discrete Applied Mathematics. — 1989. — Т. 25, вып. 1—2. — С. 37–52. — doi:10.1016/0166-218X(89)90045-0.
- András Gyárfás. Reflections on a problem of Erdős and Hajnal // The mathematics of Paul Erdős, II. — Springer, Berlin, 1997. — Т. 14. — С. 93–98. — (Algorithms Combin.). — doi:10.1007/978-3-642-60406-5_10.
- Maria Chudnovsky, Shmuel Safra. The Erdős-Hajnal conjecture for bull-free graphs // Journal of Combinatorial Theory. — 2008. — Т. 98, вып. 6. — С. 1301–1310. — doi:10.1016/j.jctb.2008.02.005.
- Noga Alon, János Pach, József Solymosi. Ramsey-type theorems with forbidden subgraphs // Combinatorica. — 2001. — Т. 21, вып. 2. — С. 155–170. — doi:10.1007/s004930100016.
- Maria Chudnovsky. The Erdös–Hajnal conjecture—a survey // Journal of Graph Theory. — 2014. — Т. 75, вып. 2. — С. 178–190. — doi:10.1002/jgt.21730. — arXiv:1606.08827.
Ссылки
- The Erdös-Hajnal Conjecture | Open Problem Garden Архивная копия от 22 декабря 2017 на Wayback Machine