Teorema de De Bruijn-Erdős (teoría de grafos)

Sobre la coloración de gráficos infinitos

En teoría de grafos , el teorema de De Bruijn-Erdős relaciona la coloración de un grafo infinito con el mismo problema en sus subgrafos finitos . Afirma que, cuando todos los subgrafos finitos pueden colorearse con colores, lo mismo es cierto para todo el grafo. El teorema fue demostrado por Nicolaas Govert de Bruijn y Paul Erdős (1951), de quienes recibe el nombre. ${\displaystyle c}$

El teorema de De Bruijn–Erdős tiene varias demostraciones diferentes, todas ellas dependiendo de algún modo del axioma de elección . Sus aplicaciones incluyen la extensión del teorema de los cuatro colores y del teorema de Dilworth desde grafos finitos y conjuntos parcialmente ordenados a los infinitos, y la reducción del problema de Hadwiger–Nelson sobre el número cromático del plano a un problema sobre grafos finitos. Puede generalizarse desde números finitos de colores a conjuntos de colores cuya cardinalidad sea un cardinal fuertemente compacto .

Definiciones y declaraciones

Un grafo no dirigido es un objeto matemático que consiste en un conjunto de vértices y un conjunto de aristas que unen pares de vértices. Los dos vértices asociados con cada arista se denominan sus puntos finales. El grafo es finito cuando sus vértices y aristas forman conjuntos finitos , e infinito en caso contrario. Una coloración de grafos asocia cada vértice con un color extraído de un conjunto de colores, de tal manera que cada arista tiene dos colores diferentes en sus puntos finales. Un objetivo frecuente en la coloración de grafos es minimizar el número total de colores que se utilizan; el número cromático de un grafo es este número mínimo de colores. ^[1] El teorema de los cuatro colores establece que todo grafo finito que se pueda dibujar sin cruces en el plano euclidiano necesita como máximo cuatro colores; sin embargo, algunos grafos con conectividad más complicada requieren más de cuatro colores. ^[2] Es una consecuencia del axioma de elección que el número cromático esté bien definido para grafos infinitos, pero para estos grafos el número cromático podría ser en sí mismo un número cardinal infinito . ^[3]

Un subgrafo de un grafo es otro grafo obtenido a partir de un subconjunto de sus vértices y un subconjunto de sus aristas. Si el grafo más grande está coloreado, se puede usar la misma coloración para el subgrafo. Por lo tanto, el número cromático de un subgrafo no puede ser mayor que el número cromático de todo el grafo. El teorema de De Bruijn–Erdős se refiere a los números cromáticos de grafos infinitos y muestra que (de nuevo, asumiendo el axioma de elección) se pueden calcular a partir de los números cromáticos de sus subgrafos finitos. Afirma que, si los números cromáticos de los subgrafos finitos de un grafo tienen un valor máximo finito , entonces el número cromático de sí mismo es exactamente . Por otro lado, si no hay un límite superior finito en los números cromáticos de los subgrafos finitos de , entonces el número cromático de sí mismo debe ser infinito. ^[4] ${\displaystyle G}$ ${\displaystyle c}$ ${\displaystyle G}$ ${\displaystyle c}$ ${\displaystyle G}$ ${\displaystyle G}$

Aplicaciones

La motivación original de Erdős al estudiar este problema fue extender de grafos finitos a grafos infinitos el teorema de que, siempre que un grafo tiene una orientación con un grado de salida máximo finito , también tiene una coloración . Para grafos finitos esto se deduce porque tales grafos siempre tienen un vértice de grado como máximo , que puede colorearse con uno de los colores después de que todos los vértices restantes se coloreen recursivamente. Los grafos infinitos con tal orientación no siempre tienen un vértice de grado bajo (por ejemplo, las redes de Bethe tienen un grado mínimo arbitrariamente grande), por lo que este argumento requiere que el grafo sea finito. Pero el teorema de De Bruijn–Erdős muestra que existe una coloración incluso para grafos infinitos. ^[5] ${\displaystyle k}$ ${\displaystyle (2k+1)}$ ${\displaystyle 2k}$ ${\displaystyle 2k+1}$ ${\displaystyle k=1}$ ${\displaystyle (2k+1)}$

