Hispanopedia Wiki
Articulo de referencia

Teorema de los cuatro colores

Ejemplo de un mapa de cuatro colores Un mapa de cuatro colores de los estados de los Estados Unidos (sin incluir lagos ni océanos). En matemáticas , el teorema de los cuatro col...

Hispanopedia WikiContenido en espanolLectura gratuita
Ejemplo de un mapa de cuatro colores
Un mapa de cuatro colores de los estados de los Estados Unidos (sin incluir lagos ni océanos).

En matemáticas , el teorema de los cuatro colores , o teorema del mapa de cuatro colores , establece que no se requieren más de cuatro colores para colorear las regiones de cualquier mapa de manera que no haya dos regiones adyacentes con el mismo color. Adyacente significa que dos regiones comparten un límite común de longitud distinta de cero (es decir, no simplemente una esquina donde se encuentran tres o más regiones). [ 1 ] Fue el primer teorema importante que se demostró utilizando una computadora . Inicialmente, esta demostración no fue aceptada por todos los matemáticos porque la demostración asistida por computadora era inviable para que un humano la verificara manualmente . [ 2 ] La demostración ha ganado amplia aceptación desde entonces, aunque aún persisten algunas reservas. [ 3 ]

Este teorema es una versión más fuerte del teorema de los cinco colores , que puede demostrarse con un argumento mucho más sencillo. Si bien el teorema de los cinco colores, más débil, ya se había demostrado en el siglo XIX, el teorema de los cuatro colores se resistió hasta 1976, cuando Kenneth Appel y Wolfgang Haken lo demostraron mediante una prueba asistida por computadora . Esto ocurrió tras numerosas demostraciones erróneas y contraejemplos equivocados en las décadas anteriores.

La demostración de Appel-Haken procede analizando un gran número de "configuraciones reducibles", ejemplos de mapas con una propiedad particular. En 1997, Robertson, Sanders, Seymour y Thomas mejoraron este método, logrando reducir el número de dichas configuraciones a 633, lo que aún supone un análisis de casos extremadamente extenso. En 2005, Georges Gonthier verificó el teorema utilizando un software de demostración de teoremas de propósito general .

Formulación

La coloración de mapas también puede expresarse en términos de teoría de grafos , considerándola como la construcción de una coloración de grafos del grafo planar de adyacencias entre regiones. En términos de teoría de grafos, el teorema establece que para un grafo planar sin buclesGRAMO{\displaystyle G}, denotando porχ(GRAMO){\displaystyle \chi (G)}su número cromático ,χ(GRAMO)≤4{\displaystyle \chi (G)\leq 4}.

Para que esto tenga sentido, la afirmación intuitiva del teorema de los cuatro colores —"dada cualquier separación de un plano en regiones contiguas, las regiones se pueden colorear utilizando como máximo cuatro colores de manera que no haya dos regiones adyacentes que tengan el mismo color"— debe interpretarse adecuadamente.

En primer lugar, las regiones son adyacentes si comparten un segmento de límite; dos regiones que comparten solo puntos de límite aislados no se consideran adyacentes. (De lo contrario, un mapa con forma de círculo haría que un número arbitrariamente grande de regiones fueran "adyacentes" entre sí en una esquina común, y requeriría, como resultado, un número arbitrariamente grande de colores). En segundo lugar, no se permiten regiones extrañas, como aquellas con área finita pero perímetro infinitamente largo; los mapas con dichas regiones pueden requerir más de cuatro colores. [ 4 ] (Para mayor seguridad, podemos restringirnos a regiones cuyos límites constan de un número finito de segmentos de línea recta. Se permite que una región tenga enclaves , es decir, que rodee completamente a una o más regiones). Nótese que la noción de "región contigua" (técnicamente: subconjunto abierto conectado del plano) no es la misma que la de "país" en mapas regulares, ya que un país no tiene por qué ser contiguo: puede tener exclaves , como Angola con su provincia de Cabinda , Azerbaiyán con su República Autónoma de Najicheván , Rusia con su óblast de Kaliningrado , Francia con sus territorios de ultramar y Estados Unidos con el estado de Alaska . Si exigimos que todo el territorio de un país reciba el mismo color, entonces cuatro colores no siempre son suficientes. Por ejemplo, considérese el mapa simplificado:

En este mapa, las dos regiones marcadas con la letra A pertenecen al mismo país. Si queremos que esas regiones tengan el mismo color, se requieren cinco colores, ya que las dos regiones A juntas son adyacentes a otras cuatro regiones, y cada una de ellas es adyacente a todas las demás.

Un mapa con cuatro regiones y el grafo planar correspondiente con cuatro vértices.

Una formulación más sencilla del teorema utiliza la teoría de grafos . El conjunto de regiones de un mapa puede representarse de forma más abstracta como un grafo no dirigido que tiene un vértice por cada región y una arista por cada par de regiones que comparten un segmento de frontera. Este grafo es planar : puede dibujarse en el plano sin cruces colocando cada vértice en una ubicación elegida arbitrariamente dentro de la región a la que corresponde, y dibujando las aristas como curvas sin cruces que van desde el vértice de una región, a través de un segmento de frontera compartido, hasta el vértice de una región adyacente. A la inversa, cualquier grafo planar puede formarse a partir de un mapa de esta manera. En la terminología de la teoría de grafos, el teorema de los cuatro colores establece que los vértices de todo grafo planar pueden colorearse con un máximo de cuatro colores de manera que no haya dos vértices adyacentes que reciban el mismo color, o, en resumen: todo grafo planar es cuatro-coloreable . [ 5 ]

Historia

Intentos de prueba tempranos

Carta de De Morgan a William Rowan Hamilton , 23 de octubre de 1852

