De Bruijn – Erdősova věta (teorie grafů) - De Bruijn–Erdős theorem (graph theory)

v teorie grafů, De Bruijn – Erdősova věta se týká zbarvení grafu z nekonečný graf ke stejnému problému v jeho konečné podobě podgrafy. Uvádí se v něm, že když lze obarvit všechny konečné podgrafy ${ displaystyle c}$ barvy, totéž platí pro celý graf. Věta byla prokázána Nicolaas Govert de Bruijn a Paul Erdős  (1951 ), po kom je pojmenován.

Věta De Bruijn – Erdős má několik různých důkazů, všechny nějakým způsobem závisejí na axiom volby. Mezi jeho aplikace patří rozšíření čtyřbarevná věta a Dilworthova věta z konečných grafů a částečně objednané sady na nekonečné a snižování Hadwiger – Nelsonův problém na chromatické číslo roviny k problému o konečných grafech. Lze ji zobecnit od konečného počtu barev k sadám barev, jejichž mohutnost je silně kompaktní kardinál.

Definice a prohlášení

An neorientovaný graf je matematický objekt skládající se z množiny vrcholy a sada hrany které spojují páry vrcholů. Dva vrcholy spojené s každou hranou se nazývají její koncové body. Graf je konečný, když se tvoří jeho vrcholy a hrany konečné množiny a nekonečně jinak. A zbarvení grafu přidružuje každý vrchol k barvě čerpané ze sady barev takovým způsobem, že každá hrana má ve svých koncových bodech dvě různé barvy. Častým cílem v barvení grafů je minimalizovat celkový počet použitých barev; the chromatické číslo grafu je tento minimální počet barev.^[1] The čtyřbarevná věta uvádí, že každý konečný graf, který lze nakreslit bez křížení v Euklidovské letadlo potřebuje maximálně čtyři barvy; některé grafy se složitější konektivitou však vyžadují více než čtyři barvy.^[2] Je to důsledek axiom volby že chromatické číslo je dobře definované pro nekonečné grafy, ale pro tyto grafy může být samotné chromatické číslo nekonečné základní číslovka.^[3]

A podgraf grafu je další graf získaný z podmnožiny jeho vrcholů a podmnožiny jeho hran. Pokud je větší graf zbarven, lze stejné zabarvení použít i pro podgraf. Proto nemůže být chromatické číslo podgrafu větší než chromatické číslo celého grafu. De Bruijn – Erdősova věta se týká chromatických čísel nekonečných grafů a ukazuje, že (opět za předpokladu axiomu výběru) je lze vypočítat z chromatických čísel jejich konečných podgrafů. Uvádí, že pokud jsou chromatická čísla konečných podgrafů grafu ${ displaystyle G}$ mít konečnou maximální hodnotu ${ displaystyle c}$, pak chromatický počet ${ displaystyle G}$ sám o sobě je přesně ${ displaystyle c}$. Na druhou stranu, pokud není konečný horní hranice o chromatických počtech konečných podgrafů ${ displaystyle G}$, pak chromatický počet ${ displaystyle G}$ sám o sobě musí být nekonečný.^[4]

Aplikace

Původní motivací Erdőse při studiu tohoto problému bylo rozšířit teorém z konečných na nekonečné grafy, že kdykoli má graf orientace s konečným maximálním výstupem ${ displaystyle k}$, má také ${ displaystyle (2k + 1)}$-zbarvení. U konečných grafů to následuje, protože takové grafy mají vždy maximálně vrchol stupně ${ displaystyle 2k}$, které lze obarvit jedním z ${ displaystyle 2k + 1}$ barvy poté, co jsou všechny zbývající vrcholy vybarveny rekurzivně. Nekonečné grafy s takovou orientací nemají vždy vrchol nízkého stupně (například Bethe mřížky mít ${ displaystyle k = 1}$ ale libovolně velký minimální stupeň), takže tento argument vyžaduje, aby byl graf konečný. Ale De Bruijn – Erdőova věta ukazuje, že a ${ displaystyle (2k + 1)}$-barvení existuje i pro nekonečné grafy.^[5]

Sedmibarevné letadlo a čtyřbarevné Moser vřeteno nakreslen jako graf jednotkové vzdálenosti v rovině, poskytující horní a dolní mez pro Hadwiger – Nelsonův problém.

