Теорема Де Брейна – Эрдеша (теория графов) - De Bruijn–Erdős theorem (graph theory)

В теория графов, то Теорема Де Брейна – Эрдеша. относится раскраска графика из бесконечный граф к той же проблеме на своей конечной подграфы. Он утверждает, что, когда все конечные подграфы могут быть раскрашены ${ displaystyle c}$ цветов, то же самое верно для всего графика. Теорема была доказана Николаас Говерт де Брёйн и Пол Эрдёш  (1951 ), в честь которого назван.

Теорема Де Брёйна – Эрдеша имеет несколько различных доказательств, все в той или иной степени зависят от аксиома выбора. Его приложения включают расширение теорема о четырех цветах и Теорема Дилворта из конечных графов и частично упорядоченные наборы к бесконечным и уменьшая Проблема Хадвигера – Нельсона на хроматическое число плоскости к задаче о конечных графах. Его можно обобщить с конечного числа цветов на наборы цветов, мощность это сильно компактный кардинал.

Определения и заявление

An неориентированный граф математический объект, состоящий из набора вершины и набор края которые связывают пары вершин. Две вершины, связанные с каждым ребром, называются его конечными точками. Граф конечен, когда его вершины и ребра образуют конечные множества, и бесконечно в противном случае. А раскраска графика связывает каждую вершину с цветом, взятым из набора цветов, таким образом, что каждое ребро имеет два разных цвета на концах. Частая цель раскраски графов - минимизировать общее количество используемых цветов; то хроматическое число графика - это минимальное количество цветов.^[1] В теорема о четырех цветах утверждает, что каждый конечный граф, который можно нарисовать без пересечений в Евклидова плоскость требуется не более четырех цветов; однако для некоторых графиков с более сложной связью требуется более четырех цветов.^[2] Это следствие аксиома выбора что хроматическое число четко определенный для бесконечных графов, но для этих графов хроматическое число само может быть бесконечным количественное числительное.^[3]

А подграф графа - это другой граф, полученный из подмножества его вершин и подмножества его ребер. Если раскрашен больший граф, такая же раскраска может быть использована для подграфа. Следовательно, хроматическое число подграфа не может быть больше хроматического числа всего графа. Теорема Де Брёйна – Эрдеша касается хроматических чисел бесконечных графов и показывает, что (опять же, принимая аксиому выбора), они могут быть вычислены по хроматическим числам их конечных подграфов. Он утверждает, что если хроматические числа конечных подграфов графа ${ displaystyle G}$ иметь конечное максимальное значение ${ displaystyle c}$, то хроматическое число ${ displaystyle G}$ сам точно ${ displaystyle c}$. С другой стороны, если нет конечного верхняя граница от хроматических чисел конечных подграфов ${ displaystyle G}$, то хроматическое число ${ displaystyle G}$ сам по себе должен быть бесконечным.^[4]

Приложения

Первоначальная мотивация Эрдеша при изучении этой проблемы заключалась в распространении с конечных графов на бесконечные теоремы о том, что всякий раз, когда граф имеет ориентация с конечной максимальной исходящей степенью ${ displaystyle k}$, он также имеет ${ displaystyle (2k + 1)}$-раскрашивание. Для конечных графов это следует потому, что такие графы всегда имеют вершину степени не выше ${ displaystyle 2k}$, который можно раскрасить одним из ${ displaystyle 2k + 1}$ цвета после того, как все остальные вершины раскрашены рекурсивно. Бесконечные графы с такой ориентацией не всегда имеют вершину низкой степени (например, Решетки Бете имеют ${ displaystyle k = 1}$ но сколь угодно большой минимальной степени), поэтому этот аргумент требует, чтобы граф был конечным. Но теорема Де Брёйна – Эрдеша показывает, что ${ displaystyle (2k + 1)}$-раскраска существует даже для бесконечных графов.^[5]

Семикрасочная окраска плоскости и четырехцветная Шпиндель Мозера нарисованный как график единичных расстояний на плоскости, обеспечивающий верхнюю и нижнюю границы для Проблема Хадвигера – Нельсона.

Еще одно приложение теоремы Де Брейна – Эрдеша - это Проблема Хадвигера – Нельсона, который спрашивает, сколько цветов нужно, чтобы раскрасить точки Евклидова плоскость так что каждые две точки, которые находятся на расстоянии единицы друг от друга, имеют разные цвета. Это раскраска графика задача для бесконечного графа, у которого есть вершина для каждой точки плоскости и ребро для каждых двух точек, чьи Евклидово расстояние ровно один. Подграфы этого графа называются графики единичных расстояний. Граф единичных расстояний с семью вершинами, Шпиндель Мозера, требуется четыре цвета; в 2018 году были обнаружены гораздо более крупные графики единичных расстояний, требующие пяти цветов.^[6] Весь бесконечный граф имеет известную раскраску в семь цветов, основанную на шестиугольной мозаике плоскости. Следовательно, хроматическое число плоскости должно быть 5, 6 или 7, но неизвестно, какое из этих трех чисел является правильным значением. Теорема Де Брёйна – Эрдеша показывает, что для этой задачи существует конечный граф единичных расстояний с тем же хроматическим числом, что и вся плоскость, поэтому, если хроматическое число больше пяти, этот факт может быть доказан конечным вычислением.^[7]

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