Hasta donde se sabe, [ 6 ] la conjetura se propuso por primera vez el 23 de octubre de 1852, [ 7 ] cuando Francis Guthrie , mientras intentaba colorear el mapa de los condados de Inglaterra, notó que solo se necesitaban cuatro colores diferentes. En ese momento, el hermano de Guthrie, Frederick , era estudiante de Augustus De Morgan (el antiguo asesor de Francis) en el University College de Londres . Francis consultó con Frederick al respecto, quien luego se lo presentó a De Morgan. (Francis Guthrie se graduó más tarde en 1852 y posteriormente se convirtió en profesor de matemáticas en Sudáfrica). Según De Morgan:

Un alumno mío [Guthrie] me pidió hoy que le diera una razón para un hecho que yo desconocía —y aún desconozco—. Dice que si una figura se divide de alguna manera y los compartimentos se colorean de forma diferente, de modo que las figuras con cualquier porción de línea de contorno común se coloreen de forma diferente —se pueden necesitar cuatro colores, pero no más—, el siguiente es su caso en el que se necesitan cuatro colores. ¿Acaso no se puede inventar la necesidad de cinco o más...? [ 8 ]

"FG", tal vez uno de los dos Guthrie, publicó la pregunta en The Athenaeum en 1854, [ 9 ] y De Morgan volvió a plantear la pregunta en la misma revista en 1860. [ 10 ] Otra referencia publicada tempranamente por Arthur Cayley ( 1879 ) a su vez atribuye la conjetura a De Morgan. 

Hubo varios intentos fallidos iniciales para demostrar el teorema. De Morgan creía que se derivaba de un hecho simple sobre cuatro regiones, aunque no creía que ese hecho pudiera obtenerse a partir de hechos más elementales.

Esto surge de la siguiente manera. Nunca necesitamos cuatro colores en un vecindario a menos que haya cuatro condados, cada uno de los cuales tenga límites comunes con cada uno de los otros tres. Tal cosa no puede suceder con cuatro áreas a menos que una o más de ellas estén rodeadas por las demás; y el color utilizado para el condado rodeado queda así libre para continuar. Ahora bien, este principio, que cuatro áreas no pueden tener límites comunes con las otras tres sin estar rodeadas, no es, creemos firmemente, susceptible de demostración con nada más evidente y elemental; debe considerarse un postulado. [ 10 ]

Una de las pruebas propuestas fue presentada por Alfred Kempe en 1879, la cual fue ampliamente aclamada; [ 11 ] otra fue presentada por Peter Guthrie Tait en 1880. No fue hasta 1890 que la prueba de Kempe fue demostrada incorrectamente por Percy Heawood , y en 1891, la prueba de Tait fue demostrada incorrectamente por Julius Petersen; cada prueba falsa permaneció sin ser cuestionada durante 11 años. [ 12 ]

En 1890, además de exponer el fallo en la demostración de Kempe, Heawood demostró el teorema de los cinco colores y generalizó la conjetura de los cuatro colores a superficies de género arbitrario . [ 13 ]

Tait, en 1880, demostró que el teorema de los cuatro colores es equivalente a la afirmación de que cierto tipo de grafo (llamado snark en la terminología moderna) debe ser no planar . [ 14 ]

En 1943, Hugo Hadwiger formuló la conjetura de Hadwiger , [ 15 ] una generalización de gran alcance del problema de los cuatro colores que aún permanece sin resolver.

Prueba por ordenador

Durante las décadas de 1960 y 1970, el matemático alemán Heinrich Heesch desarrolló métodos para utilizar ordenadores en la búsqueda de demostraciones. En particular, fue el primero en utilizar la descarga para demostrar el teorema, lo que resultó fundamental en la parte de inevitabilidad de la posterior demostración de Appel-Haken. También amplió el concepto de reducibilidad y, junto con Ken Durre, desarrolló una prueba informática para ello. Desafortunadamente, en este momento crucial, no pudo obtener el tiempo de supercomputadora necesario para continuar su trabajo. [ 16 ]

Otros adoptaron sus métodos, incluyendo su enfoque asistido por computadora. Mientras otros equipos de matemáticos competían por completar las demostraciones, Kenneth Appel y Wolfgang Haken, de la Universidad de Illinois , anunciaron el 21 de junio de 1976 [ 17 ] que habían demostrado el teorema. Contaron con la ayuda de John A. Koch en algunos aspectos algorítmicos [ 18 ] .

Si la conjetura de los cuatro colores fuera falsa, habría al menos un mapa con el menor número posible de regiones que requiere cinco colores. La prueba demostró que tal contraejemplo mínimo no puede existir, mediante el uso de dos conceptos técnicos: [ 19 ]

  1. Un conjunto inevitable es un conjunto de configuraciones tales que cada mapa que satisface algunas condiciones necesarias para ser una triangulación mínima no 4-coloreable (como tener un grado mínimo de 5) debe tener al menos una configuración de este conjunto.
  2. Una configuración reducible es una disposición de países que no puede darse en un contraejemplo mínimo. Si un mapa contiene una configuración reducible, se puede reducir a un mapa más pequeño. Este mapa más pequeño tiene la condición de que si se puede colorear con cuatro colores, esto también se aplica al mapa original. Esto implica que si el mapa original no se puede colorear con cuatro colores, el mapa más pequeño tampoco, por lo que el mapa original no es mínimo.

Utilizando reglas y procedimientos matemáticos basados ​​en propiedades de configuraciones reducibles, Appel y Haken hallaron un conjunto inevitable de configuraciones reducibles, demostrando así que no podía existir un contraejemplo mínimo a la conjetura de los cuatro colores. Su demostración redujo la infinidad de posibles mapas a 1834 configuraciones reducibles (posteriormente reducidas a 1482), las cuales tuvieron que ser verificadas una por una mediante ordenador, lo que requirió más de mil horas. Esta parte de la reducibilidad del trabajo fue verificada de forma independiente con diferentes programas y ordenadores. Sin embargo, la parte de la inevitabilidad de la demostración se verificó en más de 400 páginas de microfichas , que tuvieron que ser revisadas a mano con la ayuda de la hija de Haken, Dorothea Blostein . [ 20 ]