Una coloración de siete colores del plano y el huso de Moser de cuatro colores dibujado como un gráfico de distancia unitaria en el plano, que proporciona límites superiores e inferiores para el problema de Hadwiger-Nelson

Otra aplicación del teorema de De Bruijn–Erdős es el problema de Hadwiger–Nelson , que pregunta cuántos colores se necesitan para colorear los puntos del plano euclidiano de modo que cada dos puntos que estén separados por una unidad de distancia tengan colores diferentes. Este es un problema de coloración de grafos para un grafo infinito que tiene un vértice para cada punto del plano y una arista para cada dos puntos cuya distancia euclidiana es exactamente uno. Los subgrafos inducidos de este grafo se denominan grafos de distancia unitaria . Un grafo de distancia unitaria de siete vértices, el huso de Moser , requiere cuatro colores; en 2018, se encontraron grafos de distancia unitaria mucho más grandes que requieren cinco colores. ^[6] Todo el grafo infinito tiene una coloración conocida con siete colores basada en un mosaico hexagonal del plano. Por lo tanto, el número cromático del plano debe ser 5, 6 o 7, pero no se sabe cuál de estos tres números es el valor correcto. El teorema de De Bruijn–Erdős muestra que, para este problema, existe un grafo de distancia unitaria finita con el mismo número cromático que todo el plano, por lo que si el número cromático es mayor que cinco, este hecho puede demostrarse mediante un cálculo finito. ^[7]

El teorema de De Bruijn–Erdős también puede utilizarse para extender el teorema de Dilworth de conjuntos parcialmente ordenados finitos a infinitos . El teorema de Dilworth establece que el ancho de un orden parcial (el número máximo de elementos en un conjunto de elementos mutuamente incomparables) es igual al número mínimo de cadenas ( subconjuntos totalmente ordenados ) en los que se puede dividir el orden parcial. Una partición en cadenas puede interpretarse como una coloración del gráfico de incomparabilidad del orden parcial. Este es un gráfico con un vértice para cada elemento del orden y una arista para cada par de elementos incomparables. Utilizando esta interpretación de coloración, junto con una prueba separada del teorema de Dilworth para conjuntos parcialmente ordenados finitos, es posible demostrar que un conjunto parcialmente ordenado infinito tiene un ancho finito si y solo si tiene una partición en cadenas. ^[8] ${\displaystyle w}$ ${\displaystyle w}$

De la misma manera, el teorema de De Bruijn-Erdős extiende el teorema de los cuatro colores de los grafos planos finitos a los grafos planos infinitos. Todo grafo plano finito puede colorearse con cuatro colores, según el teorema de los cuatro colores. El teorema de De Bruijn-Erdős muestra entonces que todo grafo que puede dibujarse sin cruces en el plano, finito o infinito, puede colorearse con cuatro colores. De manera más general, todo grafo infinito para el cual todos los subgrafos finitos sean planos puede colorearse a su vez con cuatro colores. ^[9]

Pruebas

La prueba original del teorema de De Bruijn-Erdős, realizada por De Bruijn, utilizó inducción transfinita . ^[10]

Gottschalk (1951) proporcionó la siguiente prueba muy breve, basada en el teorema de compacidad de Tichonoff en topología. Supóngase que, para el grafo infinito dado , cada subgrafo finito es -coloreable, y sea el espacio de todas las asignaciones de los colores a los vértices de (independientemente de si forman una coloración válida). Entonces puede darse una topología como un espacio producto , donde denota el conjunto de vértices del grafo. Por el teorema de Tichonoff este espacio topológico es compacto . Para cada subgrafo finito de , sea el subconjunto de que consiste en asignaciones de colores que colorean válidamente . Entonces el sistema de conjuntos es una familia de conjuntos cerrados con la propiedad de intersección finita , por lo que por compacidad tiene una intersección no vacía. Cada miembro de esta intersección es una coloración válida de . ^[11] ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle X}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle k^{V(G)}}$ ${\displaystyle V(G)}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle X_{F}}$ ${\displaystyle X}$ ${\displaystyle F}$ ${\displaystyle X_{F}}$ ${\displaystyle G}$

