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

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

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

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

В 2021 году был опубликован препринт с доказательством гипотезы для больших Шаблон:Mvar[1].

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

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

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

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

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

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

Хаддад и ТардифШаблон:Sfn дают другую, но всё же эквивалентную, формулировку в терминах теории Шаблон:Не переведено 5.

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

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

Чианг и ЛоулерШаблон:Sfn доказали, что хроматическое число графа в гипотезе не превосходит Шаблон:Math, а КанШаблон:Sfn улучшил эту величину до Шаблон:Math.

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

Интересно также рассмотреть хроматическое число графов, образованных объединением Шаблон:Mvar клик с Шаблон:Mvar вершинами в каждой без ограничения размера пересечения пар клик. В этом случае хроматическое число их объединения не превосходит 1+kk−1 и некоторые графы, образованные таким образом, требуют именно такого количества цветовШаблон:SfnШаблон:Sfn.

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend Шаблон:Rq

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Harvnb. Хиндман (Шаблон:Harv) описывает эквивалентную задачу на языке системы множеств вместо гиперграфов.
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Гипотеза_Эрдёша_—_Фабера_—_Ловаса&oldid=19086