El anuncio de Appel y Haken fue ampliamente difundido por los medios de comunicación de todo el mundo, [ 21 ] y el departamento de matemáticas de la Universidad de Illinois utilizó un matasellos que decía "Cuatro colores bastan". [ 22 ] Al mismo tiempo, la naturaleza inusual de la demostración —fue el primer teorema importante que se demostró con amplia asistencia informática— y la complejidad de la parte verificable por humanos suscitaron una considerable controversia. [ 23 ] No todos los matemáticos aceptaron que una demostración basada en computadora pudiera considerarse una prueba genuina. Incluso algunos de los que sí lo hicieron, como Ian Stewart , encontraron la demostración insatisfactoria, ya que se presentó como un hecho consumado y carecía de estructura. "La respuesta parece una especie de coincidencia monstruosa", escribió Stewart. HSM Coxeter consideró "muy improbable que alguien pueda descomponer esa demostración en algo que se consideraría una demostración ordinaria". [ 24 ]

A principios de la década de 1980, se extendieron rumores de un fallo en la prueba de Appel - Haken. Ulrich Schmidt, de la RWTH Aachen, había examinado la prueba de Appel y Haken para su tesis de maestría, publicada en 1981. [ 25 ] Había comprobado aproximadamente el 40% de la parte de inevitabilidad y encontró un error significativo en el procedimiento de descarga ( Appel y Haken 1989 ) . En 1986, el editor de Mathematical Intelligencer pidió a Appel y Haken que escribieran un artículo abordando los rumores de fallos en su prueba. Respondieron que los rumores se debían a una "mala interpretación de los resultados de [Schmidt]" y accedieron con un artículo detallado. [ 25 ] Su obra magna , Every Planar Map is Four-Colorable , un libro que afirmaba una prueba completa y detallada (con un suplemento en microfichas de más de 400 páginas), apareció en 1989; Explicó y corrigió el error descubierto por Schmidt, así como otros errores hallados por otros. [ 20 ]

Simplificación y verificación

Desde la demostración del teorema, un nuevo enfoque ha llevado a una demostración más corta y a un algoritmo más eficiente para 4-colorear mapas. En 1996, Neil Robertson , Daniel P. Sanders , Paul Seymour y Robin Thomas crearon un algoritmo de tiempo cuadrático (que requiere solo O ( n² ) tiempo, donde n es el número de vértices), mejorando un algoritmo de tiempo cuártico basado en la demostración de Appel y Haken. [ 26 ] La nueva demostración, basada en las mismas ideas, es similar a la de Appel y Haken pero más eficiente porque reduce la complejidad del problema y requiere verificar solo 633 configuraciones reducibles. Tanto la parte de inevitabilidad como la de reducibilidad de esta nueva demostración deben ser ejecutadas por una computadora y son impracticables para verificar a mano. [ 27 ] En 2001, los mismos autores anunciaron una demostración alternativa, al demostrar la conjetura snark . [ 28 ] Sin embargo, esta prueba permanece inédita.

En 2005, Benjamin Werner y Georges Gonthier formalizaron una demostración del teorema dentro del asistente de demostración Coq . Esto eliminó la necesidad de confiar en los diversos programas informáticos utilizados para verificar casos particulares; solo es necesario confiar en el núcleo de Coq. [ 29 ]

Resumen de ideas para demostraciones

La siguiente discusión es un resumen basado en la introducción de Every Planar Map is Four Colorable ( Appel & Haken 1989 ) . Si bien presentaba fallas, la supuesta demostración original de Kempe del teorema de los cuatro colores proporcionó algunas de las herramientas básicas que posteriormente se utilizaron para demostrarlo. La explicación aquí presentada se reformula en términos de la formulación moderna de la teoría de grafos mencionada anteriormente.

El argumento de Kempe es el siguiente. Primero, si las regiones planas separadas por el grafo no están trianguladas (es decir, no tienen exactamente tres aristas en sus límites), podemos añadir aristas sin introducir nuevos vértices para que cada región sea triangular, incluyendo la región exterior no delimitada. Si este grafo triangulado se puede colorear con cuatro colores o menos, también lo es el grafo original, ya que la misma coloración es válida si se eliminan aristas. Por lo tanto, basta con demostrar el teorema de los cuatro colores para grafos triangulados para demostrarlo para todos los grafos planares, y sin pérdida de generalidad, asumimos que el grafo está triangulado.

Supongamos que v , e y f son el número de vértices, aristas y regiones (caras). Dado que cada región es triangular y cada arista es compartida por dos regiones, tenemos que 2e = 3f . Esto junto con la fórmula de Euler , v − e + f = 2, se puede usar para demostrar que 6v − 2e = 12. Ahora bien, el grado de un vértice es el número de aristas adyacentes a él. Si v n es el número de vértices de grado n y D es el grado máximo de cualquier vértice,

6v−2mi=6∑i=1Dvi−∑i=1Divi=∑i=1D(6−i)vi=12.{\displaystyle 6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.}

Pero como 12 > 0 y 6 − i ≤ 0 para todo i ≥ 6, esto demuestra que hay al menos un vértice de grado 5 o menos.

Si existe un grafo que requiere 5 colores, entonces existe un grafo mínimo que, al eliminar cualquier vértice, permite colorearlo con cuatro colores. Llamemos a este grafo G. Entonces, G no puede tener un vértice de grado 3 o menor, porque si d ( v ) ≤ 3, podemos eliminar v de G , colorear el grafo más pequeño con cuatro colores, luego volver a agregar v y extender la coloración a este último eligiendo un color diferente al de sus vecinos.

Un grafo que contiene una cadena de Kempe formada por vértices azules y rojos alternados.

