Нерешённые проблемы математики: Верно ли, что графы с фиксированным запрещённым порождённым подграфом обязательно имеют большие клики или большие независимые множества?

Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа пусть является семейством графов, не содержащих в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа такая, что графы с вершинами в имеют либо клику, либо независимое множество размером .

Эквивалентное утверждение исходной гипотезы: для любого графа не содержащие графы содержат произвольно большие совершенные порождённые подграфы.

Графы без больших клик или независимых множеств

править

Для сравнения, у случайных графов в модели Эрдёша — Реньи с вероятностью рёбер 1/2 как наибольшая клика, так и наибольшее независимое множество много меньше — их размер пропорционален логарифму от  , а не растёт полиномиально. Теорема Рамсея доказывает, что никакой граф не имеет одновременно размер наибольшей клики и размера наибольшего независимого множества меньше логарифмического[1][2]. Из теоремы Рамсея также следует специальный случай гипотезы Эрдёша — Хайналя, когда сам граф   является кликой или независимым множеством[1].

Частичные результаты

править

Гипотеза принадлежит Палу Эрдёшу и Андрашу Хайналю[англ.], которые доказали её для случая, когда   является кографом. Они также показали для произвольного графа  , что размер наибольшей клики или независимого множества растёт суперлогарифмично. Более точно, для любого графа   существует константа   такая, что не содержащие   графы с   вершинами имеют клики или независимые множества, содержащие по меньшей мере   вершин[1]. Графы  , для которых гипотеза верна, включают также путь[1][3] с четырьмя вершинами, голову быка[1][4] с пятью вершинами и любой граф, который можно получить из этих графов и кографов с помощью модульного разложения[1][2]. На 2021 год, однако, полностью гипотеза не доказана и остаётся открытой проблемой[5].

Более ранняя формулировка гипотезы, также принадлежащая Эрдёшу и Хайналю, касается частного случая, когда граф   является граф-циклом с 5 вершинами[3]. Согласно препринту 2021 года, в этом случае гипотеза верна[5]. Не содержащие   графы включают совершенные графы, которые обязательно имеют либо клику, либо независимое множество с размером, пропорциональном квадратному корню от числа их вершин. Обратно, любая клика или независимое множество само по себе является совершенным графом. По этой причине удобной и симметричной формулировкой гипотезы Эрдёша — Хайналя служит утверждение, что для любого графа   не содержащие   графы обязательно содержат порождённый совершенный подграф полиномиального размера[1][6].

Примечания

править
  1. 1 2 3 4 5 6 7 Erdős, Hajnal, 1989, с. 37–52.
  2. 1 2 Alon, Pach, Solymosi, 2001, с. 155–170.
  3. 1 2 Gyárfás, 1997, с. 93–98.
  4. Chudnovsky, Safra, 2008, с. 1301–1310.
  5. 1 2 Steve Nadis. New Proof Reveals That Graphs With No Pentagons Are Fundamentally Different. Quanta (26 апреля 2021). Дата обращения: 26 апреля 2021. Архивировано 26 апреля 2021 года.
  6. 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.

Ссылки

править