Una prueba diferente que utiliza el lema de Zorn fue dada por Lajos Pósa , y también en la tesis doctoral de 1951 de Gabriel Andrew Dirac . Si es un grafo infinito en el que cada subgrafo finito es -coloreable, entonces por el lema de Zorn es un subgrafo de un grafo maximal con la misma propiedad (uno al que no se pueden agregar más aristas sin causar que algún subgrafo finito requiera más que colores). La relación binaria de no adyacencia en es una relación de equivalencia , y sus clases de equivalencia proporcionan una -coloración de . Sin embargo, esta prueba es más difícil de generalizar que la prueba de compacidad. ^[12] ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle k}$ ${\displaystyle G}$

El teorema también se puede demostrar utilizando ultrafiltros ^[13] o análisis no estándar . ^[14] Nash-Williams (1967) da una prueba para gráficos con un número contable de vértices basado en el lema de infinito de König .

Dependencia de la elección

Todas las demostraciones del teorema de De Bruijn-Erdős utilizan alguna forma del axioma de elección . Alguna forma de este supuesto es necesaria, ya que existen modelos de matemáticas en los que tanto el axioma de elección como el teorema de De Bruijn-Erdős son falsos. Más precisamente, Mycielski (1961) demostró que el teorema es una consecuencia del teorema del ideal primo de Boole , una propiedad que está implícita en el axioma de elección pero es más débil que el axioma de elección completo, y Läuchli (1971) demostró que el teorema de De Bruijn-Erdős y el teorema del ideal primo de Boole son equivalentes en potencia axiomática. ^[15] También se puede demostrar que el teorema de De Bruijn–Erdős para grafos contables es equivalente en potencia axiomática, dentro de una cierta teoría de aritmética de segundo orden , al lema de Kőnig débil. ^[16]

Como contraejemplo del teorema en modelos de teoría de conjuntos sin elección, sea un grafo infinito en el que los vértices representan todos los números reales posibles. En , conecte cada dos números reales y por una arista siempre que uno de los valores sea un número racional . De manera equivalente, en este grafo, existen aristas entre todos los números reales y todos los números reales de la forma , para números racionales . Cada camino en este grafo, comenzando desde cualquier número real , alterna entre números que difieren de por un número racional más un múltiplo par de y números que difieren de por un número racional más un múltiplo impar de . Esta alternancia evita que contenga ciclos de longitud impar, por lo que cada uno de sus subgrafos finitos requiere solo dos colores. Sin embargo, en el modelo de Solovay en el que cada conjunto de números reales es medible según Lebesgue , requiere infinitos colores, ya que en este caso cada clase de color debe ser un conjunto medible y se puede demostrar que cada conjunto medible de números reales sin aristas en debe tener medida cero. Por lo tanto, en el modelo de Solovay, el número cromático (infinito) de todos es mucho mayor que el número cromático de sus subgrafos finitos (como máximo dos). ^[17] ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle |x-y|\pm {\sqrt {2}}}$ ${\displaystyle x}$ ${\displaystyle x+q\pm {\sqrt {2}}}$ ${\displaystyle q}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle {\sqrt {2}}}$ ${\displaystyle x}$ ${\displaystyle {\sqrt {2}}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Generalizaciones

Rado (1949) demuestra el siguiente teorema, que puede verse como una generalización del teorema de De Bruijn–Erdős. Sea un conjunto infinito, por ejemplo el conjunto de vértices en un grafo infinito. Para cada elemento de , sea un conjunto finito de colores. Además, para cada subconjunto finito de , elija una coloración particular de , en la que el color de cada elemento de pertenece a . Entonces existe una coloración global de todos los de con la propiedad de que cada conjunto finito tiene un superconjunto finito en el que y concuerdan. En particular, si elegimos una coloración - para cada subgrafo finito de un grafo infinito , entonces hay una coloración - de en la que cada grafo finito tiene un supergrafo más grande cuya coloración concuerda con la coloración de todo el grafo. ^[18] ${\displaystyle V}$ ${\displaystyle v}$ ${\displaystyle V}$ ${\displaystyle c_{v}}$ ${\displaystyle S}$ ${\displaystyle V}$ ${\displaystyle C_{S}}$ ${\displaystyle S}$ ${\displaystyle v}$ ${\displaystyle S}$ ${\displaystyle c_{v}}$ ${\displaystyle \chi }$ ${\displaystyle V}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle \chi }$ ${\displaystyle C_{T}}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$

