De Bruijn-Erdős sats är en klassisk grafteorem som bevisats av Pal Erdős och Nicolaas de Bruijn [1] .
Det kromatiska numret för en oändlig graf , om detta nummer är ändligt, är lika med det största kromatiska talet bland alla dess finita subgrafer .
De Bruijn-Erdős sats har flera olika bevis, var och en med hjälp av valets axiom . De Bruijns originalbevis använde transfinit induktion [2] .
Gottschalk [3] gav följande mycket korta bevis, baserat på Tikhonovs kompakthetsteorem i topologi . Antag att för en given oändlig graf G är vilken finit subgraf som helst k -färgbar, och låt X vara utrymmet för alla k färgtilldelningar till G :s hörn (oavsett om den givna färgningen är korrekt). Då kan X betraktas som en produkt av topologiska utrymmen k V ( G ) , som är kompakt enligt Tikhonovs teorem . För varje finit subgraf F av G , låt X F vara en delmängd av X som består av färgtilldelningar som ger en korrekt färgning av F. Då är mängdsystemet X F en familj av slutna mängder med den finita skärningsegenskapen , så att systemet har en icke-tom skärningspunkt på grund av sin kompakthet. Vilken term som helst av denna skärningspunkt är en riktig färgning av G [4] .
Ett annat bevis som använder Zorns lemma gavs av Lajos Poza och citerades också i 1951 års avhandling av Andrew Dirac . Om G är en oändlig graf där vilken ändlig subgraf som helst är k -färgbar, så är det enligt Zorns lemma en subgraf till en maximal graf M med samma egenskap (en graf till vilken kanter inte kan läggas till utan att någon finit subgraf kräver mer än k färger). Den binära icke-adjacensrelationen i M är en ekvivalensrelation, och ekvivalensklasserna för denna relation ger en k -färgning av grafen G . Detta bevis är dock svårare att generalisera än beviset med kompakthetslemmat [5] .
Teoremet kan bevisas med hjälp av ultrafilter [6] eller icke-standardiserad analys [7] . Nash-Williams [8] gav ett bevis för grafer med ett räknebart antal hörn, baserat på Koenigs oändliga trädlemma .
Alla bevis för de Bruijn-Erdős sats använder valets axiom . Det finns modeller för matematik där både valets axiom och de Bruijn-Erdős sats inte är sanna.
Låt till exempel G vara en oändlig graf där alla reella tal är hörn. I G , sammanfoga två valfria reella tal x och y med en kant om värdet (| x − y | ± √2) är ett rationellt tal . På motsvarande sätt finns det i denna graf kanter mellan alla reella tal x och alla reella tal av formen x ± (√2 + q ) , där q är vilket rationellt tal som helst. Således, om två hörn i G skiljer sig åt med en jämn heltalsfaktor av kvadratroten ur två plus ett rationellt tal, kan de använda samma färg och punkterna kan anses vara ekvivalenta. Grafen som bildas genom att dra ihop ekvivalensklassen till en vertex är en oändlig matchning och kan enkelt färgläggas i två färger med hjälp av det valda axiomet. Varje ändlig subgraf av G kräver alltså två färger. Men i Solovay-modellen , där varje uppsättning av reella tal är Lebesgue-mätbar , kräver G oändligt många färger, eftersom i detta fall varje färgklass måste vara en mätbar uppsättning, och det kan visas att varje mätbar uppsättning av reella tal som inte innehåller kanter på G måste ha måttet noll. I Solovay-modellen är alltså det (obegränsade) kromatiska talet för hela grafen G mycket större än det kromatiska antalet av dess ändliga subgrafer (högst två) [9] [10] .
Det kan visas att de Bruijn-Erdős sats för räkningsbara grafer är ekvivalent (i teorin om andra ordningens aritmetik ) med Königs oändliga trädlemma [11] .
En av tillämpningarna av de Bruijn-Erdős teorem är Nelson-Erdős-Hadwiger-problemet på det kromatiska numret av enhetsavståndsgrafen för det euklidiska planet . En plan graf har ett oräkneligt antal hörn, en för varje punkt i planet. Två hörn är förbundna med en kant när det euklidiska avståndet mellan motsvarande två punkter är exakt ett. En oändlig graf har finita subgrafer, som Moser-spindeln , som kräver fyra färger, och en sjufärgsfärgning baserad på en sexkantig plattsättning av planet är känd. Det kromatiska talet för planet måste alltså tillhöra mängden {4,5,6,7}, men vilket av dessa fyra tal som verkligen är ett kromatiskt tal är inte känt. De Bruijn-Erdős sats visar att det för detta problem finns en graf med ändlig enhetsdistans med samma kromatiska tal som hela planet, så att om det kromatiska talet är större än fyra, så kan detta faktum bevisas genom ändliga beräkningar [12 ] .
De Bruijn-Erdős sats kan också användas för att utöka Dilworths sats från en finit version till oändliga posetter . Dilworths teorem säger att bredden på en partiell ordning (det största antalet element i en uppsättning av ömsesidigt ojämförbara element) är lika med det minsta antalet kedjor ( helt ordnade delmängder) i vilka en partiell ordning kan delas upp. Kedjenedbrytningen kan ses som en färgning av oförlikbarhetsgrafen för en partiell ordning (en graf som har en vertex för varje element i ordningen och en kant för varje par av ojämförliga element). Genom att använda denna tolkning som en färgning, tillsammans med ett separat bevis på Dilworths sats för finita poseter, kan man bevisa att en oändlig poset har ändlig bredd w om och endast om den kan brytas ner i w -strängar [13] .
På samma sätt utvidgar de Bruijn-Erdős sats fyrfärgsproblemet från finita plana grafer till oändliga plana grafer – vilken graf som helst som kan ritas utan skärningspunkter i planet, finita eller oändliga, kan färgas med fyra färger. Mer generellt kan alla oändliga grafer för vilka en finit subgraf är plan återigen färgas med fyra färger [14] [15]
De Bruijn-Erdős sats kan användas för att svara på Gelvins fråga angående mellanvärdessatsen för grafiska kromatiska tal — för två valfria ändliga tal j < k och alla grafer G med kromatiska tal k , finns det en subgraf av G med kromatiskt nummer j . För att se detta, låt oss hitta en finit subgraf av G med samma kromatiska nummer som G själv och sedan ta bort hörnen en efter en tills vi får det kromatiska talet j . Fallet för oändliga kromatiska tal är dock mer komplicerat - det överensstämmer med mängdteorin att det finns en graf med ℵ 2 hörn och kromatiskt tal ℵ 2 men ingen subgraf med kromatisk nummer ℵ 1 [16] [17] .
Rado [18] bevisade följande teorem, som kan betraktas som en generalisering av de Bruijn-Erdős teorem. Låt V vara en oändlig mängd, till exempel mängden av hörn i en oändlig graf. För varje element v av V , låt c v vara en ändlig uppsättning färger. Dessutom, för varje ändlig delmängd S av mängden V , väljer vi någon färgning C S av delmängden S i vilken färgen på varje element v i delmängden S tillhör cv . Sedan finns det en global färgning χ av alla V med egenskapen att vilken finit mängd S som helst har en finit supermängd T som χ och C T överensstämmer med. I synnerhet, om vi väljer en k -färgning för en ändlig subgraf i en oändlig graf G , så finns det en k -färgning av G där varje ändlig graf har en större supergraf vars färgning överensstämmer med färgningen av hela grafen [ 19] .
Om grafen inte har ett ändligt kromatiskt tal, så följer det av de Bruijn-Erdős sats att grafen måste innehålla ändliga subgrafer för alla möjliga kromatiska tal. Forskarna undersökte också andra förhållanden på subgrafer. Till exempel måste obegränsade kromatiska grafer också innehålla en ändlig tvådelad graf som en subgraf. De kan dock ha en godtyckligt stor udda omkrets [20] [17] .
De Bruijn-Erdős sats gäller också direkt för hypergraffärgningsproblem , där varje hyperkant måste ha hörn av mer än en färg. När det gäller grafer har en hypergraf en k -färgning om och endast om någon av dess ändliga subhypergrafer har en k -färgning [21] . Ett specialfall Kurt Gödels kompaktitetsteorem säger att en uppsättning första ordningens påståenden har en modell om och bara om någon ändlig delmängd har en modell.
Satsen kan generaliseras till fall där antalet färger är ett oändligt kardinaltal — om κ är ett strikt kompakt kardinaltal , så har G för varje graf G och kardinaltal μ < κ ett kromatiskt tal som inte överstiger μ om och endast om när dess subgrafer med kardinalitet mindre än κ har ett kromatiskt tal som inte överstiger μ [22] . Den ursprungliga de Bruijn-Erdős sats är ett specialfall κ = ℵ 0 av denna generalisering, eftersom en mängd är finit om och endast om dess kardinalitet är mindre än ℵ 0 . Vissa antaganden, såsom den strikta kompaktheten hos mängdens kardinalnummer, är emellertid nödvändiga - om den generaliserade kontinuumhypotesen är sann, så finns det för varje oändlig kardinal γ en graf G av kardinalitet (2 γ ) + , såsom att det kromatiska numret för grafen G är större än γ , men varje subgrafgraf G , vars uppsättning hörn har mindre kardinalitet än G , har ett kromatiskt tal som inte överstiger γ [23] . Lake [24] beskriver oändliga grafer som uppfyller generaliseringen av de Bruijn-Erdős sats som grafer vars kromatiska antal är lika med det största kromatiska antalet strikt mindre subgrafer.