Теорема де Брейна — Ердеша (теорія графів)

Теорема де Брейна — Ердеша — класична теорема теорії графів доведена Палом Ердешем і Ніколасом де Брейном.

Формулювання

Хроматичне число нескінченного графу, якщо це число скінченне, дорівнює найбільшому хроматичному числу серед усіх його скінченних підграфів.

Зауваження

• Еквівалентне формулювання: будь-який k-критичний граф скінченний.
• Теорема застосовується для розширення задачі чотирьох фарб і теореми Ділуорса для скінченних графів і множин із частковим порядком до нескінченних варіантів, зведення задачі Нельсона — Ердеша — Гадвігера про хроматичне число площини до задач на скінченних графах.
  • Зокрема, з теореми Брёйна — Ердеша і теореми про чотири фарби випливає, що будь-який нескінченний планарний граф допускає розфарбування в чотири кольори.
• Теорему можна узагальнити від скінченного числа кольорів до множини кольорів, кардинальне число якої є ^[en].

Доведення

Теорема де Брейна — Ердеша має кілька різних доведень, кожне з яких використовує аксіому вибору. Початкове доведення де Брейна використовувало трансфінітну індукцію.

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

Інше доведення, що використовує лему Цорна, дав ^[en], а також навів у тезах дисертації (1951) ^[en]. Якщо G — нескінченний граф, у якому будь-який скінченний підграф є k-розфарбовуваним, тоді, за лемою Цорна, він є підграфом максимального графу M з тією ж властивістю (граф, до якого не можна додати ребра без того, щоб деякий скінченний підграф не зажадав більше k кольорів). Бінарне відношення несуміжності в M є відношенням еквівалентності і класи еквівалентності цього відношення дають k-розфарбування графу G. Однак це доведення складніше узагальнити, ніж доведення за лемою про компактність.

Теорему можна довести за допомогою (ультрафільтрів) або нестандартного аналізу. Неш-Вілльямс дав доведення для графів зі зліченним числом вершин, ґрунтуючись на (лемі Кеніга).

Залежність від вибору

Всі доведення теореми де Брейна — Ердеша використовують аксіому вибору. Існують моделі математики, в яких не є істинними ні аксіома вибору, ні теорема де Брейна — Ердеша.

Наприклад, нехай G — нескінченний граф, у якому вершинами є всі дійсні числа. В G з'єднаємо будь-які два дійсних числа x і y ребром, якщо значення (|x − y| ± √2) є раціональним числом. Еквівалентно, в цьому графі, ребра існують між усіма дійсними числами x і всіма числами вигляду x ± (√2 + q) де q — будь раціональне число. Таким чином, якщо дві вершини в G відрізняються на парний цілий множник квадратного кореня з 2 плюс раціональне число, для них можна використовувати один колір і точки можна вважати еквівалентними. Граф, утворений стягуванням класу еквівалентності в одну вершину, є нескінченним паруванням і може бути легко розфарбованим у два кольори, використовуючи аксіому вибору. Таким чином, будь-який скінченний підграф графу G вимагає два кольори. Однак у ^[en], в якій кожна множина дійсних чисел вимірюється за Лебегом, G вимагає нескінченно багато кольорів, оскільки в цьому випадку кожен клас кольору маю бути вимірною множиною, і можна показати, що будь-яка вимірна множина дійсних чисел, що не містить ребер з G, повинна мати міру 0. Таким чином, у моделі Соловея, (необмежене) хроматичне число всього графу G значно більше від хроматичного числа його скінченних підграфів (максимум 2).

Можна показати, що теорема де Брейна — Ердеша для зліченних графів еквівалентна (в теорії ^[en]) лемі Кеніга про нескінченне дерево.

Застосування

Розфарбування площини в сім кольорів і чотириколірний граф одиничних відстаней на площині, що дає верхню і нижню межі для задачі Нельсона — Ердеша — Гадвігера.

