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

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

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

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

• The Erdös-Hajnal Conjecture | Open Problem Garden