Si un grafo no tiene un número cromático finito, entonces el teorema de De Bruijn–Erdős implica que debe contener subgrafos finitos de cada número cromático finito posible. Los investigadores también han investigado otras condiciones en los subgrafos que se ven obligadas a ocurrir en este caso. Por ejemplo, los grafos cromáticos ilimitados también deben contener cada posible grafo bipartito finito como un subgrafo. Sin embargo, pueden tener una circunferencia impar arbitrariamente grande y, por lo tanto, pueden evitar cualquier conjunto finito de subgrafos no bipartitos. ^[19]

El teorema de De Bruijn–Erdős también se aplica directamente a los problemas de coloración de hipergrafos , donde se requiere que cada hiperarista tenga vértices de más de un color. En cuanto a los grafos, un hipergrafo tiene una coloración -si y solo si cada uno de sus subhipergrafos finitos tiene una coloración -. ^[20] Es un caso especial del teorema de compacidad de Kurt Gödel , que establece que un conjunto de oraciones de primer orden tiene un modelo si y solo si cada subconjunto finito de él tiene un modelo. ^[21] Más específicamente, el teorema de De Bruijn–Erdős puede interpretarse como la compacidad de las estructuras de primer orden cuyos valores no lógicos son cualquier conjunto finito de colores y cuyo único predicado sobre estos valores es la desigualdad. ^[22] ${\displaystyle k}$ ${\displaystyle k}$

El teorema también puede generalizarse a situaciones en las que el número de colores es un número cardinal infinito . Si es un cardinal fuertemente compacto , entonces para cada grafo y número cardinal , tiene número cromático como máximo si y solo si cada uno de sus subgrafos de cardinalidad menor que tiene número cromático como máximo . ^[23] El teorema original de De Bruijn–Erdős es el caso de esta generalización, ya que un conjunto es finito si y solo si su cardinalidad es menor que . Sin embargo, es necesaria alguna suposición como la de ser un cardinal fuertemente compacto: si la hipótesis generalizada del continuo es verdadera, entonces para cada cardinal infinito , existe un grafo de cardinalidad tal que el número cromático de es mayor que , pero tal que cada subgrafo de cuyo conjunto de vértices tiene una potencia menor que tiene número cromático como máximo . ^[24] Lake (1975) caracteriza los grafos infinitos que obedecen a una generalización del teorema de De Bruijn–Erdős, en que su número cromático es igual al número cromático máximo de sus subgrafos estrictamente más pequeños. ${\displaystyle \kappa }$ ${\displaystyle G}$ ${\displaystyle \mu <\kappa }$ ${\displaystyle G}$ ${\displaystyle \mu }$ ${\displaystyle \kappa }$ ${\displaystyle \mu }$ ${\displaystyle \kappa =\aleph _{0}}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle \gamma }$ ${\displaystyle G}$ ${\displaystyle (2^{\gamma })^{+}}$ ${\displaystyle G}$ ${\displaystyle \gamma }$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \gamma }$

Notas

