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

Перейти к навигацииПерейти к поиску

Теорема де Брёйна — Эрдёша — теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном[1].

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

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

Замечания

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

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

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

Готтшальк[3] дал следующее очень короткое доказательство, основанное на теореме о компактности Тихонова в топологии. Предположим, что для заданного бесконечного графа G любой конечный подграф является k-раскрашиваемым, и пусть X — пространство всех назначений k цветов вершинам графа G (независимо от того, является ли данная раскраска правильной). Тогда X можно рассматривать как произведение топологических пространств kV(G), которое по теореме Тихонова компактно. Для каждого конечного подграфа F графа G, пусть XF — подмножество X, состоящее из назначений цветов, дающих правильную раскраску F. Тогда система множеств XF является семейством замкнутых множеств со свойством конечных пересечений[англ.], так что из-за компактности система имеет непустое пересечение. Любой член этого пересечения является правильной раскраской 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. Однако случай для бесконечных хроматических чисел более сложен — это согласуется с теорией множеств, что существует граф с ℵ2 вершинами и хроматическим числом ℵ2, но не имеющего подграфа c хроматическим числом ℵ1[16][17].

Обобщения

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

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

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

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

Примечания

  1. ↑ de Bruijn, Erdős, 1951.
  2. ↑ Soifer, 2008, с. 236.
  3. ↑ Gottschalk, 1951.
  4. ↑ (Jensen, Toft 1995). Готтшальк утверждает, что его доказательство более обще, чем доказательство теоремы Радо (Rado 1949), которая обобщает теорему де Брёйна — Эрдёша.
  5. ↑ (Jensen, Toft 1995); (Harzheim 2005). Дженсен и Тофт приписывает Джерту Сэбидасси[англ.] наблюдение, что доказательство Готтшалька проще обобщить. Сойфер (стр. 238–239) даёт то же доказательство через лемму Цорна, переоткрытое в 2005 студентом бакалавриата Дмитро Карабашем.
  6. ↑ Luxemburg, 1962.
  7. ↑ Hurd, Loeb, 1985.
  8. ↑ 1 2 Nash-Williams, 1967.
  9. ↑ Shelah, Soifer, 2003.
  10. ↑ Soifer, 2008, с. 541–542.
  11. ↑ Schmerl, 2000.
  12. ↑ Soifer, 2008, с. 39.
  13. ↑ Harzheim, 2005, с. 60, Theorem 5.6.
  14. ↑ Barnette, 1983.
  15. ↑ Нэш-Вилльмс[8] высказывает тот же результат для теоремы о пяти цветах для счётных планарных графов, так как задача четырёх красок не была доказана, когда он публиковал свой обзор, а доказательство теоремы де Брёйна — Эрдёша, которое он дал, применимо только к счётным графам. Для обобщения на графы, в которых любой конечный подграф планарен (доказано прямо с помощью теоремы компактности Гёделя), см. Раутенберга (Rautenberg 2010).
  16. ↑ Komjáth, 1988.
  17. ↑ 1 2 Komjáth, 2011.
  18. ↑ Rado, 1949.
  19. ↑ Для связи леммы Радо и теоремы де Брёйна — Эрдёша см. обсуждение после теоремы A у Нэша-Вилльямса (Nash-Williams 1967).
  20. ↑ Erdős, Hajnal, 1966.
  21. ↑ Soifer, 2008, с. 239.
  22. ↑ См. Канамори (Kanamori 2008).
  23. ↑ Erdős, Hajnal, 1968.
  24. ↑ Lake, 1975.

