A de Bruijn-Erdős tétel egy klasszikus gráfelméleti tétel, amelyet Pal Erdős és Nicolaas de Bruijn bizonyított [1] .
Egy végtelen gráf kromatikus száma , ha ez a szám véges, egyenlő az összes véges részgráfja közül a legnagyobb kromatikus számmal .
A de Bruijn-Erdős tételnek több különböző bizonyítása van, mindegyik a választás axiómáját használja . De Bruijn eredeti bizonyítása transzfinit indukciót használt [2] .
Gottschalk [3] a következő nagyon rövid bizonyítást adta Tyhonov topológiás kompaktsági tétele alapján . Tegyük fel, hogy egy adott G végtelen gráfra bármely véges részgráf k -színezhető, és legyen X a G csúcsaihoz tartozó összes k szín hozzárendelés tere (függetlenül attól, hogy az adott színezés megfelelő-e). Ekkor X a k V ( G ) topológiai terek szorzatának tekinthető , amely Tyihonov tétele szerint kompakt . Legyen G minden véges F részgráfjára X F X olyan részhalmaza, amely olyan szín-hozzárendelésekből áll, amelyek F megfelelő színezését adják . Ekkor az X F halmazrendszer zárt halmazok családja véges metszéspont tulajdonsággal [ , így a rendszernek a tömörsége miatt van egy nem üres metszéspontja. Ennek a metszéspontnak bármely tagja G megfelelő színezése [4] .
A Zorn-féle lemmát használó másik bizonyítékot Poza Lajos adott, és Andrew Dirac is idézte az 1951-es dolgozatban . Ha G egy végtelen gráf, amelyben bármely véges részgráf k színezhető, akkor Zorn-lemmája szerint ez egy maximális M gráf részgráfja, amelynek ugyanaz a tulajdonsága (olyan gráf, amelyhez nem adható hozzá élek anélkül, hogy k -nál több véges részgráfot igényelne). színek). A bináris nem szomszédos reláció M -ben egy ekvivalencia reláció, és ennek a relációnak az ekvivalenciaosztályai a G gráf k színét adják . Ez a bizonyítás azonban nehezebben általánosítható, mint a tömörségi lemma [5] bizonyítása .
A tétel ultraszűrőkkel [6] vagy nem szabványos elemzéssel [7] igazolható . Nash-Williams [8] bizonyítást adott megszámlálható számú csúcsú gráfokra, Koenig végtelen fa-lemmája alapján .
A de Bruijn-Erdős tétel minden bizonyítása a választás axiómáját használja . Vannak olyan matematikai modellek, amelyekben sem a választási axióma, sem a de Bruijn-Erdős tétel nem igaz.
Legyen például G egy végtelen gráf, amelyben minden valós szám csúcs. G - ben kössünk össze tetszőleges két valós számot x és y éllel, ha az (| x − y | ± √2) érték racionális szám . Ezzel egyenértékűen ebben a gráfban élek léteznek minden x valós szám és minden x ± (√2 + q ) alakú valós szám között , ahol q bármely racionális szám. Így, ha G -ben két csúcs különbözik kettő négyzetgyökének és egy racionális számnak páros egész tényezőjével , akkor ugyanazt a színt használhatják, és a pontok egyenértékűnek tekinthetők. Az ekvivalenciaosztály egy csúcsra zsugorításával kialakított gráf végtelen egyezés , és a választott axiómával könnyen két színre színezhető. Így G bármely véges részgráfjához két szín szükséges. Azonban a Solovay modellben , amelyben minden valós számhalmaz Lebesgue mérhető , G végtelen sok színt igényel, mivel ebben az esetben minden színosztálynak mérhető halmaznak kell lennie, és kimutatható, hogy a számok bármely mérhető halmaza azoknak a valós számoknak, amelyek nem tartalmazzák G éleit, nulla mértékkel kell rendelkezniük. Így a Solovay-modellben a teljes G gráf (korlátlan) kromatikus száma sokkal nagyobb, mint véges részgráfjainak kromatikus száma (maximum kettő) [9] [10] .
Megmutatható, hogy a megszámlálható gráfokra vonatkozó de Bruijn-Erdős tétel (a másodrendű aritmetika elméletében ) ekvivalens König végtelen falemmájával [11] .
A de Bruijn-Erdős tétel egyik alkalmazása a Nelson-Erdős-Hadwiger probléma az euklideszi sík egységtávolsággráfjának kromatikus számán . Egy síkgráfnak megszámlálhatatlan számú csúcsa van, egy a sík minden pontjához. Két csúcsot egy él köt össze, ha a megfelelő két pont közötti euklideszi távolság pontosan egy. Egy végtelen gráfnak véges részgráfjai vannak, mint például a Moser-orsó , amely négy színt igényel, és ismert a sík hatszögletű csempézésén alapuló hétszínű színezés. Így a sík kromatikus számának a {4,5,6,7} halmazhoz kell tartoznia, de hogy e négy szám közül melyik valóban kromatikus szám, azt nem tudni. A de Bruijn-Erdős tétel megmutatja, hogy erre a feladatra létezik egy véges egységtávolsággráf, amelynek kromatikus száma megegyezik a teljes síkkal, így ha a kromatikus szám nagyobb négynél, akkor ez a tény véges számításokkal igazolható [12 ] .
A de Bruijn-Erdős-tétel arra is használható, hogy a Dilworth-tételt véges változatról végtelen pózokra terjesztjük ki . Dilworth tétele kimondja, hogy egy részleges sorrend (a kölcsönösen össze nem hasonlítható elemek halmazának legnagyobb száma) szélessége egyenlő azoknak a láncoknak ( teljesen rendezett részhalmazoknak) minimális számával, amelyekre egy részleges sorrendet fel lehet bontani. A láncfelbontást egy részleges rend összehasonlíthatatlansági gráfjának színezéseként tekinthetjük (olyan gráfnak, amelynek a sorrend minden eleméhez van egy csúcsa és minden összehasonlíthatatlan elempárhoz egy él). Ezt az értelmezést színezésként használva, a véges pozetekre vonatkozó Dilworth-tétel külön bizonyításával együtt, bebizonyíthatjuk, hogy egy végtelen póznak akkor és csak akkor van véges szélessége w , ha az w karakterláncokra bontható [13] .
Ugyanígy a de Bruijn-Erdős tétel is kiterjeszti a négyszín problémát a véges síkgráfokról a végtelen síkgráfokra – minden olyan gráfot, amely metszéspontok nélkül rajzolható meg a síkban, legyen véges vagy végtelen, négy színnel színezhető. Általánosságban elmondható, hogy minden végtelen gráf, amelynek bármely véges részgráfja síkbeli, ismét négy színnel színezhető [14] [15]
A de Bruijn-Erdős-tétel felhasználható Gelvin kérdésének megválaszolására a gráfkromatikus számok köztes értéktételére vonatkozóan – bármely két j < k véges számra és bármely k kromatikus számú G gráfra létezik egy részgráf G j kromatikus számmal . Ennek megtekintéséhez keressük meg G véges részgráfját, amelynek kromatikus száma megegyezik G -vel , majd egyenként távolítsuk el a csúcsokat, amíg meg nem kapjuk a j kromatikus számot . A végtelen kromatikus számok esete azonban bonyolultabb – összhangban van a halmazelmélettel, hogy létezik ℵ 2 csúcsú és ℵ 2 kromatikus számmal rendelkező gráf, de nincs ℵ 1 kromatikus számmal rendelkező részgráf [16] [17] .
Rado [18] bebizonyította a következő tételt, amely a de Bruijn-Erdős tétel általánosításának tekinthető. Legyen V egy végtelen halmaz, például egy végtelen gráf csúcsainak halmaza. V minden v elemére legyen c v véges színhalmaz. Ezenkívül a V halmaz bármely véges S részhalmazához választunk az S részhalmaz C S színezését , amelyben az S részhalmaz minden v elemének színe c v -hez tartozik . Ekkor létezik az összes V globális színezése χ azzal a tulajdonsággal, hogy bármely S véges halmaznak van T véges szuperhalmaza , amelyen χ és C T megegyezik. Konkrétan, ha egy végtelen G gráf bármely véges részgráfjához k színezést választunk , akkor létezik G-nek egy k színezése , amelyben minden véges gráfnak van egy nagyobb szupergráfja, amelynek színe összhangban van a teljes gráf színével [ 19] .
Ha a gráfnak nincs véges kromatikus száma, akkor a de Bruijn-Erdős tételből következik, hogy a gráfnak minden lehetséges kromatikus számhoz véges részgráfokat kell tartalmaznia. A kutatók az algráfok egyéb feltételeit is megvizsgálták. Például a korlátlan kromatikus gráfoknak részgráfként bármely véges kétrészes gráfot is tartalmazniuk kell. Azonban tetszőlegesen nagy páratlan kerületük lehet [20] [17] .
A de Bruijn-Erdős tétel közvetlenül vonatkozik a hipergráf színezési problémáira is , ahol minden hiperélnek egynél több színű csúcsokkal kell rendelkeznie. Ami a gráfokat illeti, egy hipergráfnak akkor és csak akkor van k színe, ha bármelyik véges részhipergráfja k színezésű [21] . Kurt Gödel kompaktsági egy speciális esete kimondja, hogy az elsőrendű utasítások halmazának akkor és csak akkor van modellje , ha bármely véges részhalmaznak van modellje.
A tétel általánosítható olyan esetekre, amikor a színek száma végtelen kardinális szám — ha κ szigorúan kompakt kardinális szám , akkor bármely G gráf és μ < κ kardinális szám esetén G kromatikus száma nem haladja meg a μ-t akkor és csak akkor, ha κ-nél kisebb számú részgráfjainak kromatikus száma nem haladja meg a μ-t [22] . Az eredeti de Bruijn-Erdős tétel ennek az általánosításnak egy speciális esete, κ = ℵ 0 , mivel egy halmaz akkor és csak akkor véges, ha a számossága kisebb, mint ℵ 0 . Szükséges azonban néhány feltételezés, mint például a halmaz bíborszámának szigorú tömörsége - ha az általánosított kontinuumhipotézis igaz, akkor bármely végtelen γ kardinálisra létezik egy (2 γ ) + számú kardinális G gráf , pl. hogy a G gráf kromatikus száma nagyobb, mint γ , de bármely G részgráfnak , amelynek csúcskészlete kisebb, mint G , kromatikus száma nem haladja meg a γ -t [23] . Lake [24] a de Bruijn-Erdős-tétel általánosítását kielégítő végtelen gráfokat olyan gráfokként írja le, amelyek kromatikus száma megegyezik a szigorúan kisebb részgráfok legnagyobb kromatikus számával.