1. Para estas definiciones básicas, véase Jensen y Toft (1995), págs. 1-2.
2. Jensen y Toft (1995), pág. 5.
3. Comunidad (2011).
4. Jensen y Toft (1995), Teorema 1, pág. 2.
5. Erdős (1950). Véase en particular la p. 137, donde se enuncia por primera vez el teorema de De Bruijn–Erdős (pero no se demuestra), con una pista de que el lema de Kőnig puede utilizarse para grafos contables.
6. Cordero (2018).
7. Soifer (2008), pág. 39.
8. Harzheim (2005), Teorema 5.6, pág. 60.
9. Barnette (1983). Nash-Williams (1967) establece el mismo resultado para el teorema de los cinco colores para grafos planares numerables, ya que el teorema de los cuatro colores aún no había sido demostrado cuando publicó su estudio, y como la prueba del teorema de De Bruijn-Erdős que él da solo se aplica a grafos numerables. Para la generalización a grafos en los que cada subgrafo finito es planar (demostrado directamente a través del teorema de compacidad de Gödel), véase Rautenberg (2010).
10. Soifer (2008), pág. 236.
11. Jensen y Toft (1995). Gottschalk enuncia su prueba de forma más general como una prueba del teorema de Rado (1949) que generaliza el teorema de De Bruijn-Erdős.
12. Jensen y Toft (1995); Harzheim (2005). Jensen y Toft atribuyen a Gert Sabidussi la observación de que la prueba de Gottschalk es más fácil de generalizar. Soifer (2008, pp. 238-239) ofrece la misma prueba a través del lema de Zorn, redescubierto en 2005 por el estudiante de pregrado Dmytro Karabash.
13. Luxemburgo (1962).
14. Hurd y Loeb (1985).
15. Para conocer esta historia, véase Cowen, Hechler y Mihók (2002). Para una demostración simplificada del teorema de Läuchli realizada por Mycielski, véase Cowen (1990).
16. Schmerl (2000).
17. Sela y Soifer (2003); Soifer (2008), págs. 541–542.
18. Para esta conexión entre el lema de Rado y el teorema de De Bruijn-Erdős, véase, por ejemplo, la discusión que sigue al Teorema A de Nash-Williams (1967).
19. Erdős y Hajnal (1966); Komjath (2011).
20. Soifer (2008), pág. 239.
21. Lake (1975), p. 171: "Es sencillo demostrar [el teorema de De Bruijn–Erdős] utilizando el teorema de compacidad para la lógica de primer orden"
22. Rorabaugh, Tardif y Wehlau (2017).
23. Esto se desprende inmediatamente de la definición de un cardinal fuertemente compacto como un cardinal tal que cada colección de fórmulas de lógica infinitaria, cada una de longitud menor que , que sea satisfacible para cada subcolección de menos de fórmulas, sea satisfacible globalmente. Véase, por ejemplo, Kanamori (2008). ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$
24. Erdős y Hajnal (1968).

Referencias

