Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Теорема де Брейна Ердеша класична теорема теорії графів доведена Палом Ердешем і Ніколасом де Брейном ФормулюванняХромат

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

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

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

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

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

Зауваження

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

Доведення

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

Готтшальк дав таке дуже коротке доведення, засноване на теоремі про компактність в топології. Припустимо, що для заданого нескінченного графу G будь-який скінченний підграф є k-раозфарбовуваним, і нехай X — простір усіх призначень k кольорів вершинам графу G (незалежно від того, чи є це розфарбування правильним). Тоді X можна розглядати як добуток топологічних просторів kV(G), який, за теоремою Тихонова, компактний. Для кожного скінченного підграфу F графу G нехай XF — підмножина X що складається з призначень кольорів, які дають правильне розфарбування F. Тоді система множин XF є сімейством замкнутих множин із властивістю скінченних перетинів, так що через компактності система має непорожній перетин. Будь-який член цього перетину є правильним розфарбуванням 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]) лемі Кеніга про нескінченне дерево.

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

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

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

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

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

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

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

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

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

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

Теорему можна узагальнити для випадків, коли число кольорів є нескінченним кардинальним числом — якщо κ є [en], то для будь-якого графу G і кардинального числа μ < κ, G має хроматичне число, яке не перевищує μ, тоді і тільки тоді, коли його підграфи з кардинальністю меншою від κ мають хроматичне число, яке не перевищує μ. Оригінальна теорема де Брейна — Ердеша є окремим випадком κ = ℵ0 цього узагальнення, оскільки множина скінченна тоді і тільки тоді, коли її потужність менша ід ℵ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.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Teorema de Brejna Erdesha klasichna teorema teoriyi grafiv dovedena Palom Erdeshem i Nikolasom de Brejnom FormulyuvannyaHromatichne chislo neskinchennogo grafu yaksho ce chislo skinchenne dorivnyuye najbilshomu hromatichnomu chislu sered usih jogo skinchennih pidgrafiv ZauvazhennyaEkvivalentne formulyuvannya bud yakij k kritichnij graf skinchennij Teorema zastosovuyetsya dlya rozshirennya zadachi chotiroh farb i teoremi Diluorsa dlya skinchennih grafiv i mnozhin iz chastkovim poryadkom do neskinchennih variantiv zvedennya zadachi Nelsona Erdesha Gadvigera pro hromatichne chislo ploshini do zadach na skinchennih grafah Zokrema z teoremi Bryojna Erdesha i teoremi pro chotiri farbi viplivaye sho bud yakij neskinchennij planarnij graf dopuskaye rozfarbuvannya v chotiri kolori Teoremu mozhna uzagalniti vid skinchennogo chisla koloriv do mnozhini koloriv kardinalne chislo yakoyi ye en DovedennyaTeorema de Brejna Erdesha maye kilka riznih doveden kozhne z yakih vikoristovuye aksiomu viboru Pochatkove dovedennya de Brejna vikoristovuvalo transfinitnu indukciyu Gottshalk dav take duzhe korotke dovedennya zasnovane na teoremi pro kompaktnist v topologiyi Pripustimo sho dlya zadanogo neskinchennogo grafu G bud yakij skinchennij pidgraf ye k raozfarbovuvanim i nehaj X prostir usih priznachen k koloriv vershinam grafu G nezalezhno vid togo chi ye ce rozfarbuvannya pravilnim Todi X mozhna rozglyadati yak dobutok topologichnih prostoriv kV G yakij za teoremoyu Tihonova kompaktnij Dlya kozhnogo skinchennogo pidgrafu F grafu G nehaj XF pidmnozhina X sho skladayetsya z priznachen koloriv yaki dayut pravilne rozfarbuvannya F Todi sistema mnozhin XF ye simejstvom zamknutih mnozhin iz vlastivistyu skinchennih peretiniv tak sho cherez kompaktnosti sistema maye neporozhnij peretin Bud yakij chlen cogo peretinu ye pravilnim rozfarbuvannyam G Inshe dovedennya sho vikoristovuye lemu Corna dav en a takozh naviv u tezah disertaciyi 1951 en Yaksho G neskinchennij graf u yakomu bud yakij skinchennij pidgraf ye k rozfarbovuvanim todi za lemoyu Corna vin ye pidgrafom maksimalnogo grafu M z tiyeyu zh vlastivistyu graf do yakogo ne mozhna dodati rebra bez togo shob deyakij skinchennij pidgraf ne zazhadav bilshe k koloriv Binarne vidnoshennya nesumizhnosti v M ye vidnoshennyam ekvivalentnosti i klasi ekvivalentnosti cogo vidnoshennya dayut k rozfarbuvannya grafu G Odnak ce dovedennya skladnishe uzagalniti nizh dovedennya za lemoyu pro kompaktnist Teoremu mozhna dovesti za dopomogoyu ultrafiltriv abo nestandartnogo analizu Nesh Villyams dav dovedennya dlya grafiv zi zlichennim chislom vershin gruntuyuchis na lemi Keniga Zalezhnist vid viboruVsi dovedennya teoremi de Brejna Erdesha vikoristovuyut aksiomu viboru Isnuyut modeli matematiki v yakih ne ye istinnimi ni aksioma viboru ni teorema de Brejna Erdesha Napriklad nehaj G neskinchennij graf u yakomu vershinami ye vsi dijsni chisla V G z yednayemo bud yaki dva dijsnih chisla x i y rebrom yaksho znachennya x y 2 ye racionalnim chislom Ekvivalentno v comu grafi rebra isnuyut mizh usima dijsnimi chislami x i vsima chislami viglyadu x 2 q de q bud racionalne chislo Takim chinom yaksho dvi vershini v G vidriznyayutsya na parnij cilij mnozhnik kvadratnogo korenya z 2 plyus racionalne chislo dlya nih mozhna vikoristovuvati odin kolir i tochki mozhna vvazhati ekvivalentnimi Graf utvorenij styaguvannyam klasu ekvivalentnosti v odnu vershinu ye neskinchennim paruvannyam i mozhe buti legko rozfarbovanim u dva kolori vikoristovuyuchi aksiomu viboru Takim chinom bud yakij skinchennij pidgraf grafu G vimagaye dva kolori Odnak u en v yakij kozhna mnozhina dijsnih chisel vimiryuyetsya za Lebegom G vimagaye neskinchenno bagato koloriv oskilki v comu vipadku kozhen klas koloru mayu buti vimirnoyu mnozhinoyu i mozhna pokazati sho bud yaka vimirna mnozhina dijsnih chisel sho ne mistit reber z G povinna mati miru 0 Takim chinom u modeli Soloveya neobmezhene hromatichne chislo vsogo grafu G znachno bilshe vid hromatichnogo chisla jogo skinchennih pidgrafiv maksimum 2 Mozhna pokazati sho teorema de Brejna Erdesha dlya zlichennih grafiv ekvivalentna v teoriyi en lemi Keniga pro neskinchenne derevo ZastosuvannyaRozfarbuvannya ploshini v sim koloriv i chotirikolirnij graf odinichnih vidstanej na ploshini sho daye verhnyu i nizhnyu mezhi dlya zadachi Nelsona Erdesha Gadvigera Odne iz zastosuvan teoremi de Brejna Erdesha ce zadachi Nelsona Erdesha Gadvigera pro hromatichne chislo grafu odinichnih vidstanej evklidovoyi ploshini Graf ploshini maye nezlichennu kilkist vershin po odnij na kozhnu tochku ploshini Dvi vershini pov yazani rebrom koli evklidova vidstan mizh vidpovidnimi dvoma tochkami dorivnyuye odinici Neskinchennij graf maye skinchenni pidgrafi taki yak vereteno Mozera yaki vimagayut chotiroh koloriv i vidome rozfarbuvannya v sim koloriv zasnovane na shestikutnij mozayici ploshini Takim chinom hromatichne chislo ploshini maye nalezhati mnozhini 4 5 6 7 ale yake z cih chotiroh chisel ye dijsno hromatichnim chislom nevidomo Teorema de Brejna Erdesha pokazuye sho dlya ciyeyi zadachi isnuye skinchennij graf odinichnih vidstanej z tim samim hromatichnim chislom sho j usya ploshina cilkom tak sho yaksho hromatichne chislo bilshe chotiroh to cej fakt mozhna dovesti skinchennimi obchislennyami Teoremu de Brejna Erdesha mozhna vikoristati takozh dlya rozshirennya teoremi Diluorsa vid skinchennogo variantu do neskinchennih chastkovo vporyadkovanih mnozhin Teorema Diluorsa stverdzhuye sho shirina chastkovogo poryadku najbilshe chislo elementiv u mnozhini vzayemno neporivnyannih elementiv dorivnyuye minimalnomu chislu lancyuzhkiv povnistyu vporyadkovanih pidmnozhin na yaki mozhna rozklasti chastkovij poryadok Rozkladannya na lancyuzhki mozhna rozglyadati yak rozfarbuvannya grafu neporivnyannosti chastkovogo poryadku graf sho maye vershinu dlya kozhnogo elementa poryadku i rebro dlya kozhnoyi pari neporivnyannih elementiv Vikoristovuyuchi cyu interpretaciyu yak rozfarbuvannya razom z okremim dovedennyam teoremi Diluorsa dlya skinchennih chastkovo vporyadkovanih mnozhin mozhna dovesti sho neskinchenna chastkovo vporyadkovana mnozhina maye skinchennu shirinu w todi i tilki todi koli jogo mozhna rozklasti na w lancyuzhkiv Tak samo teorema de Brejna Erdesha rozshiryuye problemu chotiroh farb zi skinchennih planarnih grafiv na neskinchenni planarni grafi bud yaki grafi yaki mozhna namalyuvati bez peretiniv na ploshini skinchenni abo neskinchenni mozhna rozfarbuvati chotirma farbami Zagalnishe bud yakij neskinchennij graf dlya yakogo bud yakij skinchennij pidgraf planarnij mozhna znovu rozfarbuvati v chotiri kolori Teoremu de Brejna Erdesha mozhna vikoristati dlya vidpovidi na pitannya en shodo teoremi pro promizhne znachennya dlya hromatichnih chisel grafiv dlya bud yakih dvoh skinchennih chisel j lt k i bud yakogo grafu G z hromatichnim chislom k isnuye pidgraf grafu G z hromatichnim chislom j Shob ce pobachiti znajdemo skinchennij pidgraf grafu G z tim samim hromatichnim chislom sho j sam G a potim vidalyatimemo vershini odnu za odnoyu poki ne otrimayemo hromatichne chislo j Odnak vipadok dlya neskinchennih hromatichnih chisel skladnishij ce uzgodzhuyetsya z teoriyeyu mnozhin sho isnuye graf z ℵ2 vershinami i hromatichnim chislom ℵ2 yakij prote ne maye pidgrafu z hromatichnim chislom ℵ1 UzagalnennyaRado doviv taku teoremu yaku mozhna rozglyadati yak uzagalnennya teoremi de Bryojna Erdesha Nehaj V mnozhina napriklad mnozhina vershin u neskinchennomu grafi Dlya kozhnogo elementa v mnozhini V nehaj cv ye skinchennoyu mnozhinoyu koloriv Krim togo dlya bud yakoyi skinchennoyi pidmnozhini S mnozhini V viberemo deyake rozfarbuvannya CS pidmnozhini S u yakomu kolir kozhnogo elementa v pidmnozhini S nalezhit cv Todi isnuye globalne rozfarbuvannya x vsih V z vlastivistyu sho bud yaka skinchenna mnozhina S maye skinchennu supermnozhinu T na yakij x i CT uzgodzhuyutsya Zokrema yaksho mi vibirayemo k rozfarbuvannya dlya bud yakogo skinchennogo pidgrafu neskinchennogo grafu G todi isnuye k rozfarbuvannya grafu G v yakomu kozhen skinchennij graf maye bilshij supergraf rozfarbuvannya yakogo uzgodzhuyetsya z rozfarbuvannyam usogo grafu Yaksho graf ne maye skinchennogo hromatichnogo chisla todi z teoremi de Brejna Erdesha viplivaye sho graf maye mistiti skinchenni pidgrafi dlya kozhnogo mozhlivogo hromatichnogo chisla Doslidniki takozh doslidzhuvali inshi umovi na pidgrafi Napriklad neobmezheni hromatichni grafi povinni takozh mistiti bud yakij skinchennij dvochastkovij graf yak pidgraf Odnak voni mozhut mati dovilno velikij neparnij obhvat Teoremu de Brejna Erdesha takozh mozhna zastosuvati bezposeredno do zadach rozfarbovuvannya gipergrafiv de potribno shob kozhne giperrebro malo vershini bilshe odnogo koloru Yak i dlya grafiv gipergraf maye k rozfarbuvannya todi i tilki todi koli bud yakij iz jogo skinchennih pidgipergrafiv maye k rozfarbuvannya Okremij vipadok teoremi pro kompaktnist Kurta Gedelya stverdzhuye sho mnozhina tverdzhen pershogo poryadku maye model todi i tilki todi koli bud yaka skinchenna pidmnozhina maye model Teoremu mozhna uzagalniti dlya vipadkiv koli chislo koloriv ye neskinchennim kardinalnim chislom yaksho k ye en to dlya bud yakogo grafu G i kardinalnogo chisla m lt k G maye hromatichne chislo yake ne perevishuye m todi i tilki todi koli jogo pidgrafi z kardinalnistyu menshoyu vid k mayut hromatichne chislo yake ne perevishuye m Originalna teorema de Brejna Erdesha ye okremim vipadkom k ℵ0 cogo uzagalnennya oskilki mnozhina skinchenna todi i tilki todi koli yiyi potuzhnist mensha id ℵ0 Odnak deyaki pripushennya taki yak stroga kompaktnist kardinalnogo chisla mnozhini neobhidni yaksho uzagalnena kontinuum gipoteza istinna to dlya bud yakogo neskinchennogo kardinalu g isnuye graf G potuzhnistyu 2g takij sho hromatichne chislo grafu G bilshe vid g ale bud yakij pidgraf grafu G mnozhina vershin yakogo maye menshu potuzhnist nizh u G maye hromatichne chislo yake ne perevishuye g Lejk opisuye neskinchenni grafi sho zadovolnyayut uzagalnennyu teoremi de Brejna Erdesha yak grafi hromatichne chislo yakih dorivnyuye najbilshomu hromatichnomu chislu strogo menshih pidgrafiv Primitkide Bruijn Erdos 1951 Soifer 2008 s 236 Gottschalk 1951 Jensen Toft 1995 Gottshalk stverdzhuye sho jogo dovedennya zagalnishe nizh dovedennya teoremi Rado Rado 1949 yaka uzagalnyuye teoremu de Brejna Erdesha Jensen Toft 1995 Harzheim 2005 Dzhensen i Toft pripisuyut en sposterezhennya sho dovedennya Gottshalka prostishe uzagalniti Sojfer stor 238 239 daye te zh dovedennya cherez lemu Corna yake perevidkriv 2005 roku student bakalavriatu Dmitro Karabash Luxemburg 1962 Hurd Loeb 1985 Nash Williams 1967 Shelah Soifer 2003 Soifer 2008 s 541 542 Schmerl 2000 Soifer 2008 s 39 Harzheim 2005 s 60 Theorem 5 6 Barnette 1983 Nesh Vilyams navodit toj samij rezultat dlya teoremi pro p yat koloriv dlya zlichennih planarnih grafiv oskilki zadacha chotiroh koloriv ne bula dovedenoyu koli vin publikuvav svij oglyad a dovedennya teoremi de Brejna Erdesha yake vin dav mozhna zastosuvati tilki do zlichennih grafiv Dlya uzagalnennya na grafi v yakih bud yakij skinchennij pidgraf planarnij dovedeno pryamo za dopomogoyu teoremi kompaktnosti Gedelya div Rautenberga Rautenberg 2010 Komjath 1988 Komjath 2011 Rado 1949 Pro zv yazok lemi Rado i teoremi de Brejna Erdesha div obgovorennya pislya teoremi A v Nesha Villyamsa Nash Williams 1967 Erdos Hajnal 1966 Soifer 2008 s 239 Div Kanamori Kanamori 2008 Erdos Hajnal 1968 Lake 1975 LiteraturaWolfgang Rautenberg A Concise Introduction to Mathematical Logic 3rd Springer Verlag 2010 S 32 Universitext ISBN 978 1 4419 1220 6 nedostupne posilannya z lyutogo 2020 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 z dzherela 27 chervnya 2021 David Barnette Map Coloring Polyhedra and the Four Color Problem Mathematical Association of America 1983 T 8 S 160 Dolciani Mathematical Expositions ISBN 978 0 88385 309 2 N G de Bruijn P Erdos A colour problem for infinite graphs and a problem in the theory of relations 1951 T 54 16 chervnya S 371 373 z dzherela 10 bereznya 2016 P Erdos A Hajnal On chromatic number of graphs and set systems Acta Mathematica Academiae Scientiarum Hungaricae 1966 T 17 16 chervnya S 61 99 DOI 10 1007 BF02020444 z dzherela 30 chervnya 2021 Procitovano 27 chervnya 2021 P Erdos A Hajnal On chromatic number of infinite graphs Theory of Graphs Proc Colloq Tihany 1966 New York Academic Press 1968 S 83 98 z dzherela 17 bereznya 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 T 7 Advances in Mathematics ISBN 0 387 24219 8 z dzherela 27 chervnya 2021 Albert E Hurd Peter A Loeb Theorem 5 14 p 92 An introduction to nonstandard real analysis Orlando FL Academic Press 1985 T 118 Pure and Applied Mathematics ISBN 0 12 362440 1 z dzherela 27 chervnya 2021 Tommy R Jensen Bjarne Toft Theorem 1 pp 2 3 Graph coloring problems New York John Wiley amp Sons Inc 1995 Wiley Interscience Series in Discrete Mathematics and Optimization ISBN 0 471 02865 7 Peter Komjath Consistency results on infinite graphs 1988 T 61 vip 3 16 chervnya S 285 294 DOI 10 1007 BF02772573 Peter Komjath The chromatic number of infinite graphs A survey 2011 T 311 vip 15 16 chervnya S 1448 1450 DOI 10 1016 j disc 2010 11 004 z dzherela 27 chervnya 2021 Procitovano 27 chervnya 2021 John Lake A generalization of a theorem of de Bruijn and Erdos on the chromatic number of infinite graphs 1975 T 18 16 chervnya S 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 Erdos 1962 T 24 16 chervnya S 343 345 C St J A Nash Williams Infinite graphs a survey 1967 T 3 16 chervnya S 286 301 DOI 10 1016 s0021 9800 67 80077 2 R Rado Axiomatic treatment of rank in infinite sets 1949 T 1 16 chervnya S 337 343 DOI 10 4153 cjm 1949 031 1 z dzherela 7 bereznya 2016 Procitovano 27 chervnya 2021 James H Schmerl Graph coloring and reverse mathematics Mathematical Logic Quarterly 2000 T 46 vip 4 16 chervnya S 543 548 DOI 10 1002 1521 3870 200010 46 4 lt 543 AID MALQ543 gt 3 0 CO 2 E Saharon Shelah Alexander Soifer Axiom of choice and chromatic number of the plane 2003 T 103 vip 2 16 chervnya S 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 ISBN 978 0 387 74640 1 Div rozdil II 5 De Bruin Erdos reduction to finite sets and results near the lower bound str 39 42 i glavu V 26 De Bruin Erdos s theorem and its history str 236 241

Дата публікації:
Топ