Teorema de De Bruijn–Erdős (teoria de grafs)

En teoria de grafs, el teorema de De Bruijn–Erdős relaciona la coloració de grafs d'un graf infinit amb el mateix problema dels seus subgrafs finits. Afirma que, quan es poden acolorir tots els subgrafs finits amb $c$ colors, el mateix passa amb tot el graf. El teorema va ser demostrat per Nicolaas de Bruijn i Paul Erdős (1951), dels quals rep el nom.

El teorema de De Bruijn–Erdős té diverses demostracions diferents, totes depenent d'alguna manera de l'axioma de l'elecció. Les seves aplicacions inclouen estendre el teorema dels quatre colors i el teorema de Dilworth de grafs finits i conjunts parcialment ordenats a infinits, i reduir el problema de Hadwiger-Nelson sobre el nombre cromàtic del pla a un problema sobre gràfics finits. Es pot generalitzar des de nombres finits de colors fins a conjunts de colors la cardinalitat dels quals és un cardinal fortament compacte.

Definicions i enunciat

Un graf no dirigit és un objecte matemàtic format per un conjunt de vèrtexs i un conjunt d'arestes que enllacen parells de vèrtexs. Els dos vèrtexs associats a cada aresta s'anomenen «extrems». El graf és finit quan els seus vèrtexs i arestes formen conjunts finits, i infinits en cas contrari. Una coloració de grafs associa cada vèrtex amb un color extret d'un conjunt de colors, de manera que cada aresta té dos colors diferents als seus extrems. Un objectiu freqüent en la coloració de gràfics és minimitzar el nombre total de colors que s'utilitzen; el «nombre cromàtic» d'un graf és aquest nombre mínim de colors. El teorema dels quatre colors estableix que cada graf finit que es pot dibuixar sense encreuaments en el pla euclidià necessita com a màxim quatre colors; tanmateix, alguns grafs amb connectivitat més complicada requereixen més de quatre colors. És una conseqüència de l'axioma de l'elecció que el nombre cromàtic està ben definit per a grafs infinits, però per a aquests grafs el nombre cromàtic podria ser en si mateix un nombre cardinal infinit.

Un subgraf d'un graf és un altre graf obtingut a partir d'un subconjunt dels seus vèrtexs i d'un subconjunt de les seves arestes. Si el graf més gran està acolorit, es pot utilitzar el mateix color per al subgraf. Per tant, el nombre cromàtic d'un subgraf no pot ser més gran que el nombre cromàtic de tot el graf. El teorema de De Bruijn-Erdős es refereix als nombres cromàtics de grafs infinits, i mostra que (de nou, assumint l'axioma de l'elecció) es poden calcular a partir dels nombres cromàtics dels seus subgrafs finits. Afirma que, si els nombres cromàtics dels subgrafs finits d'un graf $G$ tenen un valor màxim finit $c$, el nombre cromàtic de $G$ és exactament $c$. D'altra banda, si no hi ha cap límit superior finit en els nombres cromàtics dels subgrafs finits de $G$, el nombre cromàtic de $G$ ha de ser infinit.

Aplicacions

La motivació original d'Erdős a l'hora d'estudiar aquest problema va ser estendre dels grafs finits a infinits el teorema que, sempre que un graf tingui una orientació amb un grau $k$ superior finit, també té una $(2k+1)$-coloració. Per als grafs finits això succeeix perquè aquests grafs sempre tenen un vèrtex de grau $2k$ com a màxim, que es pot acolorir amb un de $2k+1$ colors després que tots els vèrtexs restants s'acoloreixin de manera recursiva. Els grafs infinits amb aquesta orientació no sempre tenen un vèrtex de baix grau (per exemple, les xarxes de Bethe tenen $k=1$, però un grau mínim arbitràriament gran), de manera que aquest argument requereix que el graf sigui finit. Però el teorema de De Bruijn-Erdős mostra que existeix una $(2k+1)$-coloració fins i tot per a grafs infinits.

Un pla de set colors i el graf de Moser de quatre cromàtics dibuixats com a graf de distància unitat en el pla, proporcionant límits superiors i inferiors per al problema de Hadwiger-Nelson

