Wikipédia

De Bruijn–Erdős-tétel (gráfelmélet)

gráfelméleti tétel
Ez a közzétett változat, ellenőrizve: 2024. február 24.
Ez a szócikk a végtelen gráfok színezésével foglalkozik. A véges számú pont által meghatározott egyenesek számához lásd: de Bruijn–Erdős-tétel (illeszkedési geometria)

A matematika, azon belül a gráfelmélet területén a de Bruijn–Erdős-tétel, amit először Nicolaas Govert de Bruijn és Erdős Pál igazolt, azt állítja, hogy a végtelen gráf kromatikus száma, amennyiben az véges, megegyezik a véges részgráfjainak kromatikus számai közül a legnagyobbal. A tétel szerint egy G végtelen gráf akkor és csak akkor k-színezhető (valamely véges k-ra úgy, hogy semelyik két szomszédos csúcs színe se egyezzen meg), ha minden véges részgráfja is k-színezhető. Ezzel ekvivalens állítás, hogy minden k-kritikus gráfnak (olyan gráfnak, aminek színezéséhez k színre van szükség, de minden részgráfjának ennél kevesebbre) véges számú csúccsal kell rendelkeznie.

Bár a de Bruijn–Erdős-tételnek számos különböző bizonyítása létezik, mindegyik a kiválasztási axiómára alapul. A tétel alkalmazásai közé tartozik a négyszíntétel és a Dilworth-tétel kiterjesztése véges gráfokról és részbenrendezett halmazokról végtelenre, továbbá a sík kromatikus számával foglalkozó Hadwiger–Nelson-probléma redukálása véges gráfokra vonatkozó problémára. A tétel általánosítható véges számú színről olyan színhalmazokra, melynek számossága erősen kompakt kardinális szám (wd).

Bizonyítások

szerkesztés

De Bruijn eredeti bizonyítása transzfinit indukción alapult.[1]

(Gottschalk 1951) a következő, igen rövid bizonyítást adta meg, Andrej Tyihonov topológiai kompaktsági tétele alapján. Tegyük fel, hogy adott G végtelen gráf minden véges részgráfja k-színezhető, és legyen X a k színnek a G csúcsaihoz való összes lehetséges hozzárendeléseinek tere (függetlenül attól, hogy érvényes színezést adnak-e)! Ekkor X úgy tekinthető, mint a kV(G) szorzattér, amiről a Tyihonov-tétel alapján tudjuk, hogy kompakt. Ekkor G minden F véges részgráfjára legyen XF azon részhalmaza X-nek, mely F érvényes színezéseit tartalmazza. Ekkor az XF halmazrendszer véges metszet tulajdonsággal (wd) rendelkező zárt halmazok családja, tehát a kompaktság miatt nem üres metszettel rendelkezik. Ennek a metszetnek minden tagja G érvényes színezése.[2]

Másfajta, a Zorn-lemmát felhasználó bizonyítást ad meg Pósa Lajos, illetve 1951-es PhD-tézisében Gabriel Andrew Dirac is. Ha G végtelen gráf, melynek minden véges részgráfja k-színezhető, akkor a Zorn-lemma alapján az ugyanezzel a tulajdonsággal rendelkező M maximális gráf (tehát olyan gráf, amiben nem lehet új élet felvenni anélkül, hogy valamely véges részgráfja színezéséhez ne kelljen k-nál több színt felhasználni) részgráfja. Az M-beli nem szomszédosság bináris relációja egy ekvivalenciareláció, és az ekvivalenciaosztályok megadják a G gráf k-színezését. Ez a bizonyítás azonban nehezebben általánosítható a kompaktsági bizonyításnál.[3]

A tétel bizonyítható ultraszűrők[4] vagy nem standard analízis használatával is.[5] (Nash-Williams 1967) megszámlálható csúcsú gráfokra megad egy a Kőnig-lemmára alapozó bizonyítást.

A kiválasztási axiómától való függőség

szerkesztés