Одне із застосувань теореми де Брейна — Ердеша — це задачі Нельсона — Ердеша — Гадвігера про хроматичне число графу одиничних відстаней евклідової площини. Граф площини має незліченну кількість вершин, по одній на кожну точку площини. Дві вершини пов'язані ребром, коли евклідова відстань між відповідними двома точками дорівнює одиниці. Нескінченний граф має скінченні підграфи, такі як (веретено Мозера), які вимагають чотирьох кольорів, і відоме розфарбування в сім кольорів, засноване на шестикутній мозаїці площини. Таким чином, хроматичне число площини має належати множині {4,5,6,7}, але яке з цих чотирьох чисел є дійсно хроматичним числом, невідомо. Теорема де Брейна — Ердеша показує, що для цієї задачі існує скінченний граф одиничних відстаней з тим самим хроматичним числом, що й уся площина цілком, так що, якщо хроматичне число більше чотирьох, то цей факт можна довести скінченними обчисленнями.

Теорему де Брейна — Ердеша можна використати також для розширення теореми Ділуорса від скінченного варіанту до нескінченних частково впорядкованих множин. Теорема Ділуорса стверджує, що ширина часткового порядку (найбільше число елементів у множині взаємно непорівнянних елементів) дорівнює мінімальному числу ланцюжків (повністю впорядкованих підмножин), на які можна розкласти частковий порядок. Розкладання на ланцюжки можна розглядати як розфарбування (графу непорівнянності) часткового порядку (граф, що має вершину для кожного елемента порядку і ребро для кожної пари непорівнянних елементів). Використовуючи цю інтерпретацію як розфарбування, разом з окремим доведенням теореми Ділуорса для скінченних частково впорядкованих множин, можна довести, що нескінченна частково впорядкована множина має скінченну ширину w тоді і тільки тоді, коли його можна розкласти на w ланцюжків.

Так само, теорема де Брейна — Ердеша розширює проблему чотирьох фарб зі скінченних планарних графів на нескінченні планарні графи — будь-які графи, які можна намалювати без перетинів на площині, скінченні або нескінченні, можна розфарбувати чотирма фарбами. Загальніше, будь-який нескінченний граф, для якого будь-який скінченний підграф планарний, можна знову розфарбувати в чотири кольори.

Теорему де Брейна — Ердеша можна використати для відповіді на питання ^[en] щодо теореми про проміжне значення для хроматичних чисел графів — для будь-яких двох скінченних чисел j < k і будь-якого графу G з хроматичним числом k існує підграф графу G з хроматичним числом j. Щоб це побачити, знайдемо скінченний підграф графу G з тим самим хроматичним числом, що й сам G, а потім видалятимемо вершини одну за одною, поки не отримаємо хроматичне число j. Однак, випадок для нескінченних хроматичних чисел складніший — це узгоджується з теорією множин, що існує граф з ℵ₂ вершинами і хроматичним числом ℵ₂, який проте не має підграфу з хроматичним числом ℵ₁.

Узагальнення

Радо довів таку теорему, яку можна розглядати як узагальнення теореми де Брёйна — Ердеша. Нехай V — множина, наприклад, множина вершин у нескінченному графі. Для кожного елемента v множини V нехай c_v є скінченною множиною кольорів. Крім того, для будь-якої скінченної підмножини S множини V виберемо деяке розфарбування C_S підмножини S у якому колір кожного елемента v підмножини S належить c_v. Тоді існує глобальне розфарбування χ всіх V з властивістю, що будь-яка скінченна множина S має скінченну супермножину T на якій χ і C_T узгоджуються. Зокрема, якщо ми вибираємо k-розфарбування для будь-якого скінченного підграфу нескінченного графу G тоді існує k-розфарбування графу G в якому кожен скінченний граф має більший суперграф, розфарбування якого узгоджується з розфарбуванням усього графу.

Якщо граф не має скінченного хроматичного числа, тоді з теореми де Брейна — Ердеша випливає, що граф має містити скінченні підграфи для кожного можливого хроматичного числа. Дослідники також досліджували інші умови на підграфи. Наприклад, необмежені хроматичні графи повинні також містити будь-який скінченний двочастковий граф як підграф. Однак вони можуть мати довільно великий непарний обхват.

