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

В теории графов гипотеза Эрдеша -Фабера-Ловаса представляет собой проблему раскраски графов , названную в честь Пола Эрдеша , Вэнса Фабера и Ласло Ловаса , которые сформулировали ее в 1972 году. ^[1] В ней говорится:

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

Гипотеза для всех достаточно больших значений k была доказана Донг Йеап Кангом, Томом Келли, Даниэлой Кюн , Абишеком Метхуку и Дериком Остхусом . [ 2 ^]

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

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

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

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

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

Хаддад и Тардиф (2004) предлагают еще одну эквивалентную формулировку в терминах теории клонов .

Пол Эрдёш, Вэнс Фабер и Ласло Ловас сформулировали безобидную на вид гипотезу на вечеринке в Боулдере, штат Колорадо, в сентябре 1972 года. Её сложность осознавалась лишь медленно. ^[1] Первоначально Пол Эрдёш предлагал 50 долларов США за доказательство гипотезы в утвердительном ключе, а затем увеличил вознаграждение до 500 долларов США. ^{[1] [6]} Фактически, Пол Эрдёш считал это одной из трёх своих самых любимых комбинаторных задач. ^{[1] [7]}

Чан и Лоулер (1988) доказали, что хроматическое число графов в этой гипотезе не превышает , а Кан (1992) улучшил это число до k + o ( k ) .${\displaystyle {\tfrac {3}{2}}k-2}$

В 2023 году, почти через 50 лет после того, как была сформулирована первоначальная гипотеза ^[1] , она была решена для всех достаточно больших n Донгом Йеап Кангом, Томом Келли, Даниэлой Кюн, Абишеком Метхуку и Дериком Остхусом. ^[8]

Также интересно рассмотреть хроматическое число графов, образованных как объединение k клик по k вершин в каждой, не ограничивая, насколько большими могут быть пересечения пар клик. В этом случае хроматическое число их объединения не превышает 1+ k √ k − 1 , и некоторые графы, образованные таким образом, требуют именно такого количества цветов. ^[9]

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

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

• Список гипотез Пола Эрдёша