Una altra aplicació del teorema de De Bruijn-Erdős és al problema de Hadwiger-Nelson, que pregunta quants colors es necessiten per acolorir els punts del pla euclidià de manera que cada dos punts que es troben a una distància unitat tinguin colors diferents. Aquest és un problema de coloració de grafs per a un graf infinit que té un vèrtex per a cada punt del pla i una aresta per cada dos punts la distància euclidiana dels quals és exactament una. Els subgrafs d'aquest grafs s'anomenen «grafs de distància unitat». Un graf de distància unitat de set vèrtex, el graf de Moser, requereix quatre colors; el 2018, es van trobar grafs de distància d'unitats molt més grans que requereixen cinc colors. Tot el graf infinit té una coloració coneguda amb set colors basat en un mosaic hexagonal del pla. Per tant, el nombre cromàtic del pla ha de ser 5, 6 o 7, però no se sap quin d'aquests tres nombres és el valor correcte. El teorema de De Bruijn-Erdős mostra que, per a aquest problema, existeix un graf de distància unitat finita amb el mateix nombre cromàtic que tot el pla, de manera que si el nombre cromàtic és superior a cinc, aquest fet es pot demostrar mitjançant un càlcul finit.

El teorema de De Bruijn-Erdős també es pot utilitzar per estendre el teorema de Dilworth de conjunts parcialment ordenats finits a infinits. El teorema de Dilworth estableix que l'amplada d'un ordre parcial (el nombre màxim d'elements en un conjunt d'elements mútuament incomparables) és igual al nombre mínim de cadenes (subconjunts totalment ordenats) en què es pot dividir l'ordre parcial. Una partició en cadenes es pot interpretar com una coloració del graf d'incomparabilitat de l'ordre parcial. Aquest és un graf amb un vèrtex per a cada element de l'ordre i una aresta per a cada parell d'elements incomparables. Utilitzant aquesta interpretació de color, juntament amb una demostració separada del teorema de Dilworth per a conjunts parcialment ordenats finits, és possible demostrar que un conjunt parcialment ordenat infinit té una amplada finita $w$ si i només si té una partició en $w$ cadenes.

De la mateixa manera, el teorema de De Bruijn-Erdős amplia el teorema dels quatre colors des de grafs planars finits fins a grafs planars infinits. Cada graf pla finit es pot pintar amb quatre colors, segons el teorema dels quatre colors. Aleshores, el teorema de De Bruijn-Erdős mostra que cada graf que es pot dibuixar sense encreuaments en el pla, finit o infinit, es pot pintar amb quatre colors. De manera més general, cada graf infinit per al qual tots els subgrafs finits són plans pot tornar a ser de quatre colors.

Demostracions

La demostració original del teorema de De Bruijn-Erdős, de De Bruijn, utilitzava la inducció transfinita.

[Gottschalk 1951] va proporcionar la següent demostració molt breu, basada en el teorema de compacitat de Tíkhonov en topologia. Suposem que, per al graf infinit donat $G$, cada subgraf finit és $k$-colorable, i fem que $X$ sigui l'espai de totes les tasques dels $k$-colors als vèrtexs de $G$ (independentment de si formen una coloració vàlida). Aleshores $X$ es pot donar una topologia com a espai de producte $k^{V(G)}$, on $V(G)$ denota el conjunt de vèrtexs del graf. Segons el teorema de Tychonoff, aquest espai topològic és compacte. Per a cada subgraf finit $F$ de $G$, fem que $X_{F}$ sigui el subconjunt de $X$ consistent en assignacions de colors que acoloreixin vàlidament $F$. Llavors, el sistema de conjunts $X_{F}$ és una família de conjunts tancats amb la propietat de la intersecció finita, de manera que per compacitat té una intersecció no buida. Cada membre d'aquesta intersecció és un color vàlid de $G$.

Una prova diferent utilitzant el lema de Zorn va ser donada per Lajos Pósa, i també en la tesi doctoral Ph.D. de 1951 de Gabriel Andrew Dirac. Si $G$ és un graf infinit en el qual es troba cada subgraf finit $k$-colorable, llavors pel lema de Zorn és un subgraf d'un graf màxim $M$ amb la mateixa propietat (una a la qual no es poden afegir més arestes sense fer que algun subgraf finit requereixi més de $k$ colors). La relació binària de no adjacència en $M$ és una relació d'equivalència i les seves classes d'equivalència proporcionen una $k$-coloració de $G$. Tanmateix, aquesta demostració és més difícil de generalitzar que la prova de compacitat.

