Гипотеза Эрдёша — Хайналя

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

Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа $H$ пусть ${\mathcal {F}}_{H}$ является семейством графов, не содержащих $H$ в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа $\delta _{H}>0$ такая, что графы с $n$ вершинами в ${\mathcal {F}}_{H}$ имеют либо клику, либо независимое множество размером $\Omega (n^{\delta _{H}})$.

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

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

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

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

Гипотеза принадлежит Палу Эрдёшу и Андрашу Хайналю, которые доказали её для случая, когда $H$ является кографом. Они также показали для произвольного графа $H$, что размер наибольшей клики или независимого множества растёт суперлогарифмично. Более точно, для любого графа $H$ существует константа $c$ такая, что не содержащие $H$ графы с $n$ вершинами имеют клики или независимые множества, содержащие по меньшей мере $\exp c{\sqrt {\log n}}$ вершин. Графы $H$, для которых гипотеза верна, включают также путь с четырьмя вершинами, голову быка с пятью вершинами и любой граф, который можно получить из этих графов и кографов с помощью модульного разложения. На 2021 год, однако, полностью гипотеза не доказана и остаётся открытой проблемой.

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

Ссылки

• The Erdös-Hajnal Conjecture | Open Problem Garden Архивная копия от 22 декабря 2017 на Wayback Machine