A de Bruijn–Erdős-tétel bizonyításai mind valamilyen módon felhasználják a kiválasztási axiómát. Az axióma feltételezése szükséges, léteznek olyan matematikai modellek, melyben a kiválasztási axióma és de Bruijn–Erdős-tétel is hamis.

Legyen például G egy végtelen gráf, melynek csúcsai az összes valós számot testesítik meg. Két valós számnak megfelelő G-beli x és y csúcsot akkor kössünk össze, ha (| x − y| 

± √2) értéke racionális szám. Ezzel ekvivalens, hogy a gráfban minden x valós szám és az x ± (√2 + q) alakban felírható számok között él húzódik, ahol q tetszőleges racionális szám). Így, ha két G-beli csúcs négyzetgyök kettő páros számszorosa plusz egy racionális számmal tér el, a két csúcsot ugyanazzal a színnel színezhetjük és ekvivalensnek tekinthetjük; ha a gráf minden ekvivalenciaosztályát összehúzzuk egy-egy csúccsá, végtelen párosítást kapunk, ami a kiválasztási axióma alapján két színnel színezhető. A Solovay modellben viszont, ahol a valós számok minden részhalmaza Lebesgue-mérhető, az G színezéséhez végtelen sok színre van szükség, hiszen itt minden színosztálynak mérhető halmaznak kell lennie, és megmutatható, hogy a valós számok minden olyan részhalmaza, mely nem tartalmaz G-beli élet, nullmértékű. Ezért a Solovay-modell esetén az G kromatikus száma végtelen, ami sokkal nagyobb, mint a véges részgráfjainak kromatikus száma (legfeljebb kettő).[6]

A megszámlálhatóan végtelen gráfokra vonatkozó de Bruijn–Erdős-tételről megmutatható, hogy axiomatikus erejében megegyezik a Kőnig-lemmával, a másodrendű aritmetika keretein belül.[7]

Alkalmazásai

szerkesztés
 
A sík színezése hét színnel, és a sík egy 4 kromatikus számú egységtávolsággráfja, a Moser-gráf, melyek a Hadwiger–Nelson-probléma alsó és felső korlátját jelentik.

A de Bruijn–Erdős-tétel egyik alkalmazása az euklideszi sík egységtávolsággráfának kromatikus számára rákérdező Hadwiger–Nelson-problémával kapcsolatos. A sík gráfja nem megszámlálhatóan végtelen csúcsból áll, a sík minden pontjához egy csúcs tartozik. Két csúcsot akkor köt össze él, ha pontok közötti euklideszi távolság éppen egy. Ennek a végtelen gráfnak léteznek négy színt megkövetelő véges részgráfjai, ilyen például a Moser-gráf, és létezik a sík hatszögekkel való csempézésén alapuló 7-színezése. Ezért a sík kromatikus száma biztosan a {4,5,6,7} halmazba tartozik, de nem ismert, hogy a négy szám közül melyik a helyes. A de Bruijn–Erdős-tétel megmutatja, hogy léteznie kell véges egységtávolsággráfnak, aminek kromatikus száma a teljes síkéval megegyezik, tehát ha valóban 4-nél nagyobb a sík kromatikus száma, akkor véges számítással megtalálható ez a gráf.[8]

A de Bruijn–Erdős-tétel segítségével a Dilworth-tétel kiterjeszthető véges részbenrendezett halmazokról végtelenekre. Dilworth tétele kimondja, hogy egy részben rendezés szélessége (egy halmazban a kölcsönösen össze nem hasonlítható elemek maximális száma) megegyezik a láncok (teljesen rendezett részhalmazok) minimális számával, amibe a részben rendezés particionálható. Egy láncba particionálás felfogható úgy is, mint a részbenrendezés össze nem hasonlíthatósági gráfjának egy színezése (ez olyan gráf, melynek minden csúcsa a rendezés egy elemének felel meg, és két csúcs között akkor húzódik él, ha az elemek nem összehasonlíthatók). Ezt a színezési interpretációt felhasználva, együtt a véges részbenrendezett halmazokra vonatkozó Dilworth-tétellel, lehetséges bizonyítani, hogy egy végtelen részbenrendezett halmaz pontosan akkor véges w szélességű, ha w láncba particionálható.[9]