El teorema també es pot demostrar mitjançant ultrafiltres o anàlisis no estàndard. Dóna una demostració per a grafs amb un nombre comptable de vèrtexs basat en el lema de l'infinit de Kőnig.

Dependència de l'elecció

Totes les demostracions del teorema de De Bruijn-Erdős utilitzen alguna forma de l'axioma de l'elecció. És necessària alguna forma d'aquesta suposició, ja que existeixen models de matemàtiques en què tant l'axioma de l'elecció com el teorema de De Bruijn-Erdős són falsos. Més precisament, [Mycielski 1961] va demostrar que el teorema és una conseqüència del teorema de l'ideal primer booleà, una propietat que està implicada per l'axioma de l'elecció però més feble que l'axioma complet de l'elecció, i [Läuchli 1971] va demostrar que el teorema de De Bruijn-Erdős i el teorema de l'ideal primer booleà són equivalents en potència axiomàtica.

També es pot demostrar que el teorema de De Bruijn-Erdős per a grafs comptables és equivalent en poder axiomàtic, dins d'una teoria de l'aritmètica de segon ordre, al lema de l'infinit de Kőnig.

Per a un contraexemple del teorema en models de teoria de conjunts sense elecció, fem que $G$ sigui un graf infinit en què els vèrtexs representen tots els nombres reals possibles. En $G$, es connecta cada dos nombres reals $x$ i $y$ per una vora sempre que un dels valors $|x-y|\pm {\sqrt {2}}$  és un nombre racional. De manera equivalent, en aquest graf existeixen arestes entre tots els nombres reals $x$ i tots els nombres reals de la forma $x+q\pm {\sqrt {2}}$, per a nombres racionals $q$. Cada camí d'aquest graf, començant per qualsevol nombre real $x$, alterna números que difereixen de $x$ per un nombre racional més un múltiple parell de ${\sqrt {2}}$ i números que difereixen de $x$ per un nombre racional més un múltiple senar de ${\sqrt {2}}$.

Aquesta alternança evita que $G$ contingui qualsevol cicle de longitud senar, de manera que cadascun dels seus subgrafs finits només requereix dos colors. Tanmateix, en el model de Solovay en què cada conjunt de nombres reals és mesurable per Lebesgue, $G$ requereix infinits colors, ja que en aquest cas cada classe de color ha de ser un conjunt mesurable i es pot demostrar que cada conjunt mesurable de nombres reals sense arestes en $G$ ha de tenir la mesura zero. Per tant, en el model de Solovay, el nombre cromàtic (infinit) de tots $G$ és molt més gran que el nombre cromàtic dels seus subgrafs finits (com a màxim dos).

Generalitzacions

[Rado 1949] demostra el següent teorema, que es pot veure com una generalització del teorema de De Bruijn-Erdős. Fem que $V$ siguir un conjunt infinit, per exemple el conjunt de vèrtexs en un gràfic infinit. Per a cada element $v$ de $V$, fem que $c_{v}$ sigui un conjunt finit de colors. A més, per a cada subconjunt finit $S$ de $V$, s'escull algun color en particular $C_{S}$ de $S$, en què el color de cada element $v$ de $S$ pertany a $c_{v}$. Aleshores hi ha una coloració global $\chi$ de tots $V$ amb la propietat que tot conjunt finit $S$ té un superconjunt finit $T$ en la qual $\chi$ i $C_{T}$ es consenteixen. En particular, si escollim una $k$-coloració per a cada subgraf finit d'un graf infinit $G$, llavors hi ha a $k$-coloració de $G$ en què cada graf finit té un supergraf més gran la coloració del qual coincideix amb la coloració de tot el graf.

Si un graf no té un nombre cromàtic finit, aleshores el teorema de De Bruijn-Erdős implica que ha de contenir subgrafs finits de tots els nombres cromàtics finits possibles. Els investigadors també han investigat altres condicions sobre els subgrafs que es veuen obligats a produir-se en aquest cas. Per exemple, els grafs cromàtics sense límits també han de contenir tots els possibles grafs bipartits finits com a subgraf. Tanmateix, poden tenir un cinturó imparell arbitràriament gran i, per tant, poden evitar qualsevol conjunt finit de subgrafs no bipartits.