Литература

  • Wolfgang Rautenberg. A Concise Introduction to Mathematical Logic. — 3rd. — Springer-Verlag, 2010. — С. 32. — (Universitext). — ISBN 978-1-4419-1220-6. (недоступная ссылка)
  • Akihiro Kanamori. The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings. — Springer-Verlag, 2008. — (Springer Monographs in Mathematics). — ISBN 978-3-540-88866-6.
  • David Barnette. Map Coloring, Polyhedra, and the Four-Color Problem. — Mathematical Association of America, 1983. — Т. 8. — С. 160. — (Dolciani Mathematical Expositions). — ISBN 978-0-88385-309-2.
  • N. G. de Bruijn, P. Erdős. A colour problem for infinite graphs and a problem in the theory of relations // Nederl. Akad. Wetensch. Proc. Ser. A. — 1951. — Т. 54. — С. 371—373. Архивировано 10 марта 2016 года.
  • P. Erdős, A. Hajnal. On chromatic number of graphs and set-systems // Acta Mathematica Academiae Scientiarum Hungaricae. — 1966. — Т. 17. — С. 61—99. — doi:10.1007/BF02020444.
  • P. Erdős, A. Hajnal. On chromatic number of infinite graphs // Theory of Graphs (Proc. Colloq., Tihany, 1966). — New York: Academic Press, 1968. — С. 83—98.
  • W. H. Gottschalk. Choice functions and Tychonoff's theorem (англ.) // Proceedings of the American Mathematical Society. — 1951. — Vol. 2. — P. 172. — doi:10.2307/2032641.
  • Egbert Harzheim. Theorem 5.5, p. 59 // Ordered sets. — New York: Springer, 2005. — Т. 7. — (Advances in Mathematics). — ISBN 0-387-24219-8.
  • Albert E. Hurd, Peter A. Loeb. Theorem 5.14, p. 92 // An introduction to nonstandard real analysis. — Orlando, FL: Academic Press, 1985. — Т. 118. — (Pure and Applied Mathematics). — ISBN 0-12-362440-1.
  • Tommy R. Jensen, Bjarne Toft. Theorem 1, pp. 2–3 // Graph coloring problems. — New York: John Wiley & Sons Inc., 1995. — (Wiley-Interscience Series in Discrete Mathematics and Optimization). — ISBN 0-471-02865-7.
  • Péter Komjáth. Consistency results on infinite graphs // Israel Journal of Mathematics. — 1988. — Т. 61, вып. 3. — С. 285—294. — doi:10.1007/BF02772573.
  • Péter Komjáth. The chromatic number of infinite graphs—A survey // Discrete Mathematics. — 2011. — Т. 311, вып. 15. — С. 1448—1450. — doi:10.1016/j.disc.2010.11.004.
  • John Lake. A generalization of a theorem of de Bruijn and Erdős on the chromatic number of infinite graphs // Journal of Combinatorial Theory. — 1975. — Т. 18. — С. 170—174. — doi:10.1016/0095-8956(75)90044-1.
  • W. A. J. Luxemburg. A remark on a paper by N. G. de Bruijn and P. Erdős // Indagationes Mathematicae. — 1962. — Т. 24. — С. 343—345.
  • C. St. J. A. Nash-Williams. Infinite graphs—a survey // Journal of Combinatorial Theory. — 1967. — Т. 3. — С. 286—301. — doi:10.1016/s0021-9800(67)80077-2.
  • R. Rado. Axiomatic treatment of rank in infinite sets // Canadian Journal of Mathematics. — 1949. — Т. 1. — С. 337—343. — doi:10.4153/cjm-1949-031-1.
  • James H. Schmerl. Graph coloring and reverse mathematics // Mathematical Logic Quarterly. — 2000. — Т. 46, вып. 4. — С. 543—548. — doi:10.1002/1521-3870(200010)46:4<543::AID-MALQ543>3.0.CO;2-E.
  • Saharon Shelah, Alexander Soifer. Axiom of choice and chromatic number of the plane // Journal of Combinatorial Theory. — 2003. — Т. 103, вып. 2. — С. 387—391. — doi:10.1016/S0097-3165(03)00102-X.
  • Alexander Soifer. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. — New York: Springer, 2008. — ISBN 978-0-387-74640-1.. См. главу II.5 "De Bruin–Erdős reduction to finite sets and results near the lower bound", стр. 39–42 и главу V.26 "De Bruin–Erdős's theorem and its history", стр. 236–241.