Hasonló módon terjeszti ki a de Bruijn–Erdős-tétel a négyszíntételt véges síkgráfokról végtelen síkgráfokra: minden gráf, amit síkba lehet rajzolni metsző élek nélkül, négy színnel kiszínezhető, legyen a gráf akár véges, akár végtelen. Általánosabban, minden olyan végtelen gráf, aminek az összes véges részgráfja síkba rajzolható, kiszínezhető négy színnel.[10]

A de Bruijn–Erdős-tétel alkalmas Fred Galvin gráfok kromatikus számának Darboux-tulajdonságára vonatkozó kérdésének megválaszolására is: bármely két véges pozitív egész j < k számra, ha G gráf kromatikus száma k, létezik-e j kromatikus számú részgráfja. Ennek megállapításához meg kell keresni G egy olyan véges részgráfját, aminek ugyanakkora a kromatikus száma mint G-nek, majd addig kell törölgetni egyenként a csúcsokat, amíg a kívánt j kromatikus számot el nem érjük. Végtelen kromatikus számok esetében a helyzet bonyolultabb: a halmazelmélettel konzisztens az olyan gráf létezése, mely ℵ2 csúcsból áll, kromatikus száma ℵ2, de nincs ℵ1 kromatikus számú részgráfja.[11]

Általánosításai

szerkesztés

(Rado 1949) igazolja a következő, a de Bruijn–Erdős-tétel általánosításaként tekinthető tételt. Legyen V egy végtelen halmaz, például egy végtelen gráf csúcsainak halmaza. Minden V-beli v elemhez, legyen cv színek egy véges halmaza. Ráadásul, V minden véges S részhalmazához válasszunk valamilyen S-hez tartozó CS színezést , melynen minden S-beli v elem színe a cv-be tartozik. Ekkor létezik a teljes V olyan tulajdonságú χ globális színezése, hogy minden véges S halmazhoz tartozik olyan T véges tartalmazó halmaz, melyben χ és CT megegyeznek. Méghozzá, ha egy G végtelen gráf minden véges részgráfjához választunk egy k-színezést, akkor létezik G-nak olyan k-színezése, melyben minden véges gráfnak van egy nagyobb tartalmazó gráfja, aminek színezése megegyezik a teljes gráf színezésével.[12]

Ha egy gráfnak nem véges a kromatikus száma, akkor a de Bruijn–Erdős-tételből következtethetően minden lehetséges kromatikus számhoz kell tartoznia véges részgráfjának. Történtek vizsgálatok arra nézve, hogy ebben az esetben mit lehet még mondani a kötelezően fellépő részgráfok egyéb tulajdonságairól; például a korlátlan kromatikus számú gráfok szükségképpen részgráfként tartalmaznak minden lehetséges véges páros gráfot. Lehetséges azonban, hogy tetszőlegesen nagy páratlan derékbőséggel rendelkeznek, így nem feltétlenül tartalmaznak bármely előre meghatározott véges nem páros részgráfot.[13]

A de Bruijn–Erdős-tétel közvetlenül alkalmazható hipergráf-színezési problémákra is, ahol minden hiperélnek egynél több színű csúcsot kell összekötnie: ahogy gráfoknál, úgy hipergráfoknál is pontosan akkor létezik k-színezés, ha mindegyik véges részhipergráfnak van k-színezése.[14] Ez Kurt Gödel kompaktsági tételének speciális esete, mely szerint egy elsőrendű nyelv kifejezéseinek halmazához akkor és csak akkor tartozik modell, ha minden véges részhalmazához tartozik modell.