Další aplikace věty De Bruijn – Erdős je pro Hadwiger – Nelsonův problém, který se ptá, kolik barev je potřeba k vybarvení bodů Euklidovské letadlo takže každé dva body, které jsou od sebe vzdálené, mají různé barvy. Tohle je zbarvení grafu problém pro nekonečný graf, který má vrchol pro každý bod roviny a hranu pro každé dva body, jejichž Euklidovská vzdálenost je přesně jedna. Podgrafy tohoto grafu se nazývají grafy jednotkové vzdálenosti. Sedmimístný graf vzdálenosti jednotek, Moser vřeteno, vyžaduje čtyři barvy; v roce 2018 byly nalezeny mnohem větší grafy vzdálenosti jednotek, které vyžadují pět barev.^[6] Celý nekonečný graf má známé zbarvení se sedmi barvami na základě hexagonálního obkladu roviny. Proto musí být chromatické číslo roviny buď 5, 6 nebo 7, ale není známo, které z těchto tří čísel je správná hodnota. De Bruijn – Erdősova věta ukazuje, že pro tento problém existuje graf vzdálenosti mezi konečnými jednotkami se stejným chromatickým číslem jako celá rovina, takže pokud je chromatické číslo větší než pět, lze tuto skutečnost dokázat konečným výpočtem.^[7]

K rozšíření lze také použít De Bruijn – Erdősovu větu Dilworthova věta od konečných po nekonečné částečně objednané sady. Dilworthova věta uvádí, že šířka dílčího řádu (maximální počet prvků v sadě vzájemně neporovnatelných prvků) se rovná minimálnímu počtu řetězců (zcela objednané podmnožiny), do kterých lze rozdělit dílčí pořadí. Rozdělení do řetězců lze interpretovat jako zbarvení graf neporovnatelnosti částečné objednávky. Toto je graf s vrcholem pro každý prvek řádu a hranou pro každou dvojici neporovnatelných prvků. Pomocí této interpretace zbarvení spolu se samostatným důkazem Dilworthovy věty pro konečné částečně uspořádané množiny je možné dokázat, že nekonečná částečně uspořádaná množina má konečnou šířku w právě když má oddíl do w řetězy.^[8]

Stejným způsobem rozšiřuje De Bruijn – Erdősova věta čtyřbarevná věta od konečných rovinných grafů po nekonečné rovinné grafy. Každý konečný rovinný graf může být obarven čtyřmi barvami čtyřbarevnou větou. Věta De Bruijn – Erdős pak ukazuje, že každý graf, který lze nakreslit bez křížení v rovině, konečný nebo nekonečný, lze obarvit čtyřmi barvami. Obecněji řečeno, každý nekonečný graf, pro který jsou všechny konečné podgrafy rovinné, může být opět čtyřbarevný.^[9]

Důkazy

Byl použit původní důkaz De Bruijn – Erdősovy věty od De Bruijna transfinitní indukce.^[10]

Gottschalk (1951) poskytl následující velmi krátký důkaz na základě Tychonoff je věta o kompaktnosti v topologii. Předpokládejme, že pro daný nekonečný graf G, každý konečný podgraf je k-barevné a nechte X být prostorem všech úkolů k barvy k vrcholům G (bez ohledu na to, zda tvoří platné zbarvení). Pak X může být uvedena topologie jako a produktový prostor k^PROTI(G), kde PROTI(G) označuje množinu vrcholů grafu. Podle Tychonoffovy věty je tento topologický prostor kompaktní. Pro každý konečný podgraf F z G, nechť X_F být podmnožinou X skládající se z přiřazení barev, které platně zabarvují F. Pak systém sad X_F je rodina uzavřené sady s vlastnost konečné křižovatky, takže díky kompaktnosti má neprázdnou křižovatku. Každý člen této křižovatky má platné zbarvení G.^[11]

Použití jiného důkazu Zornovo lemma byl dán Lajos Pósa, a také v roce 1951 Ph.D. práce z Gabriel Andrew Dirac. Li G je nekonečný graf, ve kterém je každý konečný podgraf k-barevný, pak podle Zornova lematu je to podgraf a maximální graf M se stejnou vlastností (ten, ke kterému nelze přidat další hrany, aniž by způsobil, že nějaký konečný podgraf vyžaduje více než k barvy). The binární relace neadjacence v M je vztah ekvivalence a jeho třídy rovnocennosti poskytují a k-barvení G. Tento důkaz je však obtížnější zobecnit než důkaz kompaktnosti.^[12]

Věta může být také prokázána pomocí ultrafiltry^[13] nebo nestandardní analýza.^[14] Nash-Williams (1967) poskytuje důkaz pro grafy se spočetným počtem vrcholů založených na Kőnigovo nekonečné lema.

Závislost na výběru

Všechny důkazy věty De Bruijn – Erdős používají nějakou formu axiom volby. Určitá forma tohoto předpokladu je nezbytná, protože existují modely matematiky, ve které jsou jak axiom výběru, tak De De Bruijn – Erdősova věta nepravdivé. Přesněji, Mycielski (1961) ukázal, že věta je důsledkem Booleova primární věta o ideálu vlastnost, kterou implikuje axiom volby, ale slabší než plný axiom volby, a Läuchli (1971) ukázal, že věta De Bruijn – Erdős a booleovská primární věta o ideálu jsou ekvivalentní v axiomatické síle.^[15] Teorém De Bruijn – Erdős pro spočetné grafy lze také ukázat jako ekvivalentní v axiomatické síle, v rámci teorie aritmetika druhého řádu, na Kőnigovo nekonečné lema.^[16]

