El problema Tierra-Luna

El problema Tierra-Luna es un problema sin resolver sobre la coloración de grafos en matemáticas. Es una extensión del problema de coloración de mapas planos (resuelto por el teorema de los cuatro colores ) y fue planteado por Gerhard Ringel en 1959. ^{[ 1 ]} Una forma intuitiva del problema pregunta cuántos colores se necesitan para colorear mapas políticos de la Tierra y la Luna, en un futuro hipotético donde cada país de la Tierra tiene una colonia lunar que debe tener el mismo color. En términos matemáticos, busca el número cromático de grafos biplanares . Se sabe que este número es al menos 9 y como máximo 12.

El problema Tierra-Luna se ha extendido a problemas análogos de colorear mapas en cualquier número de planetas. En esta extensión, los límites inferior y superior del número de colores son más cercanos, con una diferencia de dos colores entre sí. Una aplicación práctica del problema Tierra-Luna consiste en probar placas de circuitos impresos .

En el problema de coloración de mapas, se deben colorear un número finito de regiones simplemente conexas en el plano euclidiano o en un espacio topológicamente equivalente, como los países en la superficie de la Tierra, de manera que, cuando dos regiones comparten un límite de longitud distinta de cero, tengan colores diferentes. Este problema se puede transformar en un problema de coloración de grafos creando un vértice para cada región y una arista para cada par de regiones vecinas, lo que produce un grafo planar cuyos vértices deben colorearse. De acuerdo con el requisito de que las regiones adyacentes tengan colores diferentes, los vértices adyacentes (los dos extremos de cualquier arista) también deben tener colores diferentes. Según el teorema de los cuatro colores , el grafo planar resultante (o cualquier grafo planar) se puede colorear utilizando como máximo cuatro colores diferentes, independientemente del número de regiones. ^{[ 2 ]}

En 1959, Gerhard Ringel publicó un libro sobre coloraciones de superficies, revisando los resultados de la época sobre el problema de los cuatro colores y la conjetura de Heawood sobre la coloración de mapas en superficies no planas como el toro y la botella de Klein . ^{[ 1 ]} Ambos habían sido conjeturados durante mucho tiempo, pero no se habían resuelto en ese momento. El propio Ringel demostró más tarde la conjetura de Heawood en un artículo de 1968 con JWT Youngs ; ^{[ 2 ] [ 3 ]} el teorema de los cuatro colores eludió la demostración hasta 1976. ^{[ 2 ] [ 4 ]} Otro tema del libro de Ringel fue un resultado de Percy John Heawood de 1890, sobre el "problema del imperio": colorear mapas en los que cada imperio tiene algún número${\displaystyle m}$de distintas regiones de la Tierra (un país de origen y${\displaystyle m-1}$colonias). Como Heawood demostró para${\displaystyle m=2}$y Ringel demostró más tarde con Jackson en 1984 para${\displaystyle m>2}$,${\displaystyle 6m}$Los colores son necesarios y suficientes. ^{[ 2 ] [ 5 ] [ 6 ] [ 7 ]} Quizás inspirado por este problema y el amanecer de la era espacial , Ringel incluyó el problema Tierra-Luna en su libro como una variante del problema del imperio en el que las colonias están en la Luna en lugar de en la Tierra. ^{[ 1 ] [ 2 ]} En una formulación de Martin Gardner , las colonias están en Marte. ^{[ 6 ]}

En el problema Tierra-Luna de Ringel, cada país de la Tierra tiene una colonia correspondiente en la superficie de la Luna, a la que se le debe asignar el mismo color. Estas colonias pueden tener fronteras completamente diferentes a las de la Tierra. Los países deben colorearse utilizando el mismo color para cada país y su colonia, de modo que cuando dos países comparten una frontera, ya sea en la Tierra o en la Luna, se les asignen colores diferentes. El problema de Ringel plantea: ¿cuántos colores se necesitan para garantizar que todos los países puedan colorearse, independientemente de cómo estén dispuestas sus fronteras? ^{[ 2 ]} Ringel demostró que el número de colores necesarios era de al menos 8 y como máximo 12, conjeturando que 8 era la respuesta correcta. ^{[ 6 ]}

Nuevamente, se puede formular la misma pregunta de manera equivalente a una en teoría de grafos, con un vértice para cada par de país y su colonia, y una arista para cada adyacencia entre países o colonias. Como en el caso planar, después de esta transformación, son los vértices los que deben colorearse, con diferentes colores para los extremos de cada arista. Los grafos que resultan en esta versión del problema son grafos biplanares , o equivalentemente, grafos de grosor dos: sus aristas se pueden particionar en dos subconjuntos (las aristas que provienen de adyacencias de la Tierra y las que provienen de adyacencias de la Luna) de tal manera que los dos subgrafos correspondientes sean ambos planares. En términos matemáticos, el problema de Ringel pide el número cromático máximo de grafos biplanares. ^{[ 2 ]}

