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

Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа $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$, для которых гипотеза верна, включают также путь с четырьмя вершинами, голову быка с пятью вершинами и любой граф, который можно получить из этих графов, и кографов с помощью модульного разложения. К 2014, однако, полностью гипотеза доказана не была и остаётся открытой проблемой .

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

Ссылки

• The Open Problem Garden