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

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

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

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

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

Эквивалентные составы

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

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

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

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

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

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

История, частичные результаты и возможные доказательства

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

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

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

Связанные проблемы

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

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

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

См. также

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

Ссылки

• Чанг, Висконсин; Лоулер, Э.Л. (1988), «Раскраска по краям гиперграфов и гипотеза Эрдеша, Фабера, Ловаша», Combinatorica , 8 (3): 293–295, doi : 10.1007/BF02126801 , MR   0963120 , S2CID   1991737 .
• Чанг, Фан ; Грэм, Рон (1998), Эрдеш о графиках: его наследие нерешенных проблем , AK Peters, стр. 97–99 .
• Эрдеш, Пол (1981), «О комбинаторных проблемах, которые мне больше всего хотелось бы видеть решенными», Combinatorica , 1 : 25–42, CiteSeerX   10.1.1.294.9566 , doi : 10.1007/BF02579174 , MR   0602413 , S2CID   189916865 .
• Эрдеш, Пол (1991), «Сложная задача 6664», American Mathematical Monthly , 98 (7), Математическая ассоциация Америки: 655, doi : 10.2307/2324942 , JSTOR   2324942 . Решения Илиаса Кастанаса, Чарльза Вандена Эйндена и Ричарда Хольцсагера , American Mathematical Monthly 100 (7): 692–693, 1992.
• Хаддад, Л.; Тардиф, К. (2004), «Теоретико-клоническая формулировка гипотезы Эрдёша-Фабера-Ловаша», Discountes Mathematicae Graph Theory , 24 (3): 545–549, doi : 10.7151/dmgt.1252 , MR   2120637 .
• Хиндман, Нил (1981), «О гипотезе Эрдеша, Фабера и Ловаса о n -раскрасках», кан. Дж. Математика. , 33 (3): 563–570, doi : 10.4153/CJM-1981-046-9 , MR   0627643 , S2CID   124025730 .
• Горак, П.; Туза, З. (1990), «Проблема раскраски, связанная с гипотезой Эрдеша–Фабера–Ловаса», Journal of Combinatorial Theory, Series B , 50 (2): 321–322, doi : 10.1016/0095-8956(90) 90087-Г . Исправлено в JCTB 51 (2): 329, 1991 г. , добавлено имя Тузы в качестве соавтора.
• Хьюстон-Эдвардс, Келси (5 апреля 2021 г.), «Математики решают гипотезу Эрдеша о раскраске» , журнал Quanta
• Кан, Джефф (1992), «Раскраска почти непересекающихся гиперграфов в n + o ( n ) цветов», Журнал комбинаторной теории, серия A , 59 : 31–39, doi : 10.1016/0097-3165(92)90096-D , МР   1141320 .
• Кан, Джефф ; Сеймур, Пол Д. (1992), «Дробная версия гипотезы Эрдеша-Фабера-Ловаса», Combinatorica , 12 (2): 155–160, doi : 10.1007/BF01204719 , MR   1179253 , S2CID   6144958 .
• Кан, Джефф (1997), «О некоторых проблемах Пауля Эрдеша с гиперграфами и асимптотике сопоставлений, накрытий и раскрасок» , «Математика Пола Эрдеша I» , «Алгоритмы и комбинаторика», том. 13, Springer Berlin Heidelber, стр. 345–371, doi : 10.1007/978-3-642-60408-9_26 , ISBN  978-3-642-60408-9
• Калай, Гил (14 января 2021 г.), «Чтобы поднять настроение в трудные времена 17: Удивительно! Гипотезу Эрдеша-Фабера-Ловаса (для больших n) доказали Донг Йип Канг, Том Келли, Даниэла Кюн, Абхишек Метуку, и Дерик Остус!" , Комбинаторика и многое другое.
• Кан, Дон Йеп; Келли, Том; Кюн, Даниэла; Метуку, Абхишек; Остус, Дерик (2023), «Доказательство гипотезы Эрдеша-Фабера-Ловаса», Annals of Mathematics , 198 (2): 537–618, arXiv : 2101.04698 , doi : 10.4007/annals.2023.198.2.2
• Кляйн, Хауке; Марграф, Мариан (2003), О числе линейных пересечений графов , arXiv : math.CO/0305073 , Bibcode : 2003math......5073K .
• Ромеро, Дэвид; Санчес Арройо, Абдон (2007), «Прогресс в отношении гипотезы Эрдеша – Фабера – Ловаса», в Гриммете, Джеффри; МакДиармид, Колин (ред.), Комбинаторика, сложность и случайность: дань уважения Доминику Уэлшу , Оксфордская серия лекций по математике и ее приложениям, Oxford University Press, стр. 285–298, doi : 10.1093/acprof:oso/9780198571278.003. 0017 , ISBN  9780198571278 .