Kempe también demostró correctamente que G no puede tener ningún vértice de grado 4. Como antes, eliminamos el vértice v y coloreamos con cuatro colores los vértices restantes. Si los cuatro vecinos de v son de colores diferentes, digamos rojo, verde, azul y amarillo en sentido horario, buscamos un camino alterno de vértices coloreados de rojo y azul que una a los vecinos rojos y azules. Dicho camino se llama cadena de Kempe . Puede haber una cadena de Kempe que una a los vecinos rojos y azules, y puede haber una cadena de Kempe que una a los vecinos verdes y amarillos, pero no ambas, ya que estos dos caminos necesariamente se intersecarían, y el vértice donde se intersecan no puede colorearse. Supongamos que son los vecinos rojos y azules los que no están encadenados. Exploramos todos los vértices conectados al vecino rojo mediante caminos alternos rojo-azul, y luego invertimos los colores rojo y azul en todos estos vértices. El resultado sigue siendo una coloración válida con cuatro colores, y ahora se puede volver a agregar v y colorearlo de rojo.

Esto deja solo el caso en que G tiene un vértice de grado 5; pero el argumento de Kempe era erróneo para este caso. Heawood notó el error de Kempe y también observó que si uno se contentaba con demostrar que solo se necesitan cinco colores, podría seguir el argumento anterior (cambiando solo que el contraejemplo mínimo requiere 6 colores) y usar las cadenas de Kempe en la situación de grado 5 para demostrar el teorema de los cinco colores .

En cualquier caso, para abordar este caso de vértice de grado 5 se requiere una noción más compleja que la de eliminar un vértice. Más bien, la forma del argumento se generaliza para considerar configuraciones , que son subgrafos conexos de G con el grado de cada vértice (en G) especificado. Por ejemplo, el caso descrito en la situación del vértice de grado 4 es la configuración que consiste en un único vértice etiquetado como de grado 4 en G. Como se indicó anteriormente, basta con demostrar que si se elimina la configuración y el grafo restante se colorea con cuatro colores, entonces la coloración se puede modificar de tal manera que cuando se vuelve a agregar la configuración, la coloración con cuatro colores también se puede extender a ella. Una configuración para la cual esto es posible se llama configuración reducible . Si al menos una de un conjunto de configuraciones debe ocurrir en algún lugar de G, ese conjunto se llama inevitable . El argumento anterior comenzó dando un conjunto inevitable de cinco configuraciones (un vértice con grado 1, un vértice con grado 2, ..., un vértice con grado 5) y luego procedió a mostrar que los primeros 4 son reducibles; mostrar un conjunto inevitable de configuraciones donde cada configuración en el conjunto sea reducible demostraría el teorema.

Debido a que G es triangular, se conoce el grado de cada vértice en una configuración, y se conocen todas las aristas internas a la configuración; el número de vértices en G adyacentes a una configuración dada es fijo, y se unen en un ciclo. Estos vértices forman el anillo de la configuración; una configuración con k vértices en su anillo es una configuración de k -anillo, y la configuración junto con su anillo se llama configuración anillada . Como en los casos simples anteriores, se pueden enumerar todas las cuatro coloraciones distintas del anillo; cualquier coloración que se pueda extender sin modificación a una coloración de la configuración se llama inicialmente buena . Por ejemplo, la configuración de un solo vértice anterior con 3 o menos vecinos era inicialmente buena. En general, el grafo circundante debe ser sistemáticamente recoloreado para convertir la coloración del anillo en una buena, como se hizo en el caso anterior donde había 4 vecinos; para una configuración general con un anillo más grande, esto requiere técnicas más complejas. Debido a la gran cantidad de cuatro coloraciones distintas del anillo, este es el paso principal que requiere asistencia informática.

Finalmente, queda por identificar un conjunto inevitable de configuraciones susceptibles de reducción mediante este procedimiento. El método principal utilizado para descubrir dicho conjunto es el método de descarga . La idea intuitiva subyacente a la descarga es considerar el grafo planar como una red eléctrica. Inicialmente, se distribuye una "carga eléctrica" ​​positiva y negativa entre los vértices de manera que el total sea positivo.

Recuerda la fórmula anterior:

∑i=1D(6−i)vi=12.{\displaystyle \sum _{i=1}^{D}(6-i)v_{i}=12.}

Cada vértice con gradoi{\displaystyle i}se le asigna un cargo inicial de6−i{\displaystyle 6-i}Luego, la carga fluye redistribuyéndola sistemáticamente desde un vértice a sus vértices vecinos según un conjunto de reglas, el procedimiento de descarga . Dado que la carga total era inicialmente positiva (12) y la carga se conserva, algunos vértices aún tienen carga positiva. Las reglas restringen las posibilidades de configuraciones de vértices con carga positiva, por lo que enumerar todas esas configuraciones posibles da como resultado un conjunto inevitable.

Mientras algún elemento del conjunto inevitable no sea reducible, el procedimiento de descarga se modifica para eliminarlo (introduciendo otras configuraciones). El procedimiento de descarga final de Appel y Haken era extremadamente complejo y, junto con una descripción del conjunto de configuraciones inevitables resultante, ocupaba un volumen de 400 páginas; sin embargo, las configuraciones que generaba podían verificarse mecánicamente para comprobar su reducibilidad. La verificación del volumen que describía el conjunto de configuraciones inevitables se realizó mediante revisión por pares durante varios años.

Un detalle técnico que no se trata aquí, pero que es necesario para completar la demostración, es la reducibilidad por inmersión .

Falsas refutaciones

