WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.