• Barnette, David (1983), Coloración de mapas, poliedros y el problema de los cuatro colores, Dolciani Mathematical Expositions, vol. 8, Mathematical Association of America , pág. 160, ISBN 978-0-88385-309-2.
• De Bruijn, NG ; Erdős, P. (1951), "Un problema de color para grafos infinitos y un problema en la teoría de relaciones" (PDF) , Nederl. Akad. Wetensch. Proc. Ser. A , 54 : 371–373, doi :10.1016/S1385-7258(51)50053-7, MR  0046630, archivado desde el original (PDF) el 2016-03-10 , consultado el 2010-04-05.
• Cowen, Robert H. (1990), "Dos teoremas de hipergrafos equivalentes a BPI", Notre Dame Journal of Formal Logic , 31 (2): 232–240, doi : 10.1305/ndjfl/1093635418 , MR  1058424.
• Cowen, Robert; Hechler, Stephen H.; Mihók, Peter (2002), "Teoremas de compacidad de coloración de grafos equivalentes a BPI", Scientiae Mathematicae Japonicae , 56 (2): 213–223, CiteSeerX  10.1.1.23.1521 , MR  1922784.
• Erdős, P. (1950), "Algunas observaciones sobre la teoría de conjuntos" (PDF) , Actas de la American Mathematical Society , 1 (2): 127–141, doi :10.2307/2031913, JSTOR  2031913, MR  0035809.
• Erdős, P .; Hajnal, A. (1966), "Sobre el número cromático de gráficos y sistemas de conjuntos" (PDF) , Acta Mathematica Academiae Scientiarum Hungaricae , 17 (1–2): 61–99, doi :10.1007/BF02020444, MR  0193025, S2CID  189780485.
• Erdős, P. ; Hajnal, A. (1968), "Sobre el número cromático de grafos infinitos", Teoría de grafos (Proc. Colloq., Tihany, 1966) (PDF) , Nueva York: Academic Press, pp. 83–98, MR  0263693.
• Gottschalk, WH (1951), "Funciones de elección y teorema de Tychonoff", Actas de la American Mathematical Society , 2 (1): 172, doi :10.2307/2032641, JSTOR  2032641, MR  0040376.
• Harzheim, Egbert (2005), Conjuntos ordenados, Advances in Mathematics, vol. 7, Nueva York: Springer, Teorema 5.5, pág. 59, ISBN 0-387-24219-8, Sr.  2127991.
• Hurd, Albert E.; Loeb, Peter A. (1985), Introducción al análisis real no estándar, Matemáticas puras y aplicadas, vol. 118, Orlando, FL: Academic Press, Teorema 5.14, pág. 92, ISBN 0-12-362440-1, Sr.  0806135.
• Jensen, Tommy R.; Toft, Bjarne (1995), Problemas de coloración de gráficos , Wiley-Interscience Series in Discrete Mathematics and Optimization, Nueva York: John Wiley & Sons Inc., Teorema 1, págs. 2-3, ISBN 0-471-02865-7, Sr.  1304254.
• Kanamori, Akihiro (2008), El infinito superior: grandes cardinales en la teoría de conjuntos desde sus inicios , Springer Monographs in Mathematics (2.ª ed.), Springer-Verlag, pág. 37, ISBN 978-3-540-88866-6.
• Komjáth, Péter (2011), "El número cromático de grafos infinitos: un estudio", Discrete Mathematics , 311 (15): 1448–1450, doi : 10.1016/j.disc.2010.11.004.
• Lake, John (1975), "Una generalización de un teorema de de Bruijn y Erdős sobre el número cromático de grafos infinitos", Journal of Combinatorial Theory , Serie B, 18 (2): 170–174, doi : 10.1016/0095-8956(75)90044-1 , MR  0360335.
• Lamb, Evelyn (17 de abril de 2018), "Un problema gráfico que tiene décadas de antigüedad cede ante un matemático aficionado", Quanta Magazine
• Läuchli, H. (1971), "Coloración de gráficos infinitos y el teorema del ideal primo booleano", Israel Journal of Mathematics , 9 (4): 422–429, doi :10.1007/BF02771458, MR  0288051.
• Luxemburg, WAJ (1962), "Un comentario sobre un artículo de NG de Bruijn y P. Erdős", Indagationes Mathematicae , 24 : 343–345, doi : 10.1016/S1385-7258(62)50033-4 , MR  0140435.
• Mycielski, Jan (1961), "Algunas observaciones y problemas sobre la coloración de grafos infinitos y el teorema de Kuratowski", Acta Mathematica Academiae Scientiarum Hungaricae , 12 (1–2): 125–129, doi :10.1007/BF02066677, MR  0130686, S2CID  120141460.
• Nash-Williams, C. St. JA (1967), "Grafos infinitos: un estudio", Journal of Combinatorial Theory , 3 (3): 286–301, doi : 10.1016/s0021-9800(67)80077-2 , MR  0214501.
• Rado, R. (1949), "Tratamiento axiomático del rango en conjuntos infinitos", Revista canadiense de matemáticas , 1 (4): 337–343, doi : 10.4153/cjm-1949-031-1 , S2CID  124598982.
• Rautenberg, Wolfgang (2010), Una introducción concisa a la lógica matemática , Universitext (3.ª ed.), Springer-Verlag, pág. 32, doi :10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6.
• Rorabaugh, Danny; Tardif, Claude; Wehlau, David (2017), "Compactitud lógica y problemas de satisfacción de restricciones", Métodos lógicos en informática , 13 (1): 1:1–1:11, arXiv : 1609.05221 , doi :10.23638/LMCS-13(1:1)2017, MR  3607036, S2CID  31135533.
• Schmerl, James H. (2000), "Coloración de gráficos y matemáticas inversas", Mathematical Logic Quarterly , 46 (4): 543–548, doi :10.1002/1521-3870(200010)46:4<543::AID-MALQ543>3.0.CO;2-E, MR  1791549.
• Shelah, Saharon ; Soifer, Alexander (2003), "Axioma de elección y número cromático del plano", Journal of Combinatorial Theory , Serie A, 103 (2): 387–391, doi :10.1016/S0097-3165(03)00102-X, MR  1996076.
• Soifer, Alexander (2008), El libro de colorear matemático: matemáticas del coloreado y la vida colorida de sus creadores , Nueva York: Springer, ISBN 978-0-387-74640-1. Véase especialmente el Capítulo II.5 "Reducción de De Bruin–Erdős a conjuntos finitos y resultados cerca del límite inferior", pp. 39–42, y el Capítulo V.26 "El teorema de De Bruin–Erdős y su historia", pp. 236–241.