Twierdzenie De Bruijn-Erdős w teorii grafów , świadczy Nicolaas Govert de Bruijn i Paul Erdős , ustali, że (dla dowolnej liczby naturalnej k ) dla nieskończonej undirected wykres, aby mieć zabarwienie przez k kolorów, wystarczy, że "jest to sprawa dla wszystkich jego skończonych podgrafów. Innymi słowy: każdy graf k- krytyczny (en) (tj. Którego kolorystyka ma co najmniej k kolorów, ale wszystkie odpowiednie podgrafy są k -1-kolorowalne) ma skończoną liczbę wierzchołków.
Oryginalny dowód De Bruijna wykorzystywał indukcję pozaskończoną .
Gottschalk dostarczył następujące dowody, bardzo krótki, w oparciu o twierdzenie o zwartości z Tichonowa w topologii . Oznaczmy przez K zbiór k kolorów i niech G = ( V , E ) będzie wykresem. Zgodnie z twierdzeniem Tychonoffa, przestrzeń iloczynu X = K V wszystkich odwzorowań od V do K jest zwarta . Dla każdego odwzorowania f z części V do K , elementy X, które pokrywają się z f w tej części, tworzą zamknięte . W konsekwencji, dla dowolnego skończonego podgrafu F z G , zbiór X F elementów X, których ograniczenie do F jest k- kolorowaniem, jest zamknięty (przez skończoną sumę). Jeśli wszystkie te F są k- kolorowalne, wszystkie te X F tworzą rodzinę zamkniętych posiadającą właściwość skończonego przecięcia (in) , tj. Każda skończona podrodzina jest niepustą częścią przecięcia. Przez zwartość ich przecięcie nie jest pusty , albo że skrzyżowanie jest nikt inny niż wszystkie k -colorations z G .
Innym dowodem, używając lematu Zorna została przyznana przez Lajos POSA (w) , a także tezy doktora w 1951 roku Gabriel Andrew Dirac . Jeśli jakikolwiek skończony podgraf G jest k -kolorowalny, to według lematu Zorna G jest częściowym wykresem maksymalnego grafu M dla tej właściwości. Binarny związek braku przylegania w M jest stosunek równoważności którego klas stanowią k -coloring z G . Jednak dowód ten jest trudniejszy do uogólnienia niż ten przez zwięzłość.
Twierdzenie można również zademonstrować za pomocą ultrafiltrów lub niestandardowej analizy .
W szczególnym przypadku, w którym V jest policzalne , Crispin Nash-Williams podaje dowód oparty na lemacie Königa .
Wszystkie dowody twierdzenia De Bruijna-Erdősa używają jakiejś formy aksjomatu wyboru . Jest to nieuniknione, ponieważ istnieją modele matematyczne, które nie weryfikują tego twierdzenia (ani tego aksjomatu).
Na przykład k = 2, niech G będzie wykres, którego wierzchołki są liczbami rzeczywistymi, a w którym dwa rzeczywiste liczby x i y są połączone przez krawędź, gdy | x - y | ± √ 2 to liczba wymierna , tj. Wierzchołki połączone z rzeczywistym x są liczbami rzeczywistymi postaci x ± ( √ 2 + q ) z q wymierną. Zdefiniujmy na wierzchołkach G relację równoważności przez: dwa wierzchołki są równoważne, jeśli ich różnica jest sumą liczby wymiernej i wielokrotności pierwiastka kwadratowego z 2 przez parzystą liczbę całkowitą. Zatem w dwukolorowym G , dwa równoważne wierzchołki muszą być tego samego koloru. Wykres utworzony przez zawężenie każdej klasy równoważności do pojedynczego wierzchołka tworzy następnie nieskończone sprzężenie i może być łatwo dwukolorowy przy użyciu wybranego aksjomatu. Dlatego każdy skończony podgraf G jest dwukolorowy. Możemy jednak pokazać, że w każdym zabarwieniu G , każdy monochromatyczny mierzalny zbiór Lebesgue'a ma koniecznie miarę zerową. Wynika z tego, że w modelu Solovaya (in) (w którym mierzalny jest dowolny zbiór liczb rzeczywistych), G można pokolorować tylko nieskończoną liczbą kolorów.
Twierdzenie De Bruijna-Erdősa dla grafów policzalnych jest równoważne, w arytmetyce drugiego rzędu , lematowi Königa.
Aplikacja twierdzenia De Bruijn-Erdös dotyczy problemu Hadwiger-Nelson o liczbie chromatycznej z wykresem od odległości jednostki w euklidesowej płaszczyzny (wierzchołki są punkty płaszczyźnie, a dwa wierzchołki są połączone za pomocą krawędzi, gdy ich odległość euklidesowa jest 1). Niektóre z jego podgrafów, jak wrzeciono Mosera , nie dają się pokolorować mniej niż 4 kolory. Sam wykres ma 7-kolorystykę, opartą na sześciokątnej teselacji płaszczyzny. Dlatego liczba chromatyczna na tym wykresie jest jedną z czterech liczb całkowitych 4, 5, 6 lub 7, ale nie wiadomo, która z nich. Twierdzenie De Bruijna-Erdősa pokazuje jednak, że istnieje skończony wykres jednostek odległości, którego liczba chromatyczna jest taka sama jak całej płaszczyzny, więc jeśli ta ostatnia jest ściśle większa niż 4, to fakt ten można wykazać za pomocą skończonych obliczeń.
Twierdzenie De Bruijna-Erdősa można również wykorzystać do rozszerzenia twierdzenia Dilwortha na (częściowo) uporządkowane zbiory , od przypadku skończonego do przypadku nieskończonego. To twierdzenie ustanawia, że szerokość dowolnego skończonego rzędu (tj. Maksymalny rozmiar antychain ) jest równa minimalnej wielkości podziału w łańcuchach . Podział na łańcuchy można interpretować jako zabarwienie wykresu nieporównywalności rzędu (graf, którego wierzchołki są elementami uporządkowanego zbioru, a krawędzie łączą pary nieporównywalnych elementów). Z tej interpretacji iz twierdzenia Dilworth, możemy wykazać, dzięki De Bruijn-Erdős twierdzenia, że każdy nieskończony porządek szerokości mniejszej niż lub równą liczbę całkowitą w jest sumą wag łańcuchów rozłącznych.
Podobnie, twierdzenie De Bruijna-Erdősa umożliwia rozszerzenie twierdzenia o czterech kolorach na grafach planarnych od przypadku skończonego do przypadku nieskończonego: dowolnego nieskończonego grafu płaskiego lub bardziej ogólnie dowolnego grafu nieskończonego, którego skończone podgrafy są płaskie, można pokolorować 4 kolorami.
Można go również użyć, aby odpowiedzieć na pytanie Freda Galvina (en) dotyczące „ twierdzenia o pośrednich wartościach liczb chromatycznych grafów”: dla dowolnego wykresu G liczby chromatycznej k i dowolnej liczby całkowitej j <k , G ma pod- chromatyczny wykres liczbowy j . Aby go znaleźć, wystarczy wziąć skończony podgraf G o liczbie chromatycznej k i usuwać jeden po drugim wierzchołki, aż liczba chromatyczna podgrafu osiągnie wartość j . Jednakże, sytuacja liczb nieskończonych chromatycznej jest bardziej skomplikowane: Teoria zestaw jest zgodne z istnieniem chromatycznej wykresie liczba (i liczby wierzchołków) równy ℵ 2 , nie mając numer podgrafu chromatycznej równe. ℵ 1 .
Richard Rado (w 1949 r.) Zademonstrował następujące twierdzenie, które uogólnia i wyjaśnia twierdzenie De Bruijn-Erdős. Niech V będzie zbiorem nieskończonym i, dla każdego elementu v z V , zbiorem skończonym c v kolorów. Dla dowolnej skończonej części S z V wybieramy mapę C S z S w zestawie kolorów, tak że kolor każdego elementu v z S należy do c v . Wtedy istnieje mapa χ , zdefiniowana na V całkowitej, taka, że każda skończona część S jest zawarta w skończonej części T, na której χ i C T pokrywają się.
Jeśli liczba chromatyczna grafu G jest nieskończona, to z twierdzenia De Bruijna-Erdősa wynika, że G zawiera, dla każdej liczby całkowitej j , podgraf, którego liczba chromatyczna wynosi j (por. Twierdzenie o wartości pośredniej powyżej ). Naukowcy zbadali również inne konsekwencje na podgrafach G ; na przykład G musi również zawierać dowolny skończony wykres dwudzielny jako podgraf. Jednak G może mieć dowolnie dużą nieparzystą komórkę, a zatem dla dowolnego skończonego zbioru grafów nie- dwudzielnych istnieje G, którego żaden podgraf nie należy do tego zbioru.
Twierdzenie De Bruijna-Erdősa odnosi się również bezpośrednio do problemów kolorowania hipergraphów , gdzie wymagamy, aby dla każdej hiper-krawędzi wierzchołki nie były tego samego koloru: tak jak w przypadku wykresów, hipergraf jest k -kolorowalny wtedy i tylko wtedy, gdy każdy z nich z jego skończonych sub-hipergrafów. Jest to szczególny przypadek twierdzenie o zwartości z Gödel , w którym zestaw pierwszych sprawozdań porządkowych ma modelu , gdy każdy z jej gotowych części a.
Możemy również uogólnić twierdzenie na sytuacje, w których liczba kolorów jest nieskończoną liczbą kardynalną : jeśli κ jest silnie zwartym kardynałem (in) , to dla dowolnego grafu G i dowolnego kardynalnego μ <κ liczba chromatyczna G jest mniejsza lub równa μ wtedy i tylko wtedy, gdy to samo jest prawdą dla każdego z jego podgrafów o liczności dokładnie mniejszej niż κ. Oryginalne twierdzenie De Bruijna-Erdősa jest przypadkiem κ = ℵ 0 tego uogólnienia. Ale to wymaga hipotezy podobnej do hipotezy o silnej zwartości κ: w ramach uogólnionej hipotezy kontinuum dla dowolnego nieskończonego kardynalnego γ istnieje wykres G o kardynałach (2 γ ) +, którego liczba chromatyczna jest ściśle większa niż γ , ale wszystkie podgrafy, które są ściśle mniejsze (pod względem liczby wierzchołków) niż wykres, mają liczbę chromatyczną mniejszą lub równą γ . Lake charakteryzuje grafy nieskończone, dla których prawdziwe jest uogólnienie twierdzenia De Bruijn-Erdősa w tym sensie, że ich liczba chromatyczna jest równa maksimum liczb chromatycznych ich ściśle mniejszych podgrafów.