A de Bruijn-Erdős tétel a gráfelmélet , bizonyítja Nicolaas Govert de Bruijn és Erdős Pál , megállapítja, hogy a (bármely természetes egész szám k ) egy végtelen irányítatlan gráf, hogy egy színező által k színek, elegendő, ha az "ez a helyzet minden véges részgráfja ellenére. Más szavakkal: bármely k- kritikus (en) gráfnak (azaz bármelyik színének legalább k színe van, de az összes megfelelő algráfja k - 1 színezhető) véges számú csúcsa van.
De Bruijn eredeti bizonyítéka transzfinit indukciót használt .
Gottschalk szolgáltatott az alábbi bizonyítékokat, nagyon rövid alapuló tömörség tétel a Tychonoff a topológia . Jelölje K-vel a k színek halmazát, és legyen G = ( V , E ) grafikon. Tychonoff-tétel szerint az összes leképezés X = K V szorzata V és K között kompakt . Bármely leképezés f egy része V , hogy K , az elemek a X , amelyek egybeesnek f ezen a részén formában egy lezárt . Következésképpen, bármely véges részgráfja F a G , a beállított X F elemeinek X , amelyeknek restrikciós hogy F egy k -coloration zárva van (véges unió). Ha mindezen Fs vannak k színnel nem, mindezek X F alkotnak egy családot zárt, amelynek a tulajdonsága véges kereszteződés (a) , azaz bármilyen véges alcsalád a nem üres kereszteződés. Tömörségük miatt kereszteződésük nem üres , vagy ez a metszéspont nem más, mint a G összes k- színe .
Egy másik bizonyíték, a Zorn-lemma adta Pósa Lajos (in) , valamint a szakdolgozat PhD 1951 Gabriel Andrew Dirac . Ha bármely véges részgráfja G jelentése k színnel nem akkor, a Zorn-lemma, G egy részleges grafikon a maximális gráf M ezt a tulajdonságot. A bináris kapcsolatban a nem-szomszédsági in M jelentése ekvivalenciareláció amelynek osztályok olyan k -coloring a G . Ezt a bizonyítást azonban nehezebb általánosítani, mint a tömörségét.
A tétel ultraszűrőkkel vagy nem szabványos elemzéssel is kimutatható .
Abban a speciális esetben, ha V jelentése megszámlálható , Crispin Nash-Williams ad alapuló bizonyítást König lemma .
De Bruijn-Erdős tételének minden bizonyítéka a választott axióma valamilyen formáját használja . Ez elkerülhetetlen, mert vannak matematikai modellek , amelyek nem igazolják ezt a tételt (sem ezt az axiómát).
Például k = 2 esetén legyen G az a gráf, amelynek csúcsai a valós számok, és amelyben két x és y valós számot egy él kapcsol össze, amikor | x - y | ± √ 2 egy racionális szám , vagyis a csúcsok csatlakozik egy valós x a valós számok az űrlap x ± ( √ 2 + q ) a q racionális. Definiáljuk a G csúcsain az ekvivalencia relációt: két csúcs ekvivalens, ha különbségük egy racionális és egy négyzetgyök 2- szeresének páros egészének az összege . Így a G 2 színének két egyenértékű csúcsának azonos színűnek kell lennie. Az egyes ekvivalenciaosztályok egyetlen csúcsokká való összeszerelésével létrehozott grafikon végtelen tengelykapcsolatot képez, és a kívánt axióma segítségével könnyen 2 színű lehet. Ezért a G bármely véges részgráfja 2 színezhető. Megmutathatjuk azonban, hogy a G bármely színében bármely monokróm Lebesgue-mérhető halmaz szükségképpen nulla mértékű. Ebből következik, hogy a Solovay (in) modelljében (amelyben bármely valós szám halmaz mérhető) G-t csak a színek végtelenje színezheti.
A megszámlálható gráfok De Bruijn-Erdős-tétele másodrendű számtannal egyenértékű König lemmájával.
Egy alkalmazás a De Bruijn-Erdős tétel vonatkozik Hadwiger-Nelson probléma a kromatikus száma a távolság egység grafikon az euklideszi sík (csúcsai azok a pontok a síkon és két csúcsot él köt össze, amikor a euklideszi távolság értéke 1). Néhány algráfja, például a Moser orsó , 4 színnél kevesebb színezhetõ. Maga a grafikon 7 színű, a sík hatszögletű tessellációján alapul. Ezért a kromatikus szám ebben a grafikonban a négy egész szám 4, 5, 6 vagy 7 egyike, de nem ismert, hogy melyik. A De Bruijn-Erdős tétel azonban azt mutatja, hogy létezik egy véges távolság-egység gráf, amelynek kromatikus száma megegyezik az egész sík kromatikus számával, tehát ha ez utóbbi szigorúan nagyobb, mint 4, akkor ezt a tényt véges számítással lehet bizonyítani.
A De Bruijn-Erdős tétel is lehet használni, hogy kiterjesszék Dilworth tétele , a (részben) rendezett halmazok , a véges esetben a végtelen esetben. Ez a tétel megállapítja, hogy bármely véges sorrend szélessége (vagyis az antilánc maximális mérete ) megegyezik a láncokban lévő partíció minimális méretével . A láncokban lévő partíció értelmezhető a sorrend összehasonlíthatatlansági grafikonjának színezéseként (az a gráf, amelynek csúcsai a rendezett halmaz elemei, és az élek összekapcsolják a nem összehasonlítható elemek párját). Ebből az értelmezésből és Dilworth tételéből bebizonyíthatjuk De Bruijn-Erdős tételnek köszönhetően, hogy a w szélességének kisebb vagy egyenlő, mint bármely széletlen végtelen sorrendje w diszjunkt láncok egyesülése .
Hasonlóképpen, a De Bruijn-Erdős tétel lehetővé teszi, hogy meghosszabbítja a tétel a négy szín , a síkgráfok , a véges esetben a végtelen esetben: bármely végtelen sík gráf, vagy még általánosabban bármely végtelen gráf, amelynek véges részgráfok planáris, 4 színnel színezhető.
Azt is fel lehet használni, hogy válaszolni egy kérdésre a Fred Galvin (en) a „ tétel a közbenső értékek a kromatikus számát grafikonok”: bármilyen gráf G kromatikus száma k , és bármely egész szám j <k , G egy al- kromatikus számgrafikon j . Az egyik megtalálásához elegendő, ha a k kromatikus szám G véges részgráfját vesszük, és egyesével töröljük a csúcsokat, amíg az algráf kromatikus száma el nem éri a j értéket . A helyzet azonban a végtelen kromatikus szám sokkal bonyolultabb: halmazelmélet van összhangban azzal, hogy létezik egy kromatikus szám grafikon (és a csúcsok száma) és egyenlő ℵ 2 , mivel nincs több részgráf. Kromatikus egyenlő ℵ 1 .
Richard Rado (1949-ben) bemutatta a következő tételt, amely általánosítja és tisztázza De Bruijn-Erdősét. Let V legyen végtelen halmaz, és minden egyes elem v az V , véges c v színben. Úgy döntünk, bármely véges része S a V , térkép C S A S a beállított színek, úgy, hogy a szín az egyes elemek v az S tartozik c v . Ekkor létezik egy V egész számban definiált χ térkép , úgy, hogy bármely S véges rész bekerüljön egy olyan véges T részbe , amelyen χ és C T egybeesnek.
Ha egy G gráf kromatikus száma végtelen, akkor a De Bruijn-Erdős tétel azt sugallja, hogy G minden j egész számra tartalmaz egy olyan algráfot, amelynek kromatikus száma j (vö. Fenti közbenső értéktétel ). A kutatók más következményeket is vizsgáltak a G részgráfjaira ; például G- nek tartalmaznia kell minden véges kétoldalas gráfot is részgráfként. G-nek azonban lehet önkényesen nagy páratlan cellája, és ezért a nem kétoldalú gráfok bármely véges halmazához létezik olyan G, amelynek algráfja nem tartozik ebbe a halmazba.
A De Bruijn-Erdős tétel közvetlenül vonatkozik a hipergráfok színezési problémáira is , ahol azt kérjük, hogy az egyes hiperéleknél a csúcsok ne egyformák legyenek: mint a gráfoknál, a hipergráf akkor is k- színezhető, ha mindegyik véges al-hipergráfjai közül az. Ez egy speciális esete a tömörség tétel a Gödel , ahol egy sor elsőrendű állítások egy modell , ha minden egyes elkészült részeit egy.
Általánosíthatjuk a tételt olyan helyzetekre is, ahol a színek száma végtelen bíboros : ha κ erősen kompakt bíboros (in), akkor bármely G gráf és bármely μ <κ bíboros esetében a G kromatikus száma kisebb, mint egyenlő μ-vel, és csak akkor, ha ugyanaz igaz minden részgráfjára, szigorúan kisebb mint κ-os kardinalitással. Az eredeti De Bruijn-Erdős tétel az általánosítás κ = ℵ 0 esete . De ebben az esetben a feltételezést, mint hogy az erős tömörsége κ: az általánosított kontinuum hipotézist , minden végtelen bíboros γ , létezik egy gráf G bíboros (2 γ ) + , amelynek kromatikus szám szigorúan nagyobb, mint γ , de amelynek minden a grafikonnál szigorúan kisebb (csúcsok számában) algráfok kromatikus száma kisebb vagy egyenlő γ-val . Lake végtelen grafikonokat jellemez, amelyekre a De Bruijn-Erdős tétel általánosítása igaz, abban az értelemben, hogy kromatikus számuk megegyezik a szigorúan kisebb részgráfok kromatikus számának maximumával.