Гипотеза Эрдёша — Фабера — Ловаса

Случай гипотезы Эрдёша — Фаюера — Ловеса — граф, образованный из клик, в каждом, по четыре вершины в каждой, любые две из которых пересекаются в одной вершине, может быть раскрашен в три цвета.

Гипотеза Эрдёша — Фабера — Ловаса — это проблема о раскраске графов, названная именами Пала Эрдёша, Ванса Фабера и Ласло Ловаса, которые сформулировали её в 1972 году. Гипотеза гласит:

Если k полных графов, каждый из которых имеет в точности k вершин, обладают свойством, что любая пара полных графов имеет не более одной общей вершины, то объединение графов может раскрашено в k цветов.

В 2021 году был опубликован препринт с доказательством гипотезы для больших k.

Эквивалентные формулировки

Аддад и Тардиф представили задачу с историей о создании комитета — представим, что в университетском факультете имеется k комитетов, каждый состоящий из k членов, и все комитеты используют ту же комнату, имеющую k кресел. Предположим, что имеется не более одного человека, входящего в любые два комитета. Можно ли назначить каждому члену комитета кресло таким образом, что каждый член сидит на одном и том же кресле во всех комитетах? В этой модели задачи члены комитетов соответствуют вершинам графа, комитеты соответствуют полным графам, а кресла соответствуют цветам.

Линейный гиперграф (известный также как частично линейное пространство), это гиперграф, имеющей свойство, что любые два гиперребра имеют не более одной вершины. Говорят, что гиперграф является однородным, если все его гиперрёбра имеют одинаковое число составляющих вершин. В гипотезе Эрдёша — Фабера — Ловаса n клик размера n можно интерпретировать как гиперребра n-однородного линейного гиперграфа, который имеет те же вершины, что и лежащий в основе граф. На этом языке гипотеза Эрдёша — Фабера — Ловаса утверждает, что если любой n-однородный линейный гиперграф с n гиперрёбрами, можно раскрасить в n цветов вершины таким образом, что каждое гиперребро имеет одну вершину каждого цвета.

Простой гиперграф — это гиперграф, в котором не более одного ребра соединяет любую пару вершин и нет гиперрёбер размера единица. В формулировке гипотезы Эрдёша — Фабера — Ловаса на языке раскраски графов можно без проблем удалить вершины, принадлежащие лишь одной клике, поскольку их раскраска трудностей не вызывает. После того как это сделано, гиперграф, который имеет в качестве вершин клики, а в качестве гиперрёбер вершины графа, является простым гиперграфом. Гиперграф, двойственный раскраске вершин, это рёберная раскраска. Таким образом, гипотеза Эрдёша — Фабера — Ловаса эквивалентна утверждению, что любой простой гиперграф с n вершинами имеет хроматический индекс (число цветов рёберной раскраски), не превосходящий n.

Граф в гипотезе Эрдёша — Фабера — Ловаса можно представить как граф пересечений множеств — каждой вершине графа соответствует множество клик, содержащих вершину, и любые две вершины соединены ребром, если их соответствующие множества имеют непустое пересечение. Используя это описание графа, гипотезу можно поставить следующим образом: если некоторое семейство имеет в общей сложности n элементов и любые два множества в пересечении имеют не более одного элемента, граф пересечений этих множеств можно раскрасить в n цветов.

Число пересечений графа G равно минимальному числу элементов в семействе множеств, граф пересечений которых совпадает с G, или, эквивалентно, минимальному числу вершин гиперграфа, рёберный граф которого совпадает с G. Кляйн и Марграф определяют аналогично линейное число пересечений графа как минимальное число вершин в линейном гиперграфе, рёберный граф которого совпадает с G. Как они замечают, гипотеза Эродёша — Фабера Ловаса эквивалентна утверждению, что хроматическое число любого графа не превосходит его линейного числа пересечений.

Хаддад и Тардиф дают другую, но всё же эквивалентную, формулировку в терминах теории клонов.

История и частичные результаты

Пал Эрдёш, Ванс Фабер и Ласло Ловас сформулировали гипотезу в 1972. Пал Эрдёш первоначально предложил $50 за доказательство верности гипотезы, а позднее увеличил вознаграждение до $500.

Чианг и Лоулер доказали, что хроматическое число графа в гипотезе не превосходит 3k/2 − 2, а Кан улучшил эту величину до k + o(k).

Связанные задачи

Интересно также рассмотреть хроматическое число графов, образованных объединением k клик с k вершинами в каждой без ограничения размера пересечения пар клик. В этом случае хроматическое число их объединения не превосходит $1+k{\sqrt {k-1}}$ и некоторые графы, образованные таким образом, требуют именно такого количества цветов.

Известно, что версия гипотезы, использующая дробное хроматическое число вместо хроматического числа, верна. То есть, если граф G образован объединением k k-клик, которые попарно пересекаются не более чем в двух вершинах, граф G может быть раскрашен в k-цветов.

В случае рёберной раскраски простых гиперграфов Хиндман определяет число L для простого гиперграфа как число вершин гиперграфа, принадлежащих гиперребру с тремя и более вершинами. Он показал, что для любого фиксированного значения L проверка, что гипотеза верна для всех простых графов с $L\leqslant 10$, требует конечного количества вычислений. Основываясь на этой идее, он показал, что гипотеза верна для всех простых гиперграфов с $L\leqslant 10$. В формулировке раскраски графов, образованных объединением клик, результат Хиндмана показывает, что гипотеза верна, если не более десяти клик содержат вершины, принадлежащие трём или более кликам. В частности, это верно для $n\leqslant 10$.

См. также

• Список математических утверждений и объектов, названных в честь Пала Эрдёша