Теорему де Брейна — Ердеша також можна застосувати безпосередньо до задач розфарбовування гіперграфів, де потрібно, щоб кожне гіперребро мало вершини більше одного кольору. Як і для графів, гіперграф має k-розфарбування тоді і тільки тоді, коли будь-який із його скінченних підгіперграфів має k-розфарбування. Окремий випадок (теореми про компактність) Курта Геделя стверджує, що множина тверджень першого порядку має модель тоді і тільки тоді, коли будь-яка скінченна підмножина має модель.

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

Примітки

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). Дженсен і Тофт приписують ^[en] спостереження, що доведення Готтшалька простіше узагальнити. Сойфер (стор. 238—239) дає те ж доведення через лему Цорна, яке перевідкрив 2005 року студент бакалавріату Дмитро Карабаш.
6. Luxemburg, 1962.
7. Hurd, Loeb, 1985.
8. 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. Неш-Вільямс наводить той самий результат для теореми про п'ять кольорів для зліченних планарних графів, оскільки задача чотирьох кольорів не була доведеною, коли він публікував свій огляд, а доведення теореми де Брейна — Ердеша, яке він дав, можна застосувати тільки до зліченних графів. Для узагальнення на графи, в яких будь-який скінченний підграф планарний (доведено прямо за допомогою теореми компактності Геделя), див. Раутенберга (Rautenberg, 2010).
16. Komjáth, 1988.
17. 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) — .^{[недоступне посилання з лютого 2020]}
• Akihiro Kanamori. The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings. — Springer-Verlag, 2008. — (Springer Monographs in Mathematics) — . з джерела 27 червня 2021
• David Barnette. Map Coloring, Polyhedra, and the Four-Color Problem. — Mathematical Association of America, 1983. — Т. 8. — С. 160. — (Dolciani Mathematical Expositions) — .
• N. G. de Bruijn, P. Erdős. A colour problem for infinite graphs and a problem in the theory of relations // . — 1951. — Т. 54 (16 червня). — С. 371—373. з джерела 10 березня 2016.
• P. Erdős, A. Hajnal. On chromatic number of graphs and set-systems // Acta Mathematica Academiae Scientiarum Hungaricae. — 1966. — Т. 17 (16 червня). — С. 61—99. — DOI:10.1007/BF02020444. з джерела 30 червня 2021. Процитовано 27 червня 2021.
• 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. з джерела 17 березня 2022
• W. H. Gottschalk. Choice functions and Tychonoff's theorem // . — 1951. — Vol. 2 (16 June). — P. 172. — DOI:10.2307/2032641.
• Egbert Harzheim. Theorem 5.5, p. 59 // Ordered sets. — New York : Springer, 2005. — Т. 7. — (Advances in Mathematics) — . з джерела 27 червня 2021
• 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) — . з джерела 27 червня 2021
• 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) — .
• Péter Komjáth. Consistency results on infinite graphs // . — 1988. — Т. 61, вип. 3 (16 червня). — С. 285—294. — DOI:10.1007/BF02772573.
• Péter Komjáth. The chromatic number of infinite graphs—A survey // . — 2011. — Т. 311, вип. 15 (16 червня). — С. 1448—1450. — DOI:10.1016/j.disc.2010.11.004. з джерела 27 червня 2021. Процитовано 27 червня 2021.
• John Lake. A generalization of a theorem of de Bruijn and Erdős on the chromatic number of infinite graphs // . — 1975. — Т. 18 (16 червня). — С. 170—174. — (Series B). — 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 // . — 1962. — Т. 24 (16 червня). — С. 343—345.
• C. St. J. A. Nash-Williams. Infinite graphs—a survey // . — 1967. — Т. 3 (16 червня). — С. 286—301. — DOI:10.1016/s0021-9800(67)80077-2.
• R. Rado. Axiomatic treatment of rank in infinite sets // . — 1949. — Т. 1 (16 червня). — С. 337—343. — DOI:10.4153/cjm-1949-031-1. з джерела 7 березня 2016. Процитовано 27 червня 2021.
• James H. Schmerl. Graph coloring and reverse mathematics // Mathematical Logic Quarterly. — 2000. — Т. 46, вип. 4 (16 червня). — С. 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 // . — 2003. — Т. 103, вип. 2 (16 червня). — С. 387—391. — (Series A). — 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. — .. Див. розділ 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.