El teorema de De Bruijn-Erdős també s'aplica directament als problemes de coloració d'hipergrafs, on es requereix que cada hiperaresta tingui vèrtexs de més d'un color. Pel que fa als grafs, un hipergraf té una $k$-coloració si i només si cadascun dels seus subhipergrafs finits té una $k$-coloració. És un cas especial del teorema de compacitat de Kurt Gödel, que afirma que un conjunt de sentències de primer ordre té un model si i només si cada subconjunt finit té un model. Més concretament, el teorema de De Bruijn-Erdős es pot interpretar com la compacitat de les estructures de primer ordre els valors no lògics de les quals són qualsevol conjunt finit de colors i l'únic predicat de les quals sobre aquests valors és la desigualtat.

El teorema també es pot generalitzar a situacions en què el nombre de colors és un nombre cardinal infinit. Si $\kappa$ és un cardinal fortament compacte, llavors per a cada graf $G$ i número cardinal $\mu <\kappa$, $G$ té un nombre cromàtic com a màxim $\mu$ si i només si cadascun dels seus subgrafs de cardinalitat és inferior a $\kappa$ té un nombre cromàtic com a màxim $\mu$. El teorema original de De Bruijn-Erdős és el cas $\kappa =\aleph _{0}$ d'aquesta generalització, ja que un conjunt és finit si i només si la seva cardinalitat és menor que $\aleph _{0}$. No obstant això, cal supòsits com el de ser un cardinal fortament compacte: si la hipòtesi del continu generalitzat és certa, aleshores per a cada cardinal infinit $\gamma$, existeix un graf $G$ de cardinalitat $(2^{\gamma })^{+}$ tal que el nombre cromàtic de $G$ és més gran que $\gamma$, però de manera que cada subgraf de $G$ el conjunt de vèrtexs del qual té una potència menor que $G$ té un nombre cromàtic com a màxim $\gamma$.

[Lake 1975] caracteritza els grafs infinits que obeeixen a una generalització del teorema de De Bruijn–Erdős, ja que el seu nombre cromàtic és igual al nombre cromàtic màxim dels seus subgrafs estrictament més petits.

Bibliografia