Pro protiklad k teorému v modelech teorie množin bez výběru, nechť G být nekonečný graf, ve kterém vrcholy představují všechna možná reálná čísla. v G, spojte každé dvě reálná čísla X a y o hranu, kdykoli jedna z hodnot (|X − y| ± √2) je racionální číslo. Ekvivalentně v tomto grafu existují hrany mezi všemi reálnými čísly X a všechna reálná čísla formuláře X ± (√2 + q), kde q je jakékoli racionální číslo. Každá cesta v tomto grafu, počínaje jakýmkoli reálným číslem X, střídá čísla, která se liší od X racionálním číslem plus sudým násobkem √2a čísla, která se liší od X racionálním číslem plus lichým násobkem √2.Tato alternace brání G aby obsahoval libovolné liché délky, takže každý z jeho konečných podgrafů vyžaduje pouze dvě barvy. Nicméně v Solovayův model ve kterém je každá sada reálných čísel Lebesgue měřitelný, G vyžaduje nekonečně mnoho barev, protože v tomto případě musí být každá barevná třída měřitelnou sadou a je možné ukázat, že každá měřitelná sada reálných čísel bez hran v G musí mít míru nula. Proto je v Solovayově modelu (nekonečný) chromatický počet všech G je mnohem větší než chromatický počet jeho konečných podgrafů (maximálně dva).^[17]

Zobecnění

Rado (1949) dokazuje následující větu, kterou lze považovat za zobecnění věty De Bruijn – Erdős. Nechat PROTI být nekonečnou množinou, například množinou vrcholů v nekonečném grafu. Pro každý prvek proti z PROTI, nechť C_proti být konečnou sadou barev. Navíc pro každou konečnou podmnožinu S z PROTI, vyberte nějaké konkrétní zbarvení C_S z S, ve kterém je barva každého prvku proti z S patří C_proti. Pak existuje globální zbarvení χ ze všech PROTI s vlastností, kterou každá konečná množina S má konečnou nadmnožinu T na kterých χ a C_T souhlasit. Zejména pokud zvolíme a k-barvení pro každý konečný podgraf nekonečného grafu G, pak existuje k-barvení G ve kterém má každý konečný graf větší supergraf, jehož zbarvení souhlasí s vybarvením celého grafu.^[18]

Pokud graf nemá konečné chromatické číslo, pak De Bruijn – Erdősova věta znamená, že musí obsahovat konečné podgrafy všech možných konečných chromatických čísel. Vědci také zkoumali další podmínky na podgrafech, které jsou v tomto případě nuceny vyskytnout. Například neomezeně chromatické grafy musí také obsahovat všechny možné konečné bipartitní graf jako podgraf. Mohou však být libovolně velké zvláštní obvod, a proto se mohou vyhnout jakékoli konečné sadě nebipartitních podgrafů.^[19]

Věta De Bruijn – Erdős platí také přímo pro hypergraf problémy s barvením, kde jeden vyžaduje, aby každý hyperedge měl vrcholy více než jedné barvy. Pokud jde o grafy, hypergraf má a k-barvení právě tehdy, pokud má každý z jeho konečných subhypergrafů a k-zbarvení.^[20] Jedná se o speciální případ věta o kompaktnosti z Kurt Gödel s tím, že soubor první objednávka věty má a Modelka jen a jen pokud každý konečný podmnožina z toho má model.^[21] Přesněji řečeno, De Bruijn – Erdősova věta může být interpretována jako kompaktnost prvního řádu struktur jejichž nelogické hodnoty jsou jakákoli konečná sada barev a jejichž jediným predikátem na těchto hodnotách je nerovnost.^[22]

Věta může být také zobecněna na situace, ve kterých je počet barev nekonečný základní číslovka. Li κ je silně kompaktní kardinál, pak pro každý graf G a základní číslo μ < κ, G má maximálně chromatické číslo μ právě tehdy, když každý z jejích podgrafů mohutnosti menší než κ má maximálně chromatické číslo μ.^[23] Jedná se o původní větu De Bruijn – Erdős κ = ℵ₀ této generalizace, protože množina je konečná právě tehdy, pokud je její mohutnost menší než ℵ₀. Je však nezbytný některý předpoklad, jako je silně kompaktní kardinál: pokud zobecněná hypotéza kontinua je pravda, pak pro každého nekonečného kardinála y, existuje graf G mohutnosti (2^y)⁺ tak, že chromatický počet G je větší než y, ale takový, že každý podgraf z G jehož sada vrcholů má menší sílu než G má maximálně chromatické číslo y.^[24] Lake (1975) charakterizuje nekonečné grafy, které poslouchají zobecnění věty De Bruijn – Erdős, v tom, že jejich chromatický počet se rovná maximálnímu chromatickému počtu jejich přísně menších podgrafů.

Poznámky

Reference