Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа пусть является семейством графов, не содержащих в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа такая, что графы с вершинами в имеют либо клику, либо независимое множество размером .
Эквивалентное утверждение исходной гипотезы: для любого графа не содержащие графы содержат произвольно большие совершенные порождённые подграфы.
Графы без больших клик или независимых множеств Для сравнения, у случайных графов в модели Эрдёша — Реньи с вероятностью рёбер 1/2 как наибольшая клика, так и наибольшее независимое множество много меньше — их размер пропорционален логарифму от , а не растёт полиномиально. Теорема Рамсея доказывает, что никакой граф не имеет одновременно размер наибольшей клики и размера наибольшего независимого множества меньше логарифмического. Из теоремы Рамсея также следует специальный случай гипотезы Эрдёша — Хайналя, когда сам граф является кликой или независимым множеством.
Частичные результаты Гипотеза принадлежит Палу Эрдёшу и , которые доказали её для случая, когда является кографом. Они также показали для произвольного графа , что размер наибольшей клики или независимого множества растёт суперлогарифмично. Более точно, для любого графа существует константа такая, что не содержащие графы с вершинами имеют клики или независимые множества, содержащие по меньшей мере вершин. Графы , для которых гипотеза верна, включают также путь с четырьмя вершинами, голову быка с пятью вершинами и любой граф, который можно получить из этих графов и кографов с помощью модульного разложения. На 2021 год, однако, полностью гипотеза не доказана и остаётся открытой проблемой.
Более ранняя формулировка гипотезы, также принадлежащая Эрдёшу и Хайналю, касается частного случая, когда граф является граф-циклом с 5 вершинами. Согласно препринту 2021 года, в этом случае гипотеза верна. Не содержащие графы включают совершенные графы, которые обязательно имеют либо клику, либо независимое множество с размером, пропорциональном квадратному корню от числа их вершин. Обратно, любая клика или независимое множество само по себе является совершенным графом. По этой причине удобной и симметричной формулировкой гипотезы Эрдёша — Хайналя служит утверждение, что для любого графа не содержащие графы обязательно содержат порождённый совершенный подграф полиномиального размера.
Примечания
Литература
Ссылки The Erdös-Hajnal Conjecture | Open Problem Garden
Категория:Теория графов Категория:Теория Рамсея Категория:Математические гипотезы Категория:Пал Эрдёш