Teorema de Bruijn-Erdős este o teoremă clasică a teoriei grafurilor demonstrată de Pal Erdős și Nicolaas de Bruijn [1] .
Numărul cromatic al unui graf infinit , dacă acest număr este finit, este egal cu cel mai mare număr cromatic dintre toate subgrafele sale finite .
Teorema lui de Bruijn-Erdős are mai multe dovezi diferite, fiecare folosind axioma alegerii . Dovada originală a lui De Bruijn a folosit inducția transfinită [2] .
Gottschalk [3] a dat următoarea demonstrație foarte scurtă, bazată pe teorema de compactitate a lui Tikhonov în topologie . Să presupunem că pentru un graf infinit G dat, orice subgraf finit este k -colorabil și fie X spațiul tuturor k alocații de culoare la vârfurile lui G (indiferent dacă colorarea dată este corectă). Atunci X poate fi considerat ca un produs al spațiilor topologice k V ( G ) , care este compact după teorema lui Tihonov . Pentru fiecare subgraf finit F al lui G , fie X F o submulțime a lui X constând din atribuiri de culori care dau o colorare adecvată a lui F. Atunci sistemul de mulțimi X F este o familie de mulțimi închise cu proprietatea de intersecție finită , astfel încât sistemul are o intersecție nevidă datorită compactității sale. Orice termen al acestei intersecții este o colorare proprie a lui G [4] .
O altă dovadă folosind lema lui Zorn a fost dată de Lajos Poza și, de asemenea, citată în teza din 1951 de Andrew Dirac . Dacă G este un graf infinit în care orice subgraf finit este k -colorabil, atunci după lema lui Zorn este un subgraf al unui graf maxim M cu aceeași proprietate (un grafic la care nu se pot adăuga muchii fără un subgraf finit care necesită mai mult de k culori). Relația binară de non-adiacență din M este o relație de echivalență, iar clasele de echivalență ale acestei relații dau o k -colorare a graficului G. Totuși, această demonstrație este mai greu de generalizat decât demonstrația prin lema compactității [5] .
Teorema poate fi demonstrată folosind ultrafiltre [6] sau analize non-standard [7] . Nash-Williams [8] a dat o demonstrație pentru grafice cu un număr numărabil de vârfuri, bazată pe lema copacului infinit a lui Koenig .
Toate dovezile teoremei lui de Bruijn-Erdős folosesc axioma alegerii . Există modele de matematică în care atât axioma alegerii, cât și teorema lui de Bruijn-Erdős nu sunt adevărate.
De exemplu, să fie G un grafic infinit în care toate numerele reale sunt vârfuri. În G , uniți oricare două numere reale x și y cu o muchie dacă valoarea (| x − y | ± √2) este un număr rațional . În mod echivalent, în acest grafic există muchii între toate numerele reale x și toate numerele reale de forma x ± (√2 + q ) , unde q este orice număr rațional. Astfel, dacă două vârfuri din G diferă printr-un factor întreg par al rădăcinii pătrate a lui doi plus un număr rațional, ele pot folosi aceeași culoare și punctele pot fi considerate echivalente. Graficul format prin contractarea clasei de echivalență la un vârf este o potrivire infinită și poate fi colorat cu ușurință în două culori folosind axioma alegerii. Astfel, orice subgraf finit al lui G necesită două culori. Cu toate acestea, în modelul Solovay , în care fiecare set de numere reale este măsurabil Lebesgue , G necesită infinit de culori, deoarece în acest caz fiecare clasă de culori trebuie să fie o mulțime măsurabilă și se poate demonstra că orice set măsurabil de numerele reale care nu conțin muchiile lui G trebuie să aibă măsura zero. Astfel, în modelul Solovay, numărul cromatic (nemărginit) al întregului graf G este mult mai mare decât numărul cromatic al subgrafelor sale finite (maximum două) [9] [10] .
Se poate demonstra că teorema lui de Bruijn-Erdős pentru graficele numărabile este echivalentă (în teoria aritmeticii de ordinul doi ) cu lema arborelui infinit a lui König [11] .
Una dintre aplicațiile teoremei lui de Bruijn-Erdős este problema Nelson-Erdős-Hadwiger asupra numărului cromatic al graficului unității de distanță al planului euclidian . Un grafic plan are un număr nenumărat de vârfuri, câte unul pentru fiecare punct din plan. Două vârfuri sunt conectate printr-o muchie atunci când distanța euclidiană dintre cele două puncte corespunzătoare este exact unul. Un grafic infinit are subgrafe finite, cum ar fi axul Moser , care necesită patru culori, și se cunoaște o colorare în șapte culori bazată pe o placare hexagonală a planului. Astfel, numărul cromatic al planului trebuie să aparțină mulțimii {4,5,6,7}, dar care dintre aceste patru numere este într-adevăr un număr cromatic nu se știe. Teorema de Bruijn-Erdős arată că pentru această problemă există un grafic de distanță unitară finită cu același număr cromatic ca întregul plan, astfel încât dacă numărul cromatic este mai mare de patru, atunci acest fapt poate fi demonstrat prin calcule finite [12]. ] .
Teorema lui de Bruijn-Erdős poate fi, de asemenea, utilizată pentru a extinde teorema Dilworth de la o versiune finită la posete infinite . Teorema lui Dilworth afirmă că lățimea unui ordin parțial (cel mai mare număr de elemente dintr-un set de elemente reciproc incomparabile) este egală cu numărul minim de lanțuri ( submulțimi complet ordonate ) în care poate fi descompusă o ordine parțială. Descompunerea în lanț poate fi privită ca o colorare a graficului de incomparabilitate de ordin parțial (un grafic care are un vârf pentru fiecare element al ordinului și o muchie pentru fiecare pereche de elemente incomparabile). Folosind această interpretare ca o colorare, împreună cu o demonstrație separată a teoremei lui Dilworth pentru posete finite, se poate demonstra că un poset infinit are lățime finită w dacă și numai dacă poate fi descompus în w șiruri [13] .
În același mod, teorema lui de Bruijn-Erdős extinde problema cu patru culori de la grafuri plane finite la grafuri plane infinite — orice graf care poate fi desenat fără intersecții în plan, finit sau infinit, poate fi colorat cu patru culori. Mai general, orice graf infinit pentru care orice subgraf finit este plan poate fi din nou colorat cu patru culori [14] [15]
Teorema de Bruijn-Erdős poate fi folosită pentru a răspunde la întrebarea lui Gelvin cu privire la teorema valorii intermediare pentru numerele cromatice grafice — pentru orice două numere finite j < k și orice grafic G cu număr cromatic k , există un subgraf de G cu numărul cromatic j . Pentru a vedea acest lucru, să găsim un subgraf finit al lui G cu același număr cromatic ca și G însuși și apoi să eliminăm vârfurile unul câte unul până când obținem numărul cromatic j . Cu toate acestea, cazul numerelor cromatice infinite este mai complicat - este în concordanță cu teoria mulțimilor că există un grafic cu ℵ 2 vârfuri și număr cromatic ℵ 2 , dar niciun subgraf cu număr cromatic ℵ 1 [16] [17] .
Rado [18] a demonstrat următoarea teoremă, care poate fi considerată ca o generalizare a teoremei lui de Bruijn-Erdős. Fie V o mulțime infinită, de exemplu, mulțimea vârfurilor dintr-un grafic infinit. Pentru fiecare element v al lui V , fie c v un set finit de culori. Mai mult, pentru orice submulțime finită S a mulțimii V , alegem o colorare C S a submulțimii S în care culoarea fiecărui element v al submulțimii S aparține lui c v . Apoi există o colorare globală χ a tuturor V cu proprietatea că orice mulțime finită S are o supramulțime finită T pe care χ și C T sunt de acord. În special, dacă alegem o k -colorare pentru orice subgraf finit al unui graf infinit G , atunci există o k -colorare a lui G în care fiecare graf finit are un supergraf mai mare a cărui colorare este în concordanță cu colorarea întregului graf [ 19] .
Dacă graficul nu are un număr cromatic finit, atunci din teorema de Bruijn-Erdős rezultă că graficul trebuie să conțină subgrafe finite pentru fiecare număr cromatic posibil. Cercetătorii au explorat și alte condiții pe subgrafe. De exemplu, graficele cromatice nemărginite trebuie să conțină, de asemenea, orice graf bipartit finit ca subgraf. Cu toate acestea, ele pot avea o circumferință impară arbitrar mare [20] [17] .
Teorema lui de Bruijn-Erdős se aplică, de asemenea, direct problemelor de colorare a hipergrafului , unde fiecare hipermuchie trebuie să aibă vârfuri de mai mult de o culoare. În ceea ce privește graficele, un hipergraf are o k -colorare dacă și numai dacă oricare dintre subhipergrafele sale finite are o k -colorare [21] . Un caz special teoremei de compactitate a lui Kurt Gödel afirmă că o mulțime de instrucțiuni de ordinul întâi are un model dacă și numai dacă orice submulțime finită are un model.
Teorema poate fi generalizată la cazurile în care numărul de culori este un număr cardinal infinit — dacă κ este un număr cardinal strict compact , atunci pentru orice grafic G și număr cardinal μ < κ, G are un număr cromatic care nu depășește μ dacă și numai dacă atunci când subgrafele sale cu cardinalitate mai mică decât κ au un număr cromatic care nu depășește μ [22] . Teorema originală de Bruijn-Erdős este un caz special κ = ℵ 0 al acestei generalizări, deoarece o mulțime este finită dacă și numai dacă cardinalitatea sa este mai mică de ℵ 0 . Totuși, unele ipoteze, cum ar fi compactitatea strictă a numărului cardinal al mulțimii, sunt necesare - dacă ipoteza continuumului generalizat este adevărată, atunci pentru orice cardinal infinit γ , există un grafic G de cardinalitate (2 γ ) + , cum ar fi că numărul cromatic al graficului G este mai mare decât γ , dar orice subgraf grafic G , a cărui mulțime de vârfuri are cardinalitate mai mică decât G , are un număr cromatic care nu depășește γ [23] . Lake [24] descrie grafuri infinite care satisfac generalizarea teoremei lui de Bruijn-Erdős ca grafuri al căror număr cromatic este egal cu cel mai mare număr cromatic de subgrafe strict mai mici.