Теорема де Брёйна — Эрдёша (теория графов)

Хроматическое число бесконечного графа, если это число конечно, равно наибольшему хроматическому числу среди всех его конечных подграфов.

• Эквивалентная формулировка: любой k-критический граф конечен.
• Теорема применяется для расширения задачи четырёх красок и теоремы Дилуорса для конечных графов и множеств с частичным порядком до бесконечных вариантов, сведения задачи Нельсона — Эрдёша — Хадвигера о хроматическом числе плоскости к задачам на конечных графах.
  • В частности, из теоремы Брёйна — Эрдёша и теоремы о четырёх красках следует, что любой бесконечный планарный граф допускает раскраску ч четыре цвета.
• Теорему можно обобщить от конечного числа цветов к множеству цветов, кардинальное число которого является строго компактным кардинальным числом.

Теорема де Брёйна — Эрдёша имеет несколько различных доказательств, каждое использует аксиому выбора. Исходное доказательство де Брёйна использовало трансфинитную индукцию[2].

Готтшальк[3] дал следующее очень короткое доказательство, основанное на теореме о компактности Тихонова в топологии. Предположим, что для заданного бесконечного графа G любой конечный подграф является k-раскрашиваемым, и пусть X — пространство всех назначений k цветов вершинам графа G (независимо от того, является ли данная раскраска правильной). Тогда X можно рассматривать как произведение топологических пространств k^V(G), которое по теореме Тихонова компактно. Для каждого конечного подграфа F графа G, пусть X_F — подмножество X, состоящее из назначений цветов, дающих правильную раскраску F. Тогда система множеств X_F является семейством замкнутых множеств со свойством конечных пересечений, так что из-за компактности система имеет непустое пересечение. Любой член этого пересечения является правильной раскраской G [4].

Другое доказательство, использующее лемму Цорна, дал Лайош Поза, а также привёл в тезисах диссертации 1951 Эндрю Дирак. Если G — бесконечный граф, в котором любой конечный подграф является k-раскрашиваемым, тогда по лемме Цорна он является подграфом максимального графа M с тем же свойством (граф, к которому нельзя добавить рёбра без того, чтобы некоторый конечный подграф не потребует более k цветов). Бинарное отношение несмежности в M является отношением эквивалентности и классы эквивалентности этого отношения дают k-раскраску графа G. Однако это доказательство труднее обобщить, чем доказательство по лемме о компактности[5].

Теорему можно доказать с помощью ультрафильтров[6] или нестандартного анализа[7]. Нэш-Вилльямс[8] дал доказательство для графов со счётным числом вершин, основываясь на лемме Кёнига о бесконечном дереве.

Все доказательства теоремы де Брёйна — Эрдёша используют аксиому выбора. Существуют модели математики, в которых не являются верными как аксиома выбора, так и теорема де Брёйна — Эрдёша.

Например, пусть G — бесконечный граф, в котором вершинами являются все вещественные числа. В G соединим любые два вещественных чисел x и y ребром, если значение (|x − y| ± √2) является рациональным числом. Эквивалентно, в этом графе, рёбра существуют между всеми вещественными числами x и всеми вещественными числами вида x ± (√2 + q), где q — любое рациональное число. Таким образом, если две вершины в G отличаются на чётный целый множитель квадратного корня из двух плюс рациональное число, для них можно использовать один цвет и точки можно считать эквивалентными. Граф, образованный стягиванием класса эквивалентности в одну вершину, является бесконечным паросочетанием и может быть легко раскрашен в два цвета, используя аксиому выбора. Таким образом, любой конечный подграф графа G требует два цвета. Однако в модели Соловея, в которой каждое множество вещественных чисел измеримо по Лебегу, G требует бесконечно много цветов, поскольку в этом случае каждый класс цвета должен быть измеримым множеством, и можно показать, что любое измеримое множество вещественных чисел, не содержащее рёбер из G, должно иметь меру ноль. Таким образом, в модели Соловея, (неограниченное) хроматическое число всего графа G много больше хроматического числа его конечных подграфов (максимум два)[9][10].

Можно показать, что теорема де Брёйна — Эрдёша для счётных графов эквивалентна (в теории арифметики второго порядка) лемме Кёнига о бесконечном дереве[11].

Раскраска плоскости в семь цветов и четырёхцветный граф единичных расстояний на плоскости, что даёт верхнюю и нижнюю границы для задачи Нельсона — Эрдёша — Хадвигера.

Одно из приложений теоремы де Брёйна — Эрдёша — это задачи Нельсона — Эрдёша — Хадвигера о хроматическом числе графа единичных расстояний евклидовой плоскости. Граф плоскости имеет несчётное число вершин, по одной на каждую точку плоскости. Две вершины связаны ребром, когда евклидово расстояние между соответствующими двумя точками в точности равно единице. Бесконечный граф имеет конечные подграфы, такие как веретено Мозера, которые требуют четыре цвета, и известна раскраска в семь цветов, основанная на шестиугольной мозаике плоскости. Таким образом, хроматическое число плоскости должно принадлежать множеству {4,5,6,7}, но какое из этих четырёх чисел является действительно хроматическим числом, неизвестно. Теорема де Брёйна — Эрдёша показывает, что для этой задачи существует конечный граф единичных расстояний с тем же хроматическим числом, что и вся плоскость целиком, так что если хроматическое число больше четырёх, то этот факт может быть доказан конечными вычислениями[12].