Таким же образом теорема Де Брёйна – Эрдеша расширяет теорема о четырех цветах от конечных плоских графов до бесконечных плоских графов. Каждый конечный планарный граф можно раскрасить в четыре цвета по теореме о четырех цветах. Теорема Де Брёйна – Эрдеша затем показывает, что каждый граф, который можно нарисовать без пересечений на плоскости, конечной или бесконечной, можно раскрасить в четыре цвета. В более общем смысле любой бесконечный граф, для которого все конечные подграфы плоские, снова может быть четырехцветным.^[9]

Доказательства

В первоначальном доказательстве теоремы Де Брёйна – Эрдеша, сделанном Де Брёйном, использовалось трансфинитная индукция.^[10]

Готтшалк (1951) предоставил следующее очень короткое доказательство, основанное на Тихонов с теорема компактности в топологии. Предположим, что для данного бесконечного графа грамм, каждый конечный подграф является kраскрашиваем, и пусть Икс быть пространством всех заданий k цвета к вершинам грамм (независимо от того, образуют ли они допустимую окраску). потом Икс может быть задана топология как пространство продукта k^{V(грамм)}, куда V(грамм) обозначает множество вершин графа. По теореме Тихонова это топологическое пространство есть компактный. Для каждого конечного подграфа F из грамм, позволять Икс_F быть подмножеством Икс состоящий из присвоений цветов, которые правильно окрашивают F. Тогда система множеств Икс_F это семья закрытые наборы с свойство конечного пересечения, поэтому по компактности он имеет непустое пересечение. Каждый член этого пересечения является допустимой раскраской грамм.^[11]

Другое доказательство с использованием Лемма Цорна был дан Lajos Pósa, а также в 1951 г. тезис Габриэль Эндрю Дирак. Если грамм бесконечный граф, в котором каждый конечный подграф k-раскрашиваемый, то по лемме Цорна он является подграфом максимальный график M с тем же свойством (тот, к которому нельзя добавить больше ребер, не заставляя некоторый конечный подграф потребовать больше, чем k цвета). В бинарное отношение несмежности в M является отношение эквивалентности, а его классы эквивалентности обеспечивают k-крашивание грамм. Однако это доказательство труднее обобщить, чем доказательство компактности.^[12]

Теорема также может быть доказана с помощью ультрафильтры^[13] или же нестандартный анализ.^[14] Нэш-Уильямс (1967) дает доказательство для графов со счетным числом вершин на основе Лемма Кёнига о бесконечности.

Зависимость от выбора

Все доказательства теоремы Де Брейна – Эрдеша используют некоторую форму аксиома выбора. Некоторая форма этого предположения необходима, поскольку существуют модели математики, в которой и аксиома выбора, и теорема Де Брейна – Эрдеша неверны. Точнее, Мыцельский (1961) показал, что теорема является следствием Теорема о булевом простом идеале, свойство, которое подразумевается аксиомой выбора, но более слабое, чем полная аксиома выбора, и Ляухли (1971) показал, что теорема Де Брёйна – Эрдеша и теорема о булевом простом идеале эквивалентны в аксиоматической степени.^[15] Можно также показать, что теорема Де Брейна – Эрдеша для счетных графов эквивалентна по силе аксиоматики в рамках теории арифметика второго порядка, к лемме Кёнига о бесконечности.^[16]

В качестве контрпримера к теореме в моделях теории множеств без выбора, пусть грамм - бесконечный граф, вершины которого представляют все возможные действительные числа. В грамм, соедините каждые два действительных числа Икс и у ребром всякий раз, когда одно из значений (|Икс − у| ± √2) это Рациональное число. Эквивалентно, в этом графе ребра существуют между всеми действительными числами Икс и все действительные числа вида Икс ± (√2 + q), куда q - любое рациональное число. Каждый путь в этом графе, начиная с любого действительного числа Икс, чередуется числа, которые отличаются от Икс на рациональное число плюс четное кратное √2и числа, которые отличаются от Икс на рациональное число плюс нечетное кратное √2Это чередование предотвращает грамм не содержит циклов нечетной длины, поэтому каждый его конечный подграф требует только двух цветов. Однако в Модель Соловея в котором каждый набор действительных чисел Измеримый по Лебегу, грамм требует бесконечно много цветов, так как в этом случае каждый цветовой класс должен быть измеримым набором, и можно показать, что каждый измеримый набор действительных чисел без ребер в грамм должен иметь нулевую меру. Следовательно, в модели Соловея (бесконечное) хроматическое число всех грамм намного больше хроматического числа его конечных подграфов (не более двух).^[17]

Обобщения

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

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

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

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

Примечания

Рекомендации