Un gráfico biplanar en${\displaystyle n}$vértices tiene como máximo${\displaystyle 6n-12}$aristas (el doble del número que puede tener un grafo planar), de donde se deduce de la fórmula de la suma de grados que tiene al menos un vértice con como máximo 11 vecinos. Al eliminar este vértice, colorear el grafo restante recursivamente y luego usar el color no usado de menor número para el vértice eliminado, se obtiene una coloración con como máximo 12 colores; esta es la coloración voraz para un ordenamiento degenerado del grafo. Por lo tanto, los grafos biplanares requieren como máximo 12 colores. ^{[ 2 ]}

Un ejemplo de un grafo biplanar que requiere 9 colores se puede construir como la unión de un grafo completo de 6 vértices y un grafo cíclico de 5 vértices . Esto significa que estos dos subgrafos están conectados por todas las aristas posibles de un subgrafo al otro. El grafo resultante tiene 11 vértices y requiere 6 colores para el subgrafo completo y 3 colores para el subgrafo cíclico, lo que da un total de 9 colores. ^{[ 2 ]} Esta construcción, realizada por Thom Sulanke en 1974, refutó la conjetura de Ringel de que 8 colores siempre serían suficientes. ^{[ 6 ]} Posteriormente, se ha construido una familia infinita de grafos biplanares 9-críticos (grafos mínimos que requieren nueve colores). ^{[ 8 ] [ 9 ]}

A pesar de la falta de avances en el problema, en 2018 Ellen Gethner conjeturó que el número correcto de colores para este problema es 11. Sugiere varios candidatos para grafos biplanares de 10 colores, incluido el grafo${\displaystyle C_{7}\boxtimes K_{4}}$obtenido como el producto fuerte de un grafo cíclico con una camarilla, y el grafo obtenido al eliminar cualquier vértice de${\displaystyle C_{5}\boxtimes K_{4}}$Se puede demostrar que estos grafos requieren 10 colores, ya que no tienen un conjunto independiente lo suficientemente grande como para ser la clase de color más grande en una coloración con menos colores. Además, cumplen con los límites del número de aristas que puede tener un grafo biplanar. Sin embargo, una representación de ellos como grafos biplanares (o mapas Tierra-Luna) sigue siendo difícil de obtener. ^{[ 10 ]} En 2023, se confirmó que este último grafo no es biplanar. ^{[ 11 ]}

Una aplicación de la coloración de grafos biplanares consiste en probar placas de circuitos impresos para detectar cortocircuitos. Los conductores eléctricos dentro de estas placas incluyen cruces, pero (para placas de circuitos impresos de doble cara) se puede asumir que sus adyacencias forman un grafo biplanar. Después de colorear este grafo, se pueden detectar cortocircuitos entre conductores adyacentes agregando circuitos adicionales para conectar todos los conductores del mismo color entre sí y probando conexiones entre pares de colores diferentes. Con un poco de cuidado, esta idea puede usarse para reducir el número de pruebas necesarias por circuito a solo cuatro. ^{[ 2 ] [ 12 ]}

También se han considerado varias generalizaciones del problema, incluidas versiones del problema con más de dos planetas o con países que pueden tener más de una región por planeta. ^{[ 13 ] [ 14 ]} Los mapas con un planeta y múltiples regiones por país dan el problema del imperio de Heawood. ^{[ 2 ] [ 7 ]} Los mapas con más de dos planetas pero solo una región por planeta corresponden a grafos cuyo grosor es como máximo igual al número de planetas. Para estos grafos, se conocen resultados más precisos (aunque todavía incompletos). Para los grafos de grosor${\displaystyle t\geq 3}$y el correspondiente${\displaystyle t}$-mapas planetarios, el número cromático es como máximo${\displaystyle 6t}$mediante el mismo argumento de degeneración utilizado en el problema Tierra-Luna. Además, para${\displaystyle t\geq 3}$, un gráfico completo con${\displaystyle 6t-2}$vértices tiene espesor${\displaystyle t}$, mostrando algunos de estos gráficos se requiere${\displaystyle 6t-2}$colores. Por lo tanto, en este caso, los límites superior e inferior están dentro de dos colores de diferencia entre sí. ^{[ 15 ]}

• Weisstein, Eric W. , "Problema Tierra-Luna" , MathWorld
• "Problema Tierra-Luna" , Jardín de Problemas Abiertos