Русская Википедия:Теорема де Брёйна — Эрдёша (теория графов)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де БрёйномШаблон:Sfn.

Формулировка

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

Замечания

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

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

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

Другое доказательство, использующее лемму Цорна, дал Шаблон:Не переведено 5, а также привёл в тезисах диссертации 1951 Шаблон:Не переведено 5. Если Шаблон:Math — бесконечный граф, в котором любой конечный подграф является Шаблон:Mvar-раскрашиваемым, тогда по лемме Цорна он является подграфом максимального графа Шаблон:Mvar с тем же свойством (граф, к которому нельзя добавить рёбра без того, чтобы некоторый конечный подграф не потребует более Шаблон:Mvar цветов). Бинарное отношение несмежности в Шаблон:Mvar является отношением эквивалентности и классы эквивалентности этого отношения дают Шаблон:Mvar-раскраску графа Шаблон:Mvar. Однако это доказательство труднее обобщить, чем доказательство по лемме о компактности[2].

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

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

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

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

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

Приложения

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

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

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

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

Теорема де Брёйна — Эрдёша может быть использована для ответа на вопрос Шаблон:Не переведено 5 относительно теоремы о промежуточном значении для хроматических чисел графов — для любых двух конечных чисел Шаблон:Math и любого графа Шаблон:Mvar с хроматическим числом Шаблон:Mvar, существует подграф графа Шаблон:Mvar с хроматическим числом Шаблон:Mvar. Чтобы это увидеть, найдём конечный подграф графа Шаблон:Mvar с тем же хроматическим числом, что и сам Шаблон:Mvar, а затем удаляем вершины одну за другой, пока не получим хроматическое число Шаблон:Mvar. Однако случай для бесконечных хроматических чисел более сложен — это согласуется с теорией множеств, что существует граф с Шаблон:Math вершинами и хроматическим числом Шаблон:Math, но не имеющего подграфа c хроматическим числом Шаблон:MathШаблон:SfnШаблон:Sfn.

Обобщения

РадоШаблон:Sfn доказал следующую теорему, которую можно рассматривать как обобщение теоремы де Брёйна — Эрдёша. Пусть Шаблон:Mvar — бесконечное множество, например, множество вершин в бесконечном графе. Для каждого элемента Шаблон:Mvar множества Шаблон:Mvar, пусть Шаблон:Math является конечным множеством цветов. Кроме того, для любого конечного подмножества Шаблон:Mvar множества Шаблон:Mvar, выберем некоторую раскраску Шаблон:Math подмножества Шаблон:Mvar, в которой цвет каждого элемента Шаблон:Mvar пожмножества Шаблон:Mvar принадлежит Шаблон:Math. Тогда существует глобальная раскраска Шаблон:Math всех Шаблон:Mvar со свойством, что любое конечное множество Шаблон:Mvar имеет конечное супермножество Шаблон:Mvar, на котором Шаблон:Math и Шаблон:Math согласуются. В частности, если мы выбираем Шаблон:Mvar-раскраску для любого конечного подграфа бесконечного графа Шаблон:Mvar, тогда существует Шаблон:Mvar-раскраска графа Шаблон:Mvar, в которой каждый конечный граф имеет больший суперграф, раскраска которого согласуется с раскраской всего графа [4].

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

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

Теорему можно обобщить для случаев, когда число цветов является бесконечным кардинальным числом — если κ является Шаблон:Не переведено 5, то для любого графа G и кардинального числа μ < κ, G имеет хроматическое число, не превосходящее μ, тогда и только тогда, когда его подграфы с кардинальностью меньшей κ имеют хроматическое число, не превосходящее μ [5]. Оригинальная теорема де Брёйна — Эрдёша является частным случаем κ = ℵ0 этого обобщения, поскольку множество конечно тогда и только тогда, когда его мощность меньше ℵ0. Однако некоторые предположения, такие как строгая компактность кардинального числа множества необходимы — если обобщённая континуум-гипотеза верна, то для любого бесконечного кардинала Шаблон:Math, существует граф Шаблон:Mvar мощностью (2γ)+, такой, что хроматическое число графа Шаблон:Mvar больше Шаблон:Math, но любой подграфа графа Шаблон:Mvar, множество вершин которого имеет меньшую мощность, чем у Шаблон:Mvar, имеет хроматическое число, не превосходящее Шаблон:MathШаблон:Sfn. ЛейкШаблон:Sfn описывает бесконечные графы, удовлетворяющие обобщению теоремы де Брёйна — Эрдёша, как графы, хроматическое число которых равно наибольшему хроматическому числу строго меньших подграфов.

Примечания

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

Литература

Шаблон:Refbegin

Шаблон:Refend

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harv. Готтшальк утверждает, что его доказательство более обще, чем доказательство теоремы Радо Шаблон:Harv, которая обобщает теорему де Брёйна — Эрдёша.
  2. ↑ Шаблон:Harv; Шаблон:Harv. Дженсен и Тофт приписывает Шаблон:Не переведено 5 наблюдение, что доказательство Готтшалька проще обобщить. Сойфер (стр. 238–239) даёт то же доказательство через лемму Цорна, переоткрытое в 2005 студентом бакалавриата Дмитро Карабашем.
  3. ↑ Нэш-ВилльмсШаблон:Sfn высказывает тот же результат для теоремы о пяти цветах для счётных планарных графов, так как задача четырёх красок не была доказана, когда он публиковал свой обзор, а доказательство теоремы де Брёйна — Эрдёша, которое он дал, применимо только к счётным графам. Для обобщения на графы, в которых любой конечный подграф планарен (доказано прямо с помощью теоремы компактности Гёделя), см. Раутенберга Шаблон:Harv.
  4. ↑ Для связи леммы Радо и теоремы де Брёйна — Эрдёша см. обсуждение после теоремы A у Нэша-Вилльямса Шаблон:Harv.
  5. ↑ См. Канамори Шаблон:Harv.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Теорема_де_Брёйна_—_Эрдёша_(теория_графов)&oldid=10920165