Гипотеза Эрдеша — Фабера — Ловаша: раскраска графов и гиперграфов.

Введение

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

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

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

В качестве примера можно привести историю о распределении мест в комитетах: предположим, что в университете есть k комитетов, каждый из которых состоит из k преподавателей, и что все комитеты собираются в одной комнате, в которой k мест. Предположим также, что не более одного человека принадлежит к пересечению любых двух комитетов. Возможно ли назначить места членам комитетов таким образом, чтобы каждый член сидел на одном и том же месте для всех различных комитетов, в которых он или она состоит? В этой модели задачи преподаватели соответствуют вершинам графа, комитеты соответствуют полным графам, а места соответствуют цветам вершин. Линейный гиперграф (также известный как частичное линейное пространство) — это гиперграф, для которого каждые два гиперребра имеют не более одной общей вершины. Гиперграф называется однородным, если все его гиперребра имеют одинаковое количество вершин. n клик размера n в гипотезе Эрдоша — Фабера — Ловаса можно интерпретировать как гиперребра n-однородного линейного гиперграфа, имеющего те же вершины, что и базовый граф. На этом языке гипотеза Эрдоша — Фабера — Ловаса гласит, что для любого n-однородного линейного гиперграфа с n гиперребрами можно раскрасить вершины таким образом, чтобы каждое гиперребро содержало по одной вершине каждого цвета. Простой гиперграф — это гиперграф, в котором не более одного гиперребра соединяет любую пару вершин и нет гиперребер размера не более одного. В формулировке раскраски графа гипотезы Эрдоша — Фабера — Ловаса можно безопасно удалять вершины, принадлежащие только одной клике, поскольку их раскраска не представляет никаких трудностей; после этого гиперграф, имеющий вершину для каждой клики и гиперребро для каждой вершины графа, образует простой гиперграф. И гиперграф, двойственный раскраске вершин, является двойственным раскраске ребер. Таким образом, гипотеза Эрдоша — Фабера — Ловаса эквивалентна утверждению, что любой простой гиперграф с n вершинами имеет хроматический индекс (число раскраски ребер) не более n. Граф гипотезы Эрдоша — Фабера — Ловаса может быть представлен как граф пересечений множеств: каждой вершине графа соответствует множество клик, содержащих эту вершину, и любые две вершины соединяются ребром, если соответствующие множества имеют непустое пересечение. Используя это описание графа, гипотезу можно перефразировать следующим образом: если некоторое семейство множеств имеет n элементов в общей сложности, и любые два множества пересекаются не более чем в одном элементе, то граф пересечений этих множеств можно раскрасить n цветами. Число пересечений графа G — это минимальное количество элементов в семействе множеств, граф пересечений которых является G, или, эквивалентно, минимальное количество вершин в гиперграфе, линейный граф которого является G. Определим линейное число пересечений графа как минимальное количество вершин в линейном гиперграфе, линейный граф которого является G. Как они отмечают, гипотеза Эрдоша — Фабера — Ловаса эквивалентна утверждению, что хроматическое число любого графа не превышает его линейного числа пересечений. Представляем другую, но эквивалентную формулировку, в терминах теории клонов.

introduced the problem with a story about seating assignment in committees: suppose that, in a university department, there are k committees, each consisting of k faculty members, and that all committees meet in the same room, which has k chairs. Suppose also that at most one person belongs to the intersection of any two committees. Is it possible to assign the committee members to chairs in such a way that each member sits in the same chair for all the different committees to which he or she belongs? In this model of the problem, the faculty members correspond to graph vertices, committees correspond to complete graphs, and chairs correspond to vertex colors. A linear hypergraph (also known as partial linear space) is a hypergraph with the property that every two hyperedges have at most one vertex in common. A hypergraph is said to be uniform if all of its hyperedges have the same number of vertices as each other. The n cliques of size n in the Erdős–Faber–Lovász conjecture may be interpreted as the hyperedges of an n uniform linear hypergraph that has the same vertices as the underlying graph. In this language, the Erdős–Faber–Lovász conjecture states that, given any n uniform linear hypergraph with n hyperedges, one may n color the vertices such that each hyperedge has one vertex of each color. A simple hypergraph is a hypergraph in which at most one hyperedge connects any pair of vertices and there are no hyperedges of size at most one. In the graph coloring formulation of the Erdős–Faber–Lovász conjecture, it is safe to remove vertices that belong to a single clique, as their coloring presents no difficulty; once this is done, the hypergraph that has a vertex for each clique, and a hyperedge for each graph vertex, forms a simple hypergraph. And, the hypergraph dual of vertex coloring is edge coloring. Thus, the Erdős–Faber–Lovász conjecture is equivalent to the statement that any simple hypergraph with n vertices has chromatic index (edge coloring number) at most n.

The graph of the Erdős–Faber–Lovász conjecture may be represented as an intersection graph of sets: to each vertex of the graph, correspond the set of the cliques containing that vertex, and connect any two vertices by an edge whenever their corresponding sets have a nonempty intersection. Using this description of the graph, the conjecture may be restated as follows: if some family of sets has n total elements, and any two sets intersect in at most one element, then the intersection graph of the sets may be n colored. The intersection number of a graph G is the minimum number of elements in a family of sets whose intersection graph is G, or equivalently the minimum number of vertices in a hypergraph whose line graph is G. define the linear intersection number of a graph, similarly, to be the minimum number of vertices in a linear hypergraph whose line graph is G. As they observe, the Erdős–Faber–Lovász conjecture is equivalent to the statement that the chromatic number of any graph is at most equal to its linear intersection number. present another yet equivalent formulation, in terms of the theory of clones.

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

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