El teorema de los cuatro colores ha sido tristemente célebre por haber atraído un gran número de falsas demostraciones y refutaciones a lo largo de su dilatada historia. Inicialmente, The New York Times se negó, por política interna, a informar sobre la demostración de Appel-Haken, por temor a que se demostrara su falsedad, al igual que las anteriores. [ 21 ] Algunas supuestas demostraciones, como las de Kempe y Tait mencionadas anteriormente, estuvieron bajo escrutinio público durante más de una década antes de ser refutadas. Sin embargo, muchas otras, escritas por aficionados, nunca se publicaron.

En el primer mapa, que tiene más de cuatro colores, reemplazar las regiones rojas con cualquiera de los otros cuatro colores no funcionaría, y el ejemplo podría parecer inicialmente que viola el teorema. Sin embargo, los colores se pueden reorganizar, como en el segundo mapa.

Por lo general, los contraejemplos más sencillos, aunque inválidos, intentan crear una región que toque a todas las demás. Esto obliga a colorear las regiones restantes con solo tres colores. Dado que el teorema de los cuatro colores es cierto, esto siempre es posible; sin embargo, como quien dibuja el mapa se centra en la región grande, no se da cuenta de que las regiones restantes sí pueden colorearse con tres colores.

Este truco se puede generalizar: existen muchos mapas donde, si se seleccionan de antemano los colores de algunas regiones, resulta imposible colorear las regiones restantes sin exceder los cuatro colores. Un verificador casual del contraejemplo podría no pensar en cambiar los colores de estas regiones, de modo que el contraejemplo parecerá válido.

Quizás una de las causas de esta idea errónea tan común sea que la restricción de color no es transitiva : una región solo tiene que tener un color diferente al de las regiones con las que está conectada directamente, no al de las regiones que están conectadas entre sí. Si esta fuera la restricción, los grafos planares requerirían una cantidad arbitrariamente grande de colores.

Otras refutaciones falsas violan los supuestos del teorema, como por ejemplo usar una región que consta de múltiples partes desconectadas o impedir que regiones del mismo color se toquen en un punto.

Tricolor

Prueba sin palabras de que un mapa de los estados de EE. UU. necesita al menos cuatro colores.

Si bien todo mapa planar puede colorearse con cuatro colores, decidir si un mapa planar arbitrario puede colorearse con solo tres colores es un problema NP-completo en complejidad . [ 30 ]

Un mapa cúbico puede colorearse con solo tres colores si y solo si cada región interior tiene un número par de regiones vecinas. [ 31 ] En el ejemplo del mapa de los estados de EE. UU., Misuri (MO), estado sin litoral, tiene ocho vecinos (un número par): debe colorearse de forma diferente a todos ellos, pero los vecinos pueden alternar colores, por lo que esta parte del mapa solo necesita tres colores. Sin embargo, Nevada (NV), estado sin litoral, tiene cinco vecinos (un número impar): estos vecinos requieren tres colores, y debe colorearse de forma diferente a ellos, por lo que se necesitan cuatro colores.

Generalizaciones

Grafos infinitos

Al unir las flechas simples y las flechas dobles, se obtiene un toroide con siete regiones que se tocan entre sí; por lo tanto, se necesitan siete colores.
Esta construcción muestra el toroide dividido en un máximo de siete regiones, cada una de las cuales toca a todas las demás.

El teorema de los cuatro colores se aplica no solo a grafos planares finitos, sino también a grafos infinitos que pueden dibujarse sin cruces en el plano, e incluso, de forma más general, a grafos infinitos (posiblemente con un número incontable de vértices) para los que cada subgrafo finito es planar. Para demostrarlo, se puede combinar una demostración del teorema para grafos planares finitos con el teorema de De Bruijn-Erdős, que establece que, si cada subgrafo finito de un grafo infinito es k- coloreable , entonces todo el grafo también lo es ( Nash -Williams 1967 ) . Esto también puede considerarse una consecuencia inmediata del teorema de compacidad de Kurt Gödel para la lógica de primer orden , simplemente expresando la colorabilidad de un grafo infinito con un conjunto de fórmulas lógicas.

Superficies más elevadas

También se puede considerar el problema de coloración en superficies distintas del plano. [ 32 ] El problema en la esfera o el cilindro es equivalente al del plano. Para superficies cerradas (orientables o no orientables) con género positivo , el número máximo p de colores necesarios depende de la característica de Euler χ de la superficie. Excepto para la botella de Klein, la fórmula es la siguiente: pag=⌊7+49−24χ2⌋,{\displaystyle p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,} donde los corchetes exteriores denotan la función piso .

Para una superficie orientable , esto implica que p puede expresarse en términos del género g de la superficie: pag=⌊7+1+48gramo2⌋.{\displaystyle p=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor .}

La fórmula principal, la conjetura de Heawood , fue propuesta por P.J. Heawood en 1890 y, tras las contribuciones de varias personas, demostrada por Gerhard Ringel y J.W.T. Youngs en 1968. La única excepción a la fórmula es la botella de Klein , que tiene una característica de Euler χ = 0 (por lo que la fórmula da p = 7 ) pero requiere solo seis colores, como demostró Philip Franklin en 1934.

Por ejemplo, el toro tiene una característica de Euler χ = 0 (y un género g = 1 ), por lo que p = 7 , así que no se necesitan más de siete colores para colorear cualquier mapa en un toro. Este límite superior de 7 es preciso : ciertos poliedros toroidales , como el poliedro de Szilassi , requieren siete colores.

Una cinta de Möbius requiere seis colores ( Tietze 1910 ), al igual que los grafos 1-planares (grafos dibujados con como máximo un cruce simple por arista) ( Borodin 1984 ) . Si tanto los vértices como las caras de un grafo planar están coloreados, de tal manera que no haya dos vértices, caras o pares vértice-cara adyacentes que tengan el mismo color, entonces nuevamente se necesitan como máximo seis colores ( Borodin 1984 ) .

El plano proyectivo real tiene una característica de Euler χ = 1 y la fórmula da p = 6 , por lo que no se requieren más de seis colores.

