Гипотеза Эрдёша — Хайналя (Inhkmy[g |j;~og — }gwuglx)
Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа пусть является семейством графов, не содержащих в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа такая, что графы с вершинами в имеют либо клику, либо независимое множество размером .
Эквивалентное утверждение исходной гипотезы: для любого графа не содержащие графы содержат произвольно большие совершенные порождённые подграфы.
Графы без больших клик или независимых множеств
[править | править код]Для сравнения, у случайных графов в модели Эрдёша — Реньи с вероятностью рёбер 1/2 как наибольшая клика, так и наибольшее независимое множество много меньше — их размер пропорционален логарифму от , а не растёт полиномиально. Теорема Рамсея доказывает, что никакой граф не имеет одновременно размер наибольшей клики и размера наибольшего независимого множества меньше логарифмического[1][2]. Из теоремы Рамсея также следует специальный случай гипотезы Эрдёша — Хайналя, когда сам граф является кликой или независимым множеством[1].
Частичные результаты
[править | править код]Гипотеза принадлежит Палу Эрдёшу и Андрашу Хайналю[англ.], которые доказали её для случая, когда является кографом. Они также показали для произвольного графа , что размер наибольшей клики или независимого множества растёт суперлогарифмично. Более точно, для любого графа существует константа такая, что не содержащие графы с вершинами имеют клики или независимые множества, содержащие по меньшей мере вершин[1]. Графы , для которых гипотеза верна, включают также путь[1][3] с четырьмя вершинами, голову быка[1][4] с пятью вершинами и любой граф, который можно получить из этих графов и кографов с помощью модульного разложения[1][2]. На 2021 год, однако, полностью гипотеза не доказана и остаётся открытой проблемой[5].
Более ранняя формулировка гипотезы, также принадлежащая Эрдёшу и Хайналю, касается частного случая, когда граф является граф-циклом с 5 вершинами[3]. Согласно препринту 2021 года, в этом случае гипотеза верна[5]. Не содержащие графы включают совершенные графы, которые обязательно имеют либо клику, либо независимое множество с размером, пропорциональном квадратному корню от числа их вершин. Обратно, любая клика или независимое множество само по себе является совершенным графом. По этой причине удобной и симметричной формулировкой гипотезы Эрдёша — Хайналя служит утверждение, что для любого графа не содержащие графы обязательно содержат порождённый совершенный подграф полиномиального размера[1][6].
Примечания
[править | править код]- ↑ 1 2 3 4 5 6 7 Erdős, Hajnal, 1989, с. 37–52.
- ↑ 1 2 Alon, Pach, Solymosi, 2001, с. 155–170.
- ↑ 1 2 Gyárfás, 1997, с. 93–98.
- ↑ Chudnovsky, Safra, 2008, с. 1301–1310.
- ↑ 1 2 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