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

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

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

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

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

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

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

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

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

СсылкиПравить

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