В теории графов гипотеза Эрдеша -Фабера-Ловаса представляет собой проблему раскраски графов , названную в честь Пола Эрдеша , Вэнса Фабера и Ласло Ловаса , которые сформулировали ее в 1972 году. [1] В ней говорится:
Гипотезу для всех достаточно больших значений k доказали Донг Йип Канг, Том Келли, Даниэла Кюн , Абхишек Метуку и Дерик Остус . [2]
Хаддад и Тардиф (2004) представили проблему, рассказав о распределении мест в комитетах: предположим, что на факультете университета имеется 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 ) .
В 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 .
