Гипотеза Эрдёша — Хайналя
Шаблон:Unsolved Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа пусть является семейством графов, не содержащих в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа такая, что графы с вершинами в имеют либо клику, либо независимое множество размером .
Эквивалентное утверждение исходной гипотезы: для любого графа не содержащие графы содержат произвольно большие совершенные порождённые подграфы.
Графы без больших клик или независимых множеств
Для сравнения, у случайных графов в модели Эрдёша — Реньи с вероятностью рёбер 1/2 как наибольшая клика, так и наибольшее независимое множество много меньше — их размер пропорционален логарифму от , а не растёт полиномиально. Теорема Рамсея доказывает, что никакой граф не имеет одновременно размер наибольшей клики и размера наибольшего независимого множества меньше логарифмическогоШаблон:SfnШаблон:Sfn. Из теоремы Рамсея также следует специальный случай гипотезы Эрдёша — Хайналя, когда сам граф является кликой или независимым множествомШаблон:Sfn.
Частичные результаты
Гипотеза принадлежит Палу Эрдёшу и Шаблон:Не переведено 5, которые доказали её для случая, когда является кографом. Они также показали для произвольного графа , что размер наибольшей клики или независимого множества растёт суперлогарифмично. Более точно, для любого графа существует константа такая, что не содержащие графы с вершинами имеют клики или независимые множества, содержащие по меньшей мере вершинШаблон:Sfn. Графы , для которых гипотеза верна, включают также путьШаблон:SfnШаблон:Sfn с четырьмя вершинами, голову быкаШаблон:SfnШаблон:Sfn с пятью вершинами и любой граф, который можно получить из этих графов и кографов с помощью модульного разложенияШаблон:SfnШаблон:Sfn. На 2021 год, однако, полностью гипотеза не доказана и остаётся открытой проблемой[1].
Более ранняя формулировка гипотезы, также принадлежащая Эрдёшу и Хайналю, касается частного случая, когда граф является граф-циклом с 5 вершинамиШаблон:Sfn. Согласно препринту 2021 года, в этом случае гипотеза верна[1]. Не содержащие графы включают совершенные графы, которые обязательно имеют либо клику, либо независимое множество с размером, пропорциональном квадратному корню от числа их вершин. Обратно, любая клика или независимое множество само по себе является совершенным графом. По этой причине удобной и симметричной формулировкой гипотезы Эрдёша — Хайналя служит утверждение, что для любого графа не содержащие графы обязательно содержат порождённый совершенный подграф полиномиального размераШаблон:SfnШаблон:Sfn.