Теорема де Брёйна — Эрдёша может быть использована также для расширения теоремы Дилуорса от конечного варианта к бесконечным частично упорядоченным множествам. Теорема Дилуорса утверждает, что ширина частичного порядка (наибольшее число элементов в множестве взаимно несравнимых элементов) равна минимальному числу цепочек (полностью упорядоченных подмножеств), на которые может быть разложен частичный порядок. Разложение на цепочки можно рассматривать как раскраску графа несравнимости частичного порядка (граф, имеющий вершину для каждого элемента порядка и ребро для каждой пары несравнимых элементов). Используя эту интерпретацию как раскраску, вместе с отдельным доказательством теоремы Дилуорса для конечных частично упорядоченных множеств, можно доказать, что бесконечное частично упорядоченное множество имеет конечную ширину w тогда и только тогда, когда его можно разложить на w цепочек[13].

Таким же образом, Теорема де Брёйна — Эрдёша расширяет проблему четырёх красок с конечных планарных графов на бесконечные планарные графы — любые графы, которые можно нарисовать без пересечений на плоскости, конечные или бесконечные, можно раскрасить четырьмя красками. Более обще, любой бесконечный граф, для которого любой конечный подграф планарен, может быть снова раскрашен в четыре цвета[14][15]

Теорема де Брёйна — Эрдёша может быть использована для ответа на вопрос Гелвина относительно теоремы о промежуточном значении для хроматических чисел графов — для любых двух конечных чисел j < k и любого графа G с хроматическим числом k, существует подграф графа G с хроматическим числом j. Чтобы это увидеть, найдём конечный подграф графа G с тем же хроматическим числом, что и сам G, а затем удаляем вершины одну за другой, пока не получим хроматическое число j. Однако случай для бесконечных хроматических чисел более сложен — это согласуется с теорией множеств, что существует граф с ℵ₂ вершинами и хроматическим числом ℵ₂, но не имеющего подграфа c хроматическим числом ℵ₁[16][17].

Радо[18] доказал следующую теорему, которую можно рассматривать как обобщение теоремы де Брёйна — Эрдёша. Пусть V — бесконечное множество, например, множество вершин в бесконечном графе. Для каждого элемента v множества V, пусть c_v является конечным множеством цветов. Кроме того, для любого конечного подмножества S множества V, выберем некоторую раскраску C_S подмножества S, в которой цвет каждого элемента v пожмножества S принадлежит c_v. Тогда существует глобальная раскраска χ всех V со свойством, что любое конечное множество S имеет конечное супермножество T, на котором χ и C_T согласуются. В частности, если мы выбираем k-раскраску для любого конечного подграфа бесконечного графа G, тогда существует k-раскраска графа G, в которой каждый конечный граф имеет больший суперграф, раскраска которого согласуется с раскраской всего графа [19].

Если граф не имеет конечного хроматического числа, тогда из теоремы де Брёйна — Эрдёша следует, что граф должен содержать конечные подграфы для каждого возможного хроматического числа. Исследователи также исследовали другие условия на подграфы. Например, неограниченные хроматические графы должны также содержать любой конечный двудольный граф в качестве подграфа. Однако они могут иметь произвольно большой нечётный обхват[20][17].

Теорема де Брёйна — Эрдёша также применима прямо к задачам раскраски гиперграфов, где требуется, чтобы каждое гиперребро имело вершины более одного цвета. Как и для графов, гиперграф имеет k-раскраску тогда и только тогда, когда любое из его конечных подгиперграфов имеет k-раскраску[21]. Специальный случай теоремы о компактности Курта Гёделя утверждает, что множество утверждений первого порядка имеет модель тогда и только тогда, когда любое конечное подмножество имеет модель.

Теорему можно обобщить для случаев, когда число цветов является бесконечным кардинальным числом — если κ является строго компактным кардинальным числом, то для любого графа G и кардинального числа μ < κ, G имеет хроматическое число, не превосходящее μ, тогда и только тогда, когда его подграфы с кардинальностью меньшей κ имеют хроматическое число, не превосходящее μ [22]. Оригинальная теорема де Брёйна — Эрдёша является частным случаем κ = ℵ₀ этого обобщения, поскольку множество конечно тогда и только тогда, когда его мощность меньше ℵ₀. Однако некоторые предположения, такие как строгая компактность кардинального числа множества необходимы — если обобщённая континуум-гипотеза верна, то для любого бесконечного кардинала γ, существует граф G мощностью (2^γ)⁺, такой, что хроматическое число графа G больше γ, но любой подграфа графа G, множество вершин которого имеет меньшую мощность, чем у G, имеет хроматическое число, не превосходящее γ[23]. Лейк[24] описывает бесконечные графы, удовлетворяющие обобщению теоремы де Брёйна — Эрдёша, как графы, хроматическое число которых равно наибольшему хроматическому числу строго меньших подграфов.