• Barnette, David. Map Coloring, Polyhedra, and the Four-Color Problem (en anglès). 8. Mathematical Association of America, 1983, p. 160 (Dolciani Mathematical Expositions). ISBN 978-0-88385-309-2. 
• Cowen, Robert H «Two hypergraph theorems equivalent to BPI» (en anglès). Notre Dame Journal of Formal Logic, 31(2), 1990, pàg. 232-240. DOI: 10.1305/ndjfl/1093635418.
• Cowen, Robert; Hechler, Stephen H; Mihók, Peter «Graph coloring compactness theorems equivalent to BPI» (en anglès). Scientiae Mathematicae Japonicae, 56(2), 2002, pàg. 213-223.
• De Bruijn, N. G; Erdős, P «A colour problem for infinite graphs and a problem in the theory of relations» (PDF) (en anglès). Indagationes Mathematicae. Nederl. Akad. Wetensch. Proc. Ser. A, 54, 1951, pàg. 371-373. Arxivat de l'original el 2016-03-10. DOI: 10.1016/S1385-7258(51)50053-7 [Consulta: 1r gener 2024].
• Erdős, Paul «Some remarks on set theory» (PDF) (en anglès). Proceedings of the American Mathematical Society, 1(2), 1950, pàg. 127-141. DOI: 10.2307/2031913. JSTOR: 2031913.
• Erdős, Paul; Hajnal, András «On chromatic number of graphs and set-systems» (PDF) (en anglès). Acta Mathematica Academiae Scientiarum Hungaricae, 17(1)-17(2), 1966, pàg. 61-99. DOI: 10.1007/BF02020444.
• Erdős, Paul; Hajnal, András «On chromatic number of infinite graphs» (PDF) (en anglès). Theory of Graphs Proc. Colloq.. Academic Press [Tihany], 1968, pàg. 83-98.
• Gottschalk, W. H «Choice functions and Tychonoff's theorem» (en anglès). Proceedings of the American Mathematical Society, 2(1), 1951, pàg. 172. DOI: 10.2307/2032641. JSTOR: 2032641.
• Harzheim, Egbert. Ordered sets (en anglès). 7. Nova York: Springer, 2005, p. 59 (teorema 5.5) (Advances in Mathematics). ISBN 978-0-387-24219-8. 
• Hurd, Albert E; Loeb, Peter A. An introduction to nonstandard real analysis (en anglès). 118. Orlando, FL: Academic Press, 1985, p. 92 (teorema 5.14) (Pure and Applied Mathematics). ISBN 978-0-12-362440-1. 
• Jensen, Tommy R; Toft, Bjarne. Graph coloring problems (en anglès). Nova York: John Wiley & Sons Inc, 1995, p. 2-3 (teorema 1) (Wiley-Interscience Series in Discrete Mathematics and Optimization). ISBN 978-0-471-02865-7. 
• Kanamori, Akihiro. The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings (en anglès). Springer-Verlag, 2008, p. 37 (Springer Monographs in Mathematics). ISBN 978-3-540-88866-6. 
• Komjáth, Péter «The chromatic number of infinite graphs. A survey» (PDF) (en anglès). Discrete Mathematics, 311(15), 2011, pàg. 1448-1450. Arxivat de l'original el 2021-06-27. DOI: 10.1016/j.disc.2010.11.004 [Consulta: 1r gener 2024].
• Lake, John «A generalization of a theorem of de Bruijn and Erdős on the chromatic number of infinite graphs» (en anglès). Journal of Combinatorial Theory, 18(2), 1975, pàg. 170-174. DOI: 10.1016/0095-8956(75)90044-1.
• Lamb, Evelyn «Decades-old graph problem yields to amateur mathematician» (en anglès). Quanta Magazine, 17-04-2018.
• Läuchli, H «Coloring infinite graphs and the Boolean prime ideal theorem» (en anglès). Israel Journal of Mathematics, 9(4), 1971, pàg. 422-429. DOI: 10.1007/BF02771458.
• Luxemburg, W. A. J «A remark on a paper by N. G. de Bruijn and P. Erdős» (en anglès). Indagationes Mathematicae, 24, 1962, pàg. 343-345. DOI: 10.1016/S1385-7258(62)50033-4.
• Mycielski, Jan «Some remarks and problems on the colouring of infinite graphs and the theorem of Kuratowski» (en anglès). Acta Mathematica Academiae Scientiarum Hungaricae, 12(1)-12(2), 1961, pàg. 125-129. DOI: 10.1007/BF02066677.
• Nash-Williams, C. St. J. A «Infinite graphs. Asurvey» (en anglès). Journal of Combinatorial Theory, 3(3), 1967, pàg. 286-301. DOI: 10.1016/s0021-9800(67)80077-2.
• Rado, R «Axiomatic treatment of rank in infinite sets» (en anglès). Canadian Journal of Mathematics, 1(4), 1949, pàg. 337-343. DOI: 10.4153/cjm-1949-031-1.
• Rautenberg, Wolfgang. A Concise Introduction to Mathematical Logic (en anglès). Springer-Verlag, 2010, p. 32 (Universitext). DOI 10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6. 
• Rorabaugh, Danny; Tardif, Claude; Wehlau, David «Logical compactness and constraint satisfaction problems» (en anglès). Logical Methods in Computer Science, 13(1), 2017, pàg. 1:1-1:11. arXiv: 1609.05221. DOI: 10.23638/LMCS-13(1:1)2017.
• Schmerl, James H «Graph coloring and reverse mathematics» (en anglès). Mathematical Logic Quarterly, 46(4), 2000, pàg. 543-548. DOI: 10.1002/1521-3870(200010)46:4<543::AID-MALQ543>3.0.CO;2-E.
• Shelah, Saharon; Soifer, Alexander «Axiom of choice and chromatic number of the plane» (en anglès). Journal of Combinatorial Theory, 103(2), 2003, pàg. 387-391. DOI: 10.1016/S0097-3165(03)00102-X.
• Soifer, Alexander. The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of its Creators (en anglès). Nova York York: Springer, 2008. ISBN 978-0-387-74640-1.