De Bruijn-Erdősův teorém je klasický teorém teorie grafů dokázaný Palem Erdősem a Nicolaasem de Bruijnem [1] .
Pokud je toto číslo konečné, chromatické číslo nekonečného grafu se rovná největšímu chromatickému číslu ze všech jeho konečných podgrafů .
De Bruijn-Erdős teorém má několik různých důkazů, z nichž každý používá axiom výběru . De Bruijnův původní důkaz používal transfinitní indukci [2] .
Gottschalk [3] podal následující velmi krátký důkaz, založený na Tichonovově teorému kompaktnosti v topologii . Předpokládejme, že pro daný nekonečný graf G je libovolný konečný podgraf k -obarvitelný a nechť X je prostor všech k přiřazení barev k vrcholům G (bez ohledu na to, zda je dané zbarvení správné). Pak X může být považováno za součin topologických prostorů k V ( G ) , který je kompaktní podle Tichonovovy věty . Pro každý konečný podgraf F z G , nechť X F je podmnožina X sestávající z přiřazení barev, které dávají správné zbarvení F . Pak je množinový systém X F rodinou uzavřených množin s vlastností konečného průniku , takže systém má díky své kompaktnosti neprázdný průnik. Jakýkoli člen tohoto průsečíku je správným zabarvením G [4] .
Další důkaz pomocí Zornova lemmatu podal Lajos Poza a také jej citoval v tezi z roku 1951 Andrew Dirac . Je-li G nekonečný graf, ve kterém je libovolný konečný podgraf k - obarvitelný, pak podle Zornova lemmatu jde o podgraf maximálního grafu M se stejnou vlastností (graf, ke kterému nelze přidat hrany, aniž by nějaký konečný podgraf vyžadoval více než k barvy). Binární relace nesousedí v M je relací ekvivalence a třídy ekvivalence tohoto vztahu dávají k -zabarvení grafu G . Tento důkaz je však obtížnější zobecnit než důkaz pomocí lemmatu kompaktnosti [5] .
Větu lze dokázat pomocí ultrafiltrů [6] nebo nestandardní analýzy [7] . Nash-Williams [8] podal důkaz pro grafy s počitatelným počtem vrcholů na základě Koenigova lemmatu nekonečného stromu .
Všechny důkazy de Bruijn-Erdősovy věty používají axiom výběru . Existují matematické modely, ve kterých jak axiom výběru, tak de Bruijn-Erdősův teorém neplatí.
Nechť G je například nekonečný graf, ve kterém jsou všechna reálná čísla vrcholy. V G spojte jakákoli dvě reálná čísla x a y hranou, jestliže hodnota (| x − y | ± √2) je racionální číslo . Ekvivalentně v tomto grafu existují hrany mezi všemi reálnými čísly x a všemi reálnými čísly tvaru x ± (√2 + q ) , kde q je libovolné racionální číslo. Pokud se tedy dva vrcholy v G liší o faktor sudého celého čísla odmocniny ze dvou plus racionální číslo, mohou používat stejnou barvu a body lze považovat za ekvivalentní. Graf vytvořený kontrakcí třídy ekvivalence na jeden vrchol je nekonečná shoda a lze jej snadno vybarvit dvěma barvami pomocí zvoleného axiomu. Jakýkoli konečný podgraf G tedy vyžaduje dvě barvy. V Solovayově modelu , ve kterém je každá množina reálných čísel měřitelná podle Lebesguea , však G vyžaduje nekonečně mnoho barev, protože v tomto případě musí být každá barevná třída měřitelnou množinou a lze ukázat, že jakákoliv měřitelná množina reálná čísla, která neobsahují hrany G , musí mít míru nulu. V Solovayově modelu je tedy (neohraničené) chromatické číslo celého grafu G mnohem větší než chromatické číslo jeho konečných podgrafů (maximálně dva) [9] [10] .
Lze ukázat, že de Bruijn-Erdősův teorém pro spočetné grafy je ekvivalentní (v teorii aritmetiky druhého řádu ) Königovu lemmatu nekonečného stromu [11] .
Jednou z aplikací de Bruijn-Erdősovy věty je Nelson-Erdős-Hadwigerův problém na chromatickém čísle grafu jednotkové vzdálenosti euklidovské roviny . Rovinný graf má nespočetné množství vrcholů, jeden pro každý bod v rovině. Dva vrcholy jsou spojeny hranou, když je euklidovská vzdálenost mezi odpovídajícími dvěma body právě jedna. Nekonečný graf má konečné podgrafy, jako je Moserovo vřeteno , které vyžadují čtyři barvy, a je známo sedmibarevné zbarvení založené na šestiúhelníkovém obkládání roviny. Chromatické číslo roviny tedy musí patřit do množiny {4,5,6,7}, ale které z těchto čtyř čísel je skutečně chromatické, není známo. De Bruijn-Erdősův teorém ukazuje, že pro tento problém existuje graf konečných jednotek se stejným chromatickým číslem jako celá rovina, takže pokud je chromatické číslo větší než čtyři, pak lze tuto skutečnost dokázat konečnými výpočty [12 ] .
De Bruijn-Erdős teorém může být také použit k rozšíření Dilworthova teorému z konečné verze na nekonečné posety . Dilworthova věta říká, že šířka dílčího řádu (největší počet prvků v množině vzájemně nesrovnatelných prvků) se rovná minimálnímu počtu řetězců ( plně uspořádaných podmnožin), na které lze dílčí řád rozložit. Na řetězový rozklad lze nahlížet jako na zabarvení grafu nesrovnatelnosti dílčího řádu (grafu, který má vrchol pro každý prvek řádu a hranu pro každou dvojici nesrovnatelných prvků). Použitím této interpretace jako zbarvení, spolu se samostatným důkazem Dilworthovy věty pro konečné posety, lze dokázat, že nekonečný poset má konečnou šířku w právě tehdy, když jej lze rozložit na w řetězců [13] .
Stejně tak de Bruijn-Erdősův teorém rozšiřuje problém čtyř barev z konečných rovinných grafů na nekonečné rovinné grafy – jakýkoli graf, který lze nakreslit bez průsečíků v rovině, konečný nebo nekonečný, lze obarvit čtyřmi barvami. Obecněji řečeno, jakýkoli nekonečný graf, pro který je jakýkoli konečný podgraf rovinný, může být opět obarven čtyřmi barvami [14] [15]
De Bruijn-Erdősův teorém lze použít k zodpovězení Gelvinovy otázky týkající se teorému střední hodnoty pro grafová chromatická čísla — pro jakákoli dvě konečná čísla j < k a jakýkoli graf G s chromatickým číslem k existuje podgraf G s chromatickým číslem j . Abychom to viděli, najdeme konečný podgraf G se stejným chromatickým číslem, jako má G samotné , a pak jeden po druhém odebírejme vrcholy, dokud nezískáme chromatické číslo j . Případ nekonečných chromatických čísel je však složitější — s teorií množin je v souladu, že existuje graf s ℵ 2 vrcholy a chromatickým číslem ℵ 2 , ale žádný podgraf s chromatickým číslem ℵ 1 [16] [17] .
Rado [18] dokázal následující větu, kterou lze považovat za zobecnění de Bruijn-Erdősovy věty. Nechť V je nekonečná množina, například množina vrcholů v nekonečném grafu. Pro každý prvek v z V nechť cv je konečná množina barev. Navíc pro libovolnou konečnou podmnožinu S množiny V zvolíme nějaké zbarvení C S podmnožiny S , ve kterém barva každého prvku v podmnožiny S náleží c v . Pak existuje globální zabarvení χ všech V s vlastností, že jakákoli konečná množina S má konečnou nadmnožinu T , na které se χ a C T shodují. Konkrétně, pokud zvolíme k -zabarvení pro libovolný konečný podgraf nekonečného grafu G , pak existuje k -zabarvení G , ve kterém má každý konečný graf větší nadgraf, jehož zabarvení je konzistentní s vybarvením celého grafu [ 19] .
Pokud graf nemá konečné chromatické číslo, pak z de Bruijn-Erdősovy věty vyplývá, že graf musí obsahovat konečné podgrafy pro každé možné chromatické číslo. Vědci také zkoumali další podmínky na podgrafech. Například neohraničené chromatické grafy musí také obsahovat jakýkoli konečný bipartitní graf jako podgraf. Mohou však mít lichý obvod lichý lichý lichý [20] [17] .
De Bruijn-Erdősův teorém také platí přímo pro problémy s barvením hypergrafu , kde se vyžaduje, aby každý hyperedge měl vrcholy více než jedné barvy. Pokud jde o grafy, hypergraf má k -zabarvení právě tehdy, když některý z jeho konečných podhypergrafů má k -zabarvení [21] . Speciální případ teorému kompaktnosti Kurta Gödela říká, že množina výroků prvního řádu má model tehdy a jen tehdy, když model má nějaká konečná podmnožina .
Větu lze zobecnit na případy, kdy je počet barev nekonečným kardinálním číslem — je-li κ striktně kompaktní kardinální číslo , pak pro jakýkoli graf G a kardinální číslo μ < κ má G chromatické číslo nepřesahující μ právě tehdy, když jeho podgrafy s mohutností menší než κ mají chromatické číslo nepřesahující μ [22] . Původní de Bruijn-Erdősův teorém je speciálním případem κ = ℵ 0 tohoto zobecnění, protože množina je konečná právě tehdy, když je její mohutnost menší než ℵ 0 . Některé předpoklady, jako je přísná kompaktnost kardinálního čísla množiny, jsou však nutné - pokud platí hypotéza zobecněného kontinua , pak pro libovolný nekonečný kardinál γ existuje graf G mohutnosti (2 γ ) + , např. že chromatické číslo grafu G je větší než γ , ale každý podgraf graf G , jehož množina vrcholů má menší mohutnost než G , má chromatické číslo nepřesahující γ [23] . Lake [24] popisuje nekonečné grafy splňující zobecnění de Bruijn-Erdősovy věty jako grafy, jejichž chromatické číslo se rovná největšímu chromatickému počtu striktně menších podgrafů.