Para grafos cuyos vértices se representan como pares de puntos en dos superficies distintas, con aristas dibujadas como curvas que no se cruzan en una de las dos superficies, el número cromático puede ser al menos 9 y como máximo 12 , pero no se conocen límites más precisos; este es el problema Tierra-Luna de Gerhard Ringel . [ 33 ]

Regiones sólidas

Prueba sin palabras de que el número de colores necesarios es ilimitado en tres o más dimensiones.

No existe una extensión obvia del resultado de la coloración a regiones sólidas tridimensionales. Al usar un conjunto de n varillas plegadas, se puede disponer de manera que cada varilla toque a todas las demás. El conjunto requeriría entonces n colores, o n + 1 si se incluye el espacio vacío (que también toca a todas las varillas). El número n puede ser cualquier entero, tan grande como se desee. Frederick Guthrie conocía tales ejemplos en 1880. [ 34 ] Incluso para cuboides paralelos a los ejes (dos cuboides se consideran adyacentes si comparten una superficie límite bidimensional), puede ser necesario un número ilimitado de colores. [ 35 ]

Relación con otras áreas de las matemáticas

Dror Bar-Natan hizo una afirmación sobre las álgebras de Lie y los invariantes de Vassiliev que es equivalente al teorema de los cuatro colores. [ 36 ]

Uso fuera de las matemáticas

San Martín , una isla en el noreste del Caribe , está dividida entre Francia y los Países Bajos.

A pesar de la motivación de colorear mapas políticos de países , el teorema no es de particular interés para los cartógrafos . Según un artículo del historiador de matemáticas Kenneth May , "los mapas que utilizan solo cuatro colores son raros, y los que lo hacen generalmente requieren solo tres. Los libros sobre cartografía e historia de la elaboración de mapas no mencionan la propiedad de los cuatro colores". [ 37 ] El teorema tampoco garantiza el requisito cartográfico habitual de que las regiones no contiguas del mismo país (como el exclave de Alaska y el resto de los Estados Unidos ) se coloreen de forma idéntica. [ 38 ] Dado que el teorema de los cuatro colores no se aplica cuando las regiones en el mapa no son contiguas, tampoco se aplica al mapa mundial. En el mapa mundial, el océano, Bélgica, Alemania, los Países Bajos y Francia limitan entre sí porque los Países Bajos limitan con Francia en la isla de San Martín .

El teorema tampoco se aplica si se exige que todas las masas de agua tengan el mismo color que no se puede usar para un país (por ejemplo, azul). En ese caso, el mapa de Europa no admite cuatro colores. Francia, Alemania y Bélgica deben tener tres colores diferentes, ya que todas limitan entre sí, utilizando así cuatro colores en total. Francia y los Países Bajos pueden tener el mismo color, pero Luxemburgo requiere un quinto. [ 39 ]

Véase también

Notas

  1. ↑ De Gonthier (2008) : "Definiciones: Un mapa planar es un conjunto de subconjuntos disjuntos dos a dos del plano, llamados regiones. Un mapa simple es aquel cuyas regiones son conjuntos abiertos conexos. Dos regiones de un mapa son adyacentes si sus respectivas clausuras tienen un punto común que no es un vértice del mapa. Un punto es un vértice de un mapa si y solo si pertenece a las clausuras de al menos tres regiones. Teorema: Las regiones de cualquier mapa planar simple se pueden colorear con solo cuatro colores, de tal manera que cualesquiera dos regiones adyacentes tengan colores diferentes."
  2. ↑ Swart (1980) .
  3. ↑ Wilson (2014) , 216–222.
  4. ↑ Hudson (2003) .
  5. ↑ Thomas (1998 , p. 849) ; Wilson (2014) ). 
  6. ↑ Existe cierta tradición matemática que afirma que Möbius originó la conjetura de los cuatro colores, pero esta idea parece ser errónea. Véase Biggs, Norman ; Lloyd, E. Keith; Wilson, Robin J. (1986), Graph Theory, 1736–1936 , Oxford University Press, p. 116 , ISBN 0-19-853916-9& Maddison, Isabel (1897), "Nota sobre la historia del problema de la coloración de mapas", Bull. Amer. Math. Soc. , 3 (7): 257, doi : 10.1090/S0002-9904-1897-00421-9
  7. ↑ Donald MacKenzie, Mecanización de la prueba: Computación, riesgo y confianza (MIT Press, 2004) pág. 103
  8. ↑ Wilson (2014) , pág. 12.
  9. ↑ FG (1854) ; McKay (2012)
  10. 1 2 De Morgan (anónimo), Augustus (14 de abril de 1860), "La filosofía del descubrimiento, capítulos históricos y críticos. Por W. Whewell.", The Athenaeum : 501–503
  11. ↑ WW Rouse Ball (1960) El teorema de los cuatro colores , en Mathematical Recreations and Essays, Macmillan, Nueva York, pp. 222–232.
  12. ↑ Thomas (1998) , pág. 848.
  13. ↑ Heawood (1890) .
  14. ↑ Tait (1880) .
  15. ↑ Hadwiger (1943) .
  16. ↑ Wilson (2014) , págs. 139–142.
  17. ^ Gary Chartrand y Linda Lesniak, Gráficos y dígrafos (CRC Press, 2005) p. 221
  18. ↑ Wilson (2014) , págs. 145–146.
  19. ^ Wilson (2014 , págs. 105-107) ; Appel y Haken (1989) ; Tomás (1998 , págs. 852–853)  
  20. 1 2 Appel y Haken (1989) .
  21. 1 2 Wilson (2014) , pág. 153.
  22. ↑ Wilson (2014) , pág. 150.
  23. ↑ Wilson (2014) , pág. 157.
  24. ↑ Wilson (2014) , págs. 161–162.
  25. 1 2 Wilson (2014) , pág. 165.
  26. ↑ Thomas (1995) ; Robertson et al. (1996) .
  27. ↑ Thomas (1998) , págs. 852–853.
  28. ↑ Thomas (1999) ; Pegg et al. (2002) .
  29. ↑ Gonthier (2008) .
  30. ↑ Dailey, DP (1980), "La unicidad de la colorabilidad y la colorabilidad de los grafos planares 4-regulares son NP-completas", Matemáticas Discretas , 30 (3): 289– 293, doi : 10.1016/0012-365X(80)90236-8
  31. ↑ Steinberg, Richard (1993), "El estado del problema de los tres colores", en Gimbel, John; Kennedy, John W.; Quintas, Louis V. (eds.), Quo Vadis, Graph Theory?, Annals of Discrete Mathematics, vol. 55, Ámsterdam: North-Holland, pp. 211–248 , doi : 10.1016/S0167-5060(08)70391-1 , ISBN   978-0-444-89441-0, MR 1217995 
  32. ↑ Ringel (1974) .
  33. ↑ Gethner, Ellen (2018), "A la Luna y más allá", en Gera, Ralucca ; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.), Teoría de grafos: conjeturas favoritas y problemas abiertos, II , Problem Books in Mathematics, Springer International Publishing, pp. 115–133 , doi : 10.1007/978-3-319-97686-0_11 , ISBN  978-3-319-97684-6, MR 3930641 
  34. ↑ Wilson (2014) , pág. 15.
  35. ↑ Reed y Allwright (2008) ; Magnant y Martin (2011)
  36. ↑ Bar-Natan (1997) .
  37. ↑ Wilson (2014) , 2.
  38. ↑ Wilson (2014) , 6.
  39. ↑ Coxeter, HSM (verano de 1971), "Las matemáticas de la coloración de mapas", Leonardo , 4 (3): 273– 277, doi : 10.2307/1572306 , JSTOR 1572306 

Referencias

  • Allaire, Frank (1978), "Otra demostración del teorema de los cuatro colores. I.", en D. McCarthy; HC Williams (eds.), Actas de la 7.ª Conferencia de Manitoba sobre Matemáticas Numéricas y Computación, Congr. Numer. , vol.  20, Winnipeg, Man.: Utilitas Mathematica Publishing, Inc., pp. 3–72 , ISBN  0-919628-20-6, MR 0535003 
  • Appel, Kenneth ; Haken, Wolfgang (1977), "Every Planar Map is Four Colorable. I. Dischargeging", Illinois Journal of Mathematics , 21 (3): 429–490 , doi : 10.1215/ijm/1256049011 , MR 0543792 
  • Appel, Kenneth ; Haken, Wolfgang ; Koch, John (1977), "Every Planar Map is Four Colorable. II. Reducibility", Illinois Journal of Mathematics , 21 (3): 491–567 , doi : 10.1215/ijm/1256049012 , MR 0543793 
  • Appel, Kenneth ; Haken, Wolfgang (octubre de 1977), "Solución del problema del mapa de cuatro colores", Scientific American , vol.  237, n.º  4, págs. 108–121 , Bibcode : 1977SciAm.237d.108A , doi : 10.1038/scientificamerican1077-108 
  • Appel, Kenneth ; Haken, Wolfgang (1989), Every Planar Map is Four-Colorable , Contemporary Mathematics, vol.  98, Con la colaboración de J. Koch, Providence, Rhode Island: American Mathematical Society, doi : 10.1090/conm/098 , ISBN 0-8218-5103-9, MR 1025335 , S2CID 8735627  
  • Bar-Natan, Dror (1997), "Álgebras de Lie y el teorema de los cuatro colores", Combinatorica , 17 (1): 43– 52, arXiv : q-alg/9606016 , doi : 10.1007/BF01196130 , MR 1466574 , S2CID 2103049  
  • Bernhart, Frank R. (1977), "Un resumen del teorema de los cuatro colores", Journal of Graph Theory , vol.  1, n.º  3, págs. 207–225 , doi : 10.1002/jgt.3190010305 , MR 0465921  
  • Borodin, OV (1984), "Solución del problema de Ringel sobre la coloración de caras de vértices de grafos planares y la coloración de grafos 1-planares", Metody Diskretnogo Analiza (41): 12– 26, 108, MR 0832128 
  • Cayley, Arthur (1879), "Sobre la coloración de los mapas", Actas de la Real Sociedad Geográfica , 1 (4), Blackwell Publishing: 259– 261, doi : 10.2307/1799998 , JSTOR 1799998 
  • Fritsch, Rudolf; Fritsch, Gerda (1998), El teorema de los cuatro colores: historia, fundamentos topológicos e idea de demostración , traducido del original alemán de 1994 por Julie Peschke, Nueva York: Springer, doi : 10.1007/978-1-4612-1720-6 , ISBN 978-0-387-98497-1, MR 1633950 
  • FG (10 de junio de 1854), "Coloreando mapas" , The Athenaeum : 726
  • Gethner, E.; Springer, WM (2003), "¿Qué tan falsa es la demostración de Kempe del teorema de los cuatro colores?", Congr. Numer ., 164 : 159–175 , MR 2050581 , Zbl 1050.05049  
  • Gethner, Ellen ; Kalichanda, Bopanna; Mentis, Alexander S. (2009), "¿Qué tan falsa es la demostración de Kempe del Teorema de los Cuatro Colores? Parte II", Involve , 2 (3): 249–265 , doi : 10.2140/involve.2009.2.249
  • Gonthier, Georges (2005), Una demostración verificada por computadora del teorema de los cuatro colores (PDF) , inédito, archivado (PDF) del original el 8 de septiembre de 2017
  • Gonthier, Georges (2008), "Demostración formal: el teorema de los cuatro colores" (PDF) , Notices of the American Mathematical Society , 55 (11): 1382–1393 , MR 2463991 , archivado (PDF) del original el 5 de agosto de 2011. 
  • Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckkomplexe", Vierteljschr. Naturalmente. Ges. Zúrich , 88 : 133-143​
  • Heawood, PJ (1890), "Teorema del color del mapa", Quarterly Journal of Pure and Applied Mathematics, Oxford , vol.  24, pp . 332–338 
  • Hudson, Hud (mayo de 2003), "Cuatro colores no son suficientes", The American Mathematical Monthly , 110 (5): 417– 423, doi : 10.2307/3647828 , JSTOR 3647828 
  • Kempe, AB (1879), "Sobre el problema geográfico de los cuatro colores", American Journal of Mathematics , 2 (3): 193– 220, doi : 10.2307/2369235 , JSTOR 2369235 
  • Magnant, C.; Martin, DM (2011), "Coloring rectangular blocks in 3-space", Discussiones Mathematicae Graph Theory , 31 (1): 161– 170, doi : 10.7151/dmgt.1535
  • McKay, Brendan D. (2012), Una nota sobre la historia de la conjetura de los cuatro colores , arXiv : 1201.2852 , Bibcode : 2012arXiv1201.2852M
  • Nash-Williams, C. St. JA (1967), "Grafos infinitos: una revisión", Journal of Combinatorial Theory , 3 (3): 286– 301, doi : 10.1016/s0021-9800(67)80077-2 , MR 0214501 
  • O'Connor; Robertson (1996), El teorema de los cuatro colores , archivo MacTutor , archivado del original el 16 de enero de 2013 , recuperado el 5 de agosto de 2001.
  • Pegg, Ed Jr .; Melendez, J.; Berenguer, R.; Sendra, JR; Hernandez, A.; Del Pino, J. (2002), "Reseña del libro: El libro colosal de las matemáticas" (PDF) , Notices of the American Mathematical Society , 49 (9): 1084–1086 , archivado (PDF) del original el 9 de abril de 2003.
  • Reed, Bruce ; Allwright, David (2008), "Pintando la oficina" , Mathematics-in-Industry Case Studies , 1 : 1–8 , archivado del original el 3 de febrero de 2013 , recuperado el 11 de julio de 2011.
  • Ringel, G. (1974), Teorema del color del mapa , Nueva York-Berlín: Springer-Verlag
  • Ringel, G.; Youngs , JWT (1968), "Solución del problema de coloración de mapas de Heawood", Proc. Natl. Acad. Sci. USA , vol.  60, n.º  2, págs. 438–445 , Bibcode : 1968PNAS...60..438R , doi : 10.1073/pnas.60.2.438 , PMC 225066 , PMID 16591648   
  • Robertson, Neil ; Sanders, Daniel P.; Seymour , Paul ; Thomas, Robin (1996), "Coloración eficiente de cuatro colores en grafos planares", Actas del 28.º Simposio ACM sobre Teoría de la Computación (STOC 1996) , págs. 571–575 , doi : 10.1145/237814.238005 , ISBN  0-89791-785-5, MR 1427555 , S2CID 14962541  
  • Robertson, Neil ; Sanders, Daniel P .; Seymour, Paul ; Thomas, Robin (1997), "El teorema de los cuatro colores", J. Combin. Theory Ser. B , vol.  70, n.º  1, págs. 2–44 , doi : 10.1006/jctb.1997.1750 , MR 1441258  
  • Saaty, Thomas ; Kainen, Paul (1986), El problema de los cuatro colores: asaltos y conquista , Nueva York: Dover Publications, ISBN 0-486-65092-8
  • Swart, Edward Reinier (1980), "Las implicaciones filosóficas del problema de los cuatro colores" , American Mathematical Monthly , vol.  87, n.º  9, Mathematical Association of America, pp. 697–702 , doi : 10.2307/2321855 , JSTOR 2321855 , MR 0602826   
  • Thomas, Robin (1998), "Una actualización sobre el teorema de los cuatro colores" (PDF) , Notices of the American Mathematical Society , vol.  45, n.º  7, págs. 848–859 , MR 1633714 , archivado (PDF) del original el 29 de septiembre de 2000.  
  • Thomas, Robin (1995), El teorema de los cuatro colores
  • Tietze, Heinrich (1910), "Einige Bemerkungen über das Problem des Kartenfärbens auf einseitigen Flächen" [ Algunas observaciones sobre el problema de la coloración de mapas en superficies unilaterales ] , Jahresbericht der Deutschen Mathematiker-Vereinigung , 19 : 155– 159
  • Thomas, Robin (1999), "Teoremas menores excluidos recientes para grafos", en Lamb, John D.; Preece, DA (eds.), Surveys in combinatorics, 1999 , London Mathematical Society Lecture Note Series, vol.  267, Cambridge: Cambridge University Press, pp. 201–222 , doi : 10.1017/CBO9780511721335 , ISBN  0-521-65376-2, MR 1725004 
  • Tait, PG (1880), "Observaciones sobre la coloración de los mapas", Proc. R. Soc. Edinburgh , 10 : 729, doi : 10.1017/S0370164600044643
  • Wilson, Robin (2014) [2002], Cuatro colores bastan , Biblioteca de Ciencias de Princeton, Princeton, Nueva Jersey: Princeton University Press, ISBN 978-0-691-15822-8, MR 3235839 
  • Wilson, Robin; Watkins, John J.; Parks, David J. (17 de enero de 2023), Teoría de grafos en Estados Unidos , Princeton Oxford: Princeton University Press, ISBN 978-0-691-19402-8
  • "Problema de los cuatro colores" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
  • Wilson, Robin (marzo de 2026). "El teorema de los cuatro colores: 1852–1976" (PDF) . Notices of the American Mathematical Society . 73 (3): 216–228 . doi : 10.1090/noti3305 .
  • Lista de generalizaciones del teorema de los cuatro colores en MathOverflow