WikiSort.ru - Не сортированное

Нерешённые проблемы математики: Графы с фиксированным запрещённым порождённым подграфом обязательно имеют большие клики или большие независимые множества?

Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа ${\displaystyle H}$ пусть ${\displaystyle {\mathcal {F}}_{H}}$ является семейством графов, не содержащих ${\displaystyle H}$ в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа ${\displaystyle \delta _{H}>0}$ , такая, что графы с ${\displaystyle n}$ вершинами в ${\displaystyle {\mathcal {F}}_{H}}$ имеют либо клику или независимое множество размером ${\displaystyle \Omega (n^{\delta _{H}})}$ .

Эквивалентное утверждение исходной гипотезы: для любого графа ${\displaystyle H}$ свободные от ${\displaystyle H}$ графы содержат произвольно большие совершенные порождённые подграфы.

Графы без больших клик или назависимых множеств

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

Частичные результаты

Гипотеза принадлежит Палу Эрдёшу и Андрашу Хайналю^[en], которые доказали её для случая, когда ${\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] с пятью вершинами и любой граф, который можно получить из этих графов, и кографов с помощью модульного разложения^[en][1][2]. К 2014, однако, полностью гипотеза доказана не была и остаётся открытой проблемой^[1][5].

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

Примечания

Литература

Ссылки

• The Open Problem Garden

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.