Teorema de De Bruijn-Erdős (teoría de grafos) - De Bruijn–Erdős theorem (graph theory)

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

El teorema de De Bruijn-Erdős tiene varias demostraciones diferentes, todas dependiendo de alguna manera del axioma de elección . Sus aplicaciones incluyen extender el teorema de los cuatro colores y el teorema de Dilworth de gráficos finitos y conjuntos parcialmente ordenados a infinitos, y reducir el problema de Hadwiger-Nelson sobre el número cromático del plano a un problema sobre gráficos finitos. Puede generalizarse desde números finitos de colores hasta conjuntos de colores cuya cardinalidad es un cardinal fuertemente compacto .

Definiciones y declaración

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

Un subgráfico de un gráfico es otro gráfico obtenido a partir de un subconjunto de sus vértices y un subconjunto de sus aristas. Si el gráfico más grande está coloreado, se puede usar el mismo color para el subgráfico. Por lo tanto, el número cromático de un subgráfico no puede ser mayor que el número cromático de todo el gráfico. El teorema de De Bruijn-Erdős se refiere a los números cromáticos de gráficos infinitos y muestra que (nuevamente, asumiendo el axioma de elección) pueden calcularse a partir de los números cromáticos de sus subgrafos finitos. Establece que, si los números cromáticos de los subgráficos finitos de un gráfico 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. ${\ 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 infinitos el teorema de que, siempre que un grafo tiene una orientación con un máximo de grado finito , también tiene un color-. Para los gráficos finitos, esto se debe a que dichos gráficos siempre tienen un vértice de grado como máximo , que se puede colorear con uno de los colores después de que todos los vértices restantes se colorean de forma recursiva. Los gráficos infinitos con tal orientación no siempre tienen un vértice de bajo grado (por ejemplo, las celosías tienen un grado mínimo arbitrariamente grande), por lo que este argumento requiere que el gráfico sea finito. Pero el teorema de De Bruijn-Erdős muestra que existe un color-incluso para gráficas infinitas. ${\ Displaystyle k}$${\ Displaystyle (2k + 1)}$${\ displaystyle 2k}$${\ Displaystyle 2k + 1}$${\ Displaystyle k = 1}$${\ Displaystyle (2k + 1)}$

Un siete colores del plano, y el eje de Moser de cuatro cromáticos dibujado como un gráfico de distancia unitaria en el plano, proporcionando límites superior e inferior 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 gráficos para un gráfico infinito que tiene un vértice para cada punto del plano y un borde para cada dos puntos cuya distancia euclidiana es exactamente uno. Los subgráficos de este gráfico se denominan gráficos de unidades de distancia . Un gráfico de unidad de distancia de siete vértices, el eje de Moser , requiere cuatro colores; En 2018, se encontraron gráficos de distancia unitaria mucho más grandes que requieren cinco colores. Todo el gráfico infinito tiene una coloración conocida con siete colores basados ​​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 gráfico de distancia unitaria finita con el mismo número cromático que el plano completo, por lo que si el número cromático es mayor que cinco, este hecho puede demostrarse mediante un cálculo finito.

El teorema de De Bruijn-Erdős también puede usarse para extender el teorema de Dilworth de conjuntos finitos a infinitos parcialmente ordenados . 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 un borde para cada par de elementos incomparables. Usando esta interpretación de colores, junto con una demostración separada del teorema de Dilworth para conjuntos finitos parcialmente ordenados, es posible probar que un conjunto infinito parcialmente ordenado tiene un ancho finito w si y solo si tiene una partición en w cadenas.

De la misma manera, el teorema de De Bruijn-Erdős extiende el teorema de los cuatro colores desde gráficas planas finitas hasta gráficas planas infinitas. Cada gráfico plano finito se puede colorear con cuatro colores, mediante el teorema de los cuatro colores. El teorema de De Bruijn-Erdős muestra que cada gráfico que se puede dibujar sin cruces en el plano, finito o infinito, se puede colorear con cuatro colores. De manera más general, cada gráfico infinito para el que todos los subgráficos finitos son planos puede volver a tener cuatro colores.

Pruebas

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

Gottschalk (1951) proporcionó la siguiente prueba muy breve, basada en el teorema de compacidad de Tychonoff en topología. Suponga que, para el grafo infinito G dado , cada subgrafo finito es k -colorable, y sea X el espacio de todas las asignaciones de los k colores a los vértices de G (independientemente de si forman un color válido). Entonces X puede recibir una topología como un producto espacio k ^{V ( G )} , donde V ( G ) denota el conjunto de vértices del gráfico. Según el teorema de Tychonoff, este espacio topológico es compacto . Para cada subgrafo finito F de G , sea X _F el subconjunto de X que consta de asignaciones de colores que colorean F de forma válida . Entonces el sistema de conjuntos X _F 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 G .

Una prueba diferente utilizando el lema de Zorn fue dada por Lajos Pósa , y también en el Ph.D. de 1951. tesis de Gabriel Andrew Dirac . Si G es un grafo infinito en el que cada subgrafo finito es k -colorable, entonces, según el lema de Zorn, es un subgrafo de un grafo máximo M con la misma propiedad (uno al que no se pueden agregar más aristas sin causar que algún subgrafo finito requiera más de k  colores). La relación binaria de nonadjacency en M es una relación de equivalencia , y sus clases de equivalencia proporcionar un k -Coloreado de G . Sin embargo, esta prueba es más difícil de generalizar que la prueba de compacidad.

El teorema también se puede demostrar utilizando ultrafiltros o análisis no estándar . Nash-Williams (1967) proporciona una prueba de gráficas con un número contable de vértices basada en el lema 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 . Es necesaria alguna forma de esta suposición, ya que existen modelos matemáticos en los que tanto el axioma de elección como el teorema de De Bruijn-Erdős son falsos. Más precisamente, Mycielski (1961) mostró que el teorema es una consecuencia del teorema del ideal primo booleano , una propiedad que está implícita en el axioma de elección pero más débil que el axioma completo de elección, y Läuchli (1971) mostró que el De Bruijn –El teorema de Erd y el teorema del ideal primo de Boole son equivalentes en potencia axiomática. También se puede demostrar que el teorema de De Bruijn-Erdős para gráficas contables es equivalente en potencia axiomática, dentro de una teoría de aritmética de segundo orden , al lema infinito de Kőnig.

Como contraejemplo del teorema en modelos de teoría de conjuntos sin elección, sea G un gráfico infinito en el que los vértices representan todos los números reales posibles. En G , conecte cada dos números reales x e y por un borde cada vez que uno de los valores (| x - y | ± √ 2 ) es un número racional . De manera equivalente, en este gráfico, existen aristas entre todos los números reales x y todos los números reales de la forma x ± ( √ 2 + q ) , donde q es cualquier número racional. Cada camino en este gráfico, a partir de cualquier número real x , alterna entre números que difieren de x por un número racional más un múltiplo par de √ 2 y números que difieren de x por un número racional más un múltiplo impar de √ 2 . Esta alternancia evita que G 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 , G requiere una cantidad infinita de colores, ya que en este caso cada clase de color debe ser un conjunto medible y se puede demostrar que todo conjunto medible de números reales sin aristas en G debe tener medida cero. Por lo tanto, en el modelo de Solovay, el número cromático (infinito) de todo G es mucho mayor que el número cromático de sus subgrafos finitos (como máximo dos).

Generalizaciones

Rado (1949) demuestra el siguiente teorema, que puede verse como una generalización del teorema de De Bruijn-Erdős. Sea V un conjunto infinito, por ejemplo, el conjunto de vértices en un grafo infinito. Para cada elemento v de V , sea c _v un conjunto finito de colores. Además, para cada subconjunto finito S de V , elija algún color particular C _S de S , en el que el color de cada elemento v de S pertenece a c _v . Entonces existe una coloración global χ de todo V con la propiedad de que todo conjunto finito S tiene un superconjunto finito T en el que χ y C _T concuerdan. En particular, si elegimos un color k para cada subgrafo finito de un grafo infinito G , entonces hay un color k de G en el que cada grafo finito tiene un supergrafo mas grande cuyo color concuerda con el color de todo el grafo.

Si un gráfico 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 obligados a ocurrir en este caso. Por ejemplo, los gráficos cromáticos ilimitados también deben contener todos los gráficos bipartitos finitos posibles como un subgráfico. Sin embargo, pueden tener una circunferencia impar arbitrariamente grande y, por lo tanto, pueden evitar cualquier conjunto finito de subgrafos no bipartitos.

El teorema de De Bruijn-Erdős también se aplica directamente a hypergraph problemas colorear, donde se requiere que cada hyperedge tiene vértices de más de un color. En cuanto a los gráficos, un hipergráfico tiene un color k si y solo si cada uno de sus subhipergráficos finitos tiene un color k . Es un caso especial del teorema de la 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 tiene un modelo. 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.

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 gráfico G y número cardinal μ < κ , G tiene un número cromático como máximo μ si y solo si cada uno de sus subgrafos de cardinalidad menor que κ tiene un número cromático como máximo μ . El teorema de De Bruijn-Erdős original 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 del continuo generalizado es cierta, entonces para cada cardinal infinito γ , existe un gráfico G de cardinalidad (2 ^γ ) ⁺ tal que el número cromático de G es mayor que γ , pero tal que cada subgrafo de G cuyo conjunto de vértices tenga una potencia menor que G tiene un número cromático como máximo γ . Lake (1975) caracteriza los gráficos 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.

Notas

Referencias