Русская Википедия:Гипотеза Эрдёша — Хайналя
Шаблон:Unsolved Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа <math>H</math> пусть <math>\mathcal{F}_H</math> является семейством графов, не содержащих <math>H</math> в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа <math>\delta_H > 0</math> такая, что графы с <math>n</math> вершинами в <math>\mathcal{F}_H</math> имеют либо клику, либо независимое множество размером <math>\Omega(n^{\delta_H})</math>.
Эквивалентное утверждение исходной гипотезы: для любого графа <math>H</math> не содержащие <math>H</math> графы содержат произвольно большие совершенные порождённые подграфы.
Графы без больших клик или независимых множеств
Для сравнения, у случайных графов в модели Эрдёша — Реньи с вероятностью рёбер 1/2 как наибольшая клика, так и наибольшее независимое множество много меньше — их размер пропорционален логарифму от <math>n</math>, а не растёт полиномиально. Теорема Рамсея доказывает, что никакой граф не имеет одновременно размер наибольшей клики и размера наибольшего независимого множества меньше логарифмическогоШаблон:SfnШаблон:Sfn. Из теоремы Рамсея также следует специальный случай гипотезы Эрдёша — Хайналя, когда сам граф <math>H</math> является кликой или независимым множествомШаблон:Sfn.
Частичные результаты
Гипотеза принадлежит Палу Эрдёшу и Шаблон:Не переведено 5, которые доказали её для случая, когда <math>H</math> является кографом. Они также показали для произвольного графа <math>H</math>, что размер наибольшей клики или независимого множества растёт суперлогарифмично. Более точно, для любого графа <math>H</math> существует константа <math>c</math> такая, что не содержащие <math>H</math> графы с <math>n</math> вершинами имеют клики или независимые множества, содержащие по меньшей мере <math>\exp c\sqrt{\log n}</math> вершинШаблон:Sfn. Графы <math>H</math>, для которых гипотеза верна, включают также путьШаблон:SfnШаблон:Sfn с четырьмя вершинами, голову быкаШаблон:SfnШаблон:Sfn с пятью вершинами и любой граф, который можно получить из этих графов и кографов с помощью модульного разложенияШаблон:SfnШаблон:Sfn. На 2021 год, однако, полностью гипотеза не доказана и остаётся открытой проблемой[1].
Более ранняя формулировка гипотезы, также принадлежащая Эрдёшу и Хайналю, касается частного случая, когда граф <math>H</math> является граф-циклом с 5 вершинамиШаблон:Sfn. Согласно препринту 2021 года, в этом случае гипотеза верна[1]. Не содержащие <math>C_5</math> графы включают совершенные графы, которые обязательно имеют либо клику, либо независимое множество с размером, пропорциональном квадратному корню от числа их вершин. Обратно, любая клика или независимое множество само по себе является совершенным графом. По этой причине удобной и симметричной формулировкой гипотезы Эрдёша — Хайналя служит утверждение, что для любого графа <math>H</math> не содержащие <math>H</math> графы обязательно содержат порождённый совершенный подграф полиномиального размераШаблон:SfnШаблон:Sfn.
Примечания
Литература
Ссылки