A tétel általánosítható olyan helyzetekre, ahol a színek száma végtelen kardinális szám: ha κ erősen kompakt kardinális szám, akkor minden G gráf és μ < κ, kardinális szám esetében G kromatikus száma pontosan akkor legfeljebb μ, ha minden κ-nál kisebb számosságú részgráfja kromatikus száma is legfeljebb μ.[15] Az eredeti de Bruijn–Erdős-tétel ennek az általánosításnak a κ = ℵ0 esete, hiszen egy halmaz pontosan akkor véges, ha számossága ℵ0-nál kisebb. Mindenesetre az erősen kompakt kardinális kitétel fontos: ha az általánosított kontinuumhipotézis (GCH) igaz, akkor minden γ végtelen kardinális számhoz tartozik (2γ)+ számosságú G gráf úgy, hogy G kromatikus száma nagyobb mint γ, de G minden részgráfja, aminek csúcshalmaza kisebb kitevőjű mint G, legfeljebb γ kromatikus számú.[16] (Lake 1975) azt a jellemzést adja a De Bruijn–Erdős-tétel általánosításának megfelelő végtelen gráfokra, hogy kromatikus számuk megegyezik a szigorúan kisebb részgráfjuk maximális kromatikus számával.

Fordítás

szerkesztés
  • Ez a szócikk részben vagy egészben a De Bruijn–Erdős theorem (graph theory) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

szerkesztés
  1. ↑ (Soifer 2008) (p. 236).
  2. ↑ (Jensen & Toft 1995). Gottschalk a bizonyítást általánosabban, a de Bruijn–Erdős tételt általánosító (Rado 1949)-tétel bizonyításaként.
  3. ↑ (Jensen & Toft 1995); (Harzheim 2005). Jensen és Toft Gert Sabidussinak tulajdonítják az észrevételt, hogy Gottschalk bizonyítása könnyebben általánosítható. Soifer (pp. 238–239) megadja ugyanazt a bizonyítást a Zorn-lemma felhasználásával, amit 2005-ben Dmytro Karabash egyetemi hallgató fedezett fel újra.
  4. ↑ (Luxemburg 1962).
  5. ↑ (Hurd & Loeb 1985).
  6. ↑ (Shelah & Soifer 2003); (Soifer 2008), pp. 541–542.
  7. ↑ (Schmerl 2000).
  8. ↑ (Soifer 2008), p. 39.
  9. ↑ (Harzheim 2005), Theorem 5.6, p. 60.
  10. ↑ (Barnette 1983). (Nash-Williams 1967) ugyanezt az állítást teszi az ötszín-tétellel a megszámlálhatóan végtelen síkgráfokra; ugyanis a négyszínsejtést még nem sikerült bebizonyítani, amikor a felmérését közzétette, és a de Bruijn–Erdős-tételnek az általa használt bizonyítása csak megszámlálhatóan végtelen gráfokra vonatkozik. A síkba rajzolható véges síkgráfos általánosításhoz (amit közvetlenül a Gödel-féle kompaktsági tétellel igazolnak) lásd Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), Universitext, Springer-Verlag, p. 32, ISBN 978-1-4419-1220-6, <http://www.springerlink.com/content/978-1-4419-1220-6/>[halott link].
  11. ↑ (Komjáth 1988); (Komjáth 2011).
  12. ↑ A Rado-lemma és a de Bruijn–Erdős-tétel kapcsolatához lásd a Theorem A of (Nash-Williams 1967)-hoz kapcsolódó diszkussziót.
  13. ↑ (Erdős & Hajnal 1966); (Komjáth 2011).
  14. ↑ (Soifer 2008), p. 239.
  15. ↑ This follows immediately from the definition of a strongly compact cardinal κ as being a cardinal such that every collection of formulae of infinitary logic each of length smaller than κ, that is satisfiable for every subcollection of fewer than κ formulae, is globally satisfiable. See e.g. Kanamori, Akihiro (2008), The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings (2nd ed.), Springer Monographs in Mathematics, Springer-Verlag, p. 37, ISBN 978-3-540-88866-6, <https://books.google.com/books?id=FH_n84ocuSMC&pg=PA37>.
  16. ↑ (Erdős & Hajnal 1968).
A lap eredeti címe: „https://hu.wiki.x.io/w/index.php?title=De_Bruijn–Erdős-tétel_(gráfelmélet)&oldid=26913173”