De Bruijn-Erdős sætning er en klassisk grafteoretisk sætning bevist af Pal Erdős og Nicolaas de Bruijn [1] .
Det kromatiske tal for en uendelig graf , hvis dette tal er endeligt, er lig med det største kromatiske tal blandt alle dens endelige undergrafer .
De Bruijn-Erdős sætning har flere forskellige beviser, som hver bruger det valgte aksiom . De Bruijns originale bevis brugte transfinit induktion [2] .
Gottschalk [3] gav følgende meget korte bevis, baseret på Tikhonovs kompakthedsteorem i topologi . Antag, at for en given uendelig graf G er enhver finit subgraf k -farverbar, og lad X være rummet for alle k farvetildelinger til toppunkterne af G (uanset om den givne farve er korrekt). Så kan X betragtes som et produkt af topologiske rum k V ( G ) , som er kompakt ved Tikhonovs sætning . For hver endelig undergraf F af G , lad X F være en delmængde af X bestående af farvetildelinger, der giver en korrekt farvning af F. Så er mængdesystemet X F en familie af lukkede mængder med den endelige skæringsegenskab , således at systemet på grund af dets kompakthed har et ikke-tomt skæringspunkt. Ethvert led i dette skæringspunkt er en korrekt farvning af G [4] .
Et andet bevis ved hjælp af Zorns lemma blev givet af Lajos Poza og også citeret i 1951-afhandlingen af Andrew Dirac . Hvis G er en uendelig graf, hvor en hvilken som helst finit subgraf er k -farverbar, så er den ifølge Zorns lemma en subgraf af en maksimal graf M med samme egenskab (en graf, hvortil kanter ikke kan tilføjes uden en eller anden endelig subgraf, der kræver mere end k farver). Den binære ikke-tilstødende relation i M er en ækvivalensrelation, og ækvivalensklasserne af denne relation giver en k -farvning af grafen G . Dette bevis er dog sværere at generalisere end beviset med kompakthedslemmaet [5] .
Sætningen kan bevises ved hjælp af ultrafiltre [6] eller ikke-standardanalyse [7] . Nash-Williams [8] gav et bevis for grafer med et tælleligt antal hjørner, baseret på Koenigs uendelige trælemma .
Alle beviser for de Bruijn-Erdős sætning bruger valgaksiomet . Der er modeller for matematik, hvor både valgaksiomet og de Bruijn-Erdős sætning ikke er sande.
Lad for eksempel G være en uendelig graf, hvor alle reelle tal er hjørner. I G skal du forbinde to reelle tal x og y med en kant, hvis værdien (| x − y | ± √2) er et rationelt tal . Tilsvarende eksisterer der i denne graf kanter mellem alle reelle tal x og alle reelle tal på formen x ± (√2 + q ) , hvor q er et hvilket som helst rationelt tal. Således, hvis to hjørner i G adskiller sig med en lige heltalsfaktor af kvadratroden af to plus et rationelt tal, kan de bruge den samme farve, og punkterne kan betragtes som ækvivalente. Grafen dannet ved at kontrahere ækvivalensklassen til et toppunkt er en uendelig matchning og kan nemt farves i to farver ved hjælp af det valgte aksiom. Enhver endelig subgraf af G kræver således to farver. Men i Solovay-modellen , hvor hvert sæt af reelle tal er Lebesgue-målbare , kræver G uendeligt mange farver, da hver farveklasse i dette tilfælde skal være et målbart sæt, og det kan påvises, at ethvert målbart sæt af reelle tal, der ikke indeholder kanter af G , skal have mål nul. I Solovay-modellen er det (ubegrænsede) kromatiske tal for hele grafen G meget større end det kromatiske antal af dens endelige undergrafer (maksimalt to) [9] [10] .
Det kan påvises, at de Bruijn-Erdős-sætningen for tællelige grafer svarer (i teorien om andenordens aritmetik ) til Königs uendelige trælemma [11] .
En af anvendelserne af de Bruijn-Erdős sætning er Nelson-Erdős-Hadwiger-problemet på det kromatiske tal på enhedsafstandsgrafen for det euklidiske plan . En plan graf har et utalligt antal hjørner, en for hvert punkt i planet. To hjørner er forbundet med en kant, når den euklidiske afstand mellem de tilsvarende to punkter er nøjagtig ét. En uendelig graf har endelige undergrafer, såsom Moser-spindelen , som kræver fire farver, og en syvfarvet farvning baseret på en sekskantet flisebelægning af planet er kendt. Flyets kromatiske tal må således tilhøre mængden {4,5,6,7}, men hvilket af disse fire tal, der egentlig er et kromatisk tal, vides ikke. De Bruijn-Erdős sætning viser, at for dette problem er der en finit enhedsafstandsgraf med samme kromatiske tal som hele planen, så hvis det kromatiske tal er større end fire, så kan dette faktum bevises ved endelige beregninger [12 ] .
De Bruijn-Erdős-sætningen kan også bruges til at udvide Dilworth-sætningen fra en finit version til uendelige stillinger . Dilworths sætning siger, at bredden af en partiel orden (det største antal elementer i et sæt af gensidigt uforlignelige elementer) er lig med det mindste antal kæder ( fuldt ordnede delmængder), hvori en partiel orden kan dekomponeres. Kædens nedbrydning kan ses som en farvning af uforlignelige grafen for en delrækkefølge (en graf, der har et toppunkt for hvert element i rækkefølgen og en kant for hvert par uforlignelige elementer). Ved at bruge denne fortolkning som farvelægning, sammen med et særskilt bevis på Dilworths sætning for endelige poseter, kan man bevise, at en uendelig poset har begrænset bredde w hvis og kun hvis den kan dekomponeres i w - strenge [13] .
På samme måde udvider de Bruijn-Erdős sætning firefarveproblemet fra endelige plane grafer til uendelige plane grafer - enhver graf, der kan tegnes uden skæringspunkter i planet, endelig eller uendelig, kan farves med fire farver. Mere generelt kan enhver uendelig graf, for hvilken enhver finit subgraf er plan, igen farves med fire farver [14] [15]
De Bruijn-Erdős-sætningen kan bruges til at besvare Gelvins spørgsmål vedrørende mellemværdisætningen for grafiske kromatiske tal — for alle to endelige tal j < k og enhver graf G med kromatisk tal k , findes der en undergraf af G med kromatisk tal j . For at se dette, lad os finde en endelig undergraf af G med det samme kromatiske tal som G selv , og derefter fjerne hjørnerne en efter en, indtil vi får det kromatiske tal j . Imidlertid er sagen for uendelige kromatiske tal mere kompliceret - det er i overensstemmelse med mængdeteorien, at der eksisterer en graf med ℵ 2 hjørner og kromatisk tal ℵ 2 , men ingen subgraf med kromatisk tal ℵ 1 [16] [17] .
Rado [18] beviste følgende sætning, som kan betragtes som en generalisering af de Bruijn-Erdős sætning. Lad V være en uendelig mængde, for eksempel mængden af hjørner i en uendelig graf. For hvert element v i V , lad c v være et endeligt sæt farver. For en hvilken som helst finit delmængde S af mængden V vælger vi desuden en farve C S af delmængden S , hvor farven på hvert element v i delmængden S tilhører cv . Så er der en global farvning χ af alle V med den egenskab, at enhver endelig mængde S har en endelig supermængde T , som χ og C T er enige om. Især hvis vi vælger en k -farvning for en hvilken som helst finit undergraf af en uendelig graf G , så er der en k -farvning af G , hvor hver endelig graf har en større supergraf, hvis farve er i overensstemmelse med farven af hele grafen [ 19] .
Hvis grafen ikke har et endeligt kromatisk tal, så følger det af de Bruijn-Erdős sætning, at grafen skal indeholde endelige undergrafer for alle mulige kromatiske tal. Forskerne undersøgte også andre forhold på undergrafer. For eksempel skal ubundne kromatiske grafer også indeholde enhver finit todelt graf som en undergraf. De kan dog have en vilkårligt stor ulige omkreds [20] [17] .
De Bruijn-Erdős-sætningen gælder også direkte for hypergraffarveproblemer , hvor hver hyperkant skal have hjørner med mere end én farve. Hvad angår grafer, har en hypergraf en k -farve, hvis og kun hvis nogen af dens endelige subhypergrafer har en k -farve [21] . Et særligt tilfælde Kurt Gödels kompaktitetssætning siger, at et sæt af førsteordens udsagn har en model, hvis og kun hvis en begrænset delmængde har en model.
Sætningen kan generaliseres til tilfælde, hvor antallet af farver er et uendeligt kardinaltal — hvis κ er et strengt kompakt kardinaltal , så for enhver graf G og kardinaltal μ < κ, har G et kromatisk tal, der ikke overstiger μ hvis og kun hvis dens undergrafer med kardinalitet mindre end κ har et kromatisk tal, der ikke overstiger μ [22] . Den oprindelige de Bruijn-Erdős sætning er et specialtilfælde κ = ℵ 0 af denne generalisering, da en mængde er endelig, hvis og kun hvis dens kardinalitet er mindre end ℵ 0 . Men nogle antagelser, såsom den strenge kompakthed af mængdens kardinalnummer, er nødvendige - hvis den generaliserede kontinuumhypotese er sand, så eksisterer der for enhver uendelig kardinal γ en graf G for kardinalitet (2 γ ) + , som f.eks. at det kromatiske tal for grafen G er større end γ , men enhver undergrafgraf G , hvis sæt af hjørner har mindre kardinalitet end G , har et kromatisk tal, der ikke overstiger γ [23] . Lake [24] beskriver uendelige grafer, der opfylder generaliseringen af de Bruijn-Erdős sætning, som grafer, hvis kromatiske tal er lig med det største kromatiske antal af strengt mindre undergrafer.