En matemáticas , el teorema de los cuatro colores , o el teorema del mapa de cuatro colores , establece que, dada cualquier separación de un plano en regiones contiguas , para producir una figura llamada mapa , no se requieren más de cuatro colores para colorear las regiones del mapa de manera que que no hay dos regiones adyacentes que tengan el mismo color. Adyacente significa que dos regiones comparten un segmento de curva de límite común, 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 prueba no fue aceptada por todos los matemáticos porque la prueba asistida por computadoraera imposible que un humano lo comprobara a mano . [2] Desde entonces, la prueba ha ganado una amplia aceptación, aunque quedan algunos escépticos. [3]
El teorema de los cuatro colores fue probado en 1976 por Kenneth Appel y Wolfgang Haken después de muchas pruebas falsas y contraejemplos (a diferencia del teorema de los cinco colores , probado en el siglo XIX, que establece que cinco colores son suficientes para colorear un mapa). Para disipar cualquier duda restante sobre la prueba de Appel-Haken, Robertson, Sanders, Seymour y Thomas publicaron en 1997 una prueba más simple que usaba las mismas ideas y aún confiaba en computadoras. Además, en 2005, el teorema fue probado por Georges Gonthier con un software de demostración de teoremas de propósito general .
Formulación precisa del teorema
En términos de teoría de grafos, el teorema establece que para grafos planos sin bucles , el número cromático de su gráfico dual es.
El enunciado intuitivo 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 para que no haya dos regiones adyacentes con el mismo color" - debe interpretarse adecuadamente para que sea correcta .
Primero, 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. En segundo lugar, las regiones extrañas, como las que tienen un área finita pero un perímetro infinitamente largo, no están permitidas; los mapas con tales regiones pueden requerir más de cuatro colores. [4] (Para estar seguros, podemos restringir a las regiones cuyos límites consisten en un número finito de segmentos de línea recta. Se permite que una región rodee por completo una o más regiones). Tenga en cuenta que la noción de "región contigua" (técnicamente: subconjunto abierto conectado del avión) no es el mismo que el de un "país" en los mapas regulares, ya que los países no necesitan ser contiguos (por ejemplo, la provincia de Cabinda como parte de Angola , Nakhchivan como parte de Azerbaiyán , Kaliningrado como parte de Rusia y Alaska como parte de los Estados Unidos no son contiguas). Si exigimos que todo el territorio de un país reciba el mismo color, entonces cuatro colores no siempre son suficientes. Por ejemplo, considere un mapa simplificado:
En este mapa, las dos regiones etiquetadas como A pertenecen al mismo país. Si quisiéramos que esas regiones recibieran el mismo color, entonces se necesitarían cinco colores, ya que las dos regiones A juntas son adyacentes a otras cuatro regiones, cada una de las cuales es adyacente a todas las demás. Forzar dos regiones separadas para que tengan el mismo color se puede modelar agregando un 'mango' que las une fuera del plano.
Tal construcción hace que el problema sea equivalente a colorear un mapa en un toro (una superficie del género 1), que requiere hasta 7 colores para un mapa arbitrario. Una construcción similar también se aplica si se usa un solo color para múltiples áreas disjuntas, como para cuerpos de agua en mapas reales, o si hay más países con territorios disjuntos. En tales casos, es posible que se requieran más colores con un género en crecimiento de una superficie resultante. (Consulte la sección Generalizaciones a continuación).
Un enunciado más simple del teorema utiliza la teoría de grafos . El conjunto de regiones de un mapa se puede representar de manera más abstracta como un gráfico no dirigido que tiene un vértice para cada región y un borde para cada par de regiones que comparten un segmento de límite. Este gráfico es plano : se puede dibujar 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 parten del vértice de una región, a través de una región compartida. segmento de límite, al vértice de una región adyacente. Por el contrario, cualquier gráfico plano se puede formar 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 cada grafo plano se pueden colorear con un máximo de cuatro colores para que dos vértices adyacentes no reciban el mismo color, o para abreviar:
- Cada gráfico plano tiene cuatro colores . [5]
Historia
Intentos de prueba temprana
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 alumno de Augustus De Morgan (el ex consejero de Francis) en el University College London . Francis preguntó a Frederick al respecto, quien luego se lo llevó a De Morgan (Francis Guthrie se graduó más tarde en 1852 y luego 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 de un hecho que yo no sabía que era un hecho, y todavía no lo sé. Dice que si una figura está dividida y los compartimentos de diferentes colores, que las figuras con cualquier parte de la línea de límite común tienen colores diferentes (se pueden querer cuatro colores pero no más), el siguiente es su caso en el que se quieren cuatro colores . No se puede inventar la consulta de la necesidad de cinco o más ... "( Wilson 2014 , pág.18)
"FG", quizás uno de los dos Guthries, publicó la pregunta en The Athenaeum en 1854, [8] y De Morgan planteó la pregunta nuevamente en la misma revista en 1860. [9] Otra referencia publicada anteriormente por Arthur Cayley ( 1879 ) a su vez, atribuye la conjetura a De Morgan.
Hubo varios intentos fallidos tempranos de probar el teorema. De Morgan creía que se derivaba de un simple hecho sobre cuatro regiones, aunque no creía que ese hecho pudiera derivarse 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 tiene líneas fronterizas en común 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é encerrada por el resto; y el color utilizado para el condado cerrado queda así libre para continuar. Ahora bien, creemos plenamente que este principio de que cuatro áreas no pueden tener un límite común cada una con las otras tres sin un cerramiento, no es capaz de demostrarse sobre nada más evidente y más elemental; debe ser un postulado. [9]
Alfred Kempe dio una supuesta prueba en 1879, que fue ampliamente aclamada; [10] otro fue dado por Peter Guthrie Tait en 1880. No fue hasta 1890 que la prueba de Kempe se demostró incorrecta por Percy Heawood , y en 1891, la prueba de Tait se demostró incorrecta por Julius Petersen falsa prueba -cada se paró sin respuesta desde hace 11 años. [11]
En 1890, además de exponer la falla 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éneros arbitrarios. [12]
Tait, en 1880, demostró que el teorema de los cuatro colores es equivalente a la afirmación de que cierto tipo de gráfico (llamado snark en la terminología moderna) debe ser no plano . [13]
En 1943, Hugo Hadwiger formuló la conjetura de Hadwiger , [14] una generalización de gran alcance del problema de los cuatro colores que aún permanece sin resolver.
Prueba por computadora
Durante las décadas de 1960 y 1970, el matemático alemán Heinrich Heesch desarrolló métodos para usar computadoras para buscar una prueba. En particular, fue el primero en utilizar la descarga para demostrar el teorema, que resultó ser importante en la parte inevitable de la siguiente prueba de Appel-Haken. También amplió el concepto de reducibilidad y, junto con Ken Durre, desarrolló una prueba de computadora para ello. Desafortunadamente, en esta coyuntura crítica, no pudo conseguir el tiempo de supercomputadora necesario para continuar con su trabajo. [15]
Otros adoptaron sus métodos, incluido su enfoque asistido por computadora. Mientras otros equipos de matemáticos corrían para completar las pruebas, Kenneth Appel y Wolfgang Haken de la Universidad de Illinois anunciaron, el 21 de junio de 1976, [16] que habían probado el teorema. Fueron asistidos en algunos trabajos algorítmicos por John A. Koch . [15]
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 mostró que tal contraejemplo mínimo no puede existir, mediante el uso de dos conceptos técnicos: [17]
- Un conjunto inevitable es un conjunto de configuraciones de modo que cada mapa que satisfaga 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.
- Una configuración reducible es un arreglo de países que no puede ocurrir en un contraejemplo mínimo. Si un mapa contiene una configuración reducible, el mapa 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 puede hacerlo, 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 encontraron un conjunto inevitable de configuraciones reducibles, demostrando así que no podía existir un contraejemplo mínimo de la conjetura de los cuatro colores. Su prueba redujo la infinitud de mapas posibles a 1.834 configuraciones reducibles (luego reducidas a 1.482) que tuvieron que ser revisadas una a una por computadora y tomaron más de mil horas. Esta parte de reducibilidad del trabajo se verificó dos veces de forma independiente con diferentes programas y computadoras. Sin embargo, la parte inevitable de la prueba se verificó en más de 400 páginas de microfichas , que tuvieron que verificarse a mano con la ayuda de la hija de Haken, Dorothea Blostein ( Appel & Haken 1989 ).
El anuncio de Appel y Haken fue ampliamente difundido por los medios de comunicación de todo el mundo, y el departamento de matemáticas de la Universidad de Illinois utilizó un matasellos que decía "Cuatro colores son suficientes". Al mismo tiempo, la naturaleza inusual de la demostración (fue el primer teorema importante que se demostró con una amplia asistencia informática) y la complejidad de la parte verificable por humanos suscitaron una controversia considerable ( Wilson 2014 ).
A principios de la década de 1980, se difundieron rumores de una falla en la prueba de Appel-Haken. Ulrich Schmidt en RWTH Aachen había examinado la prueba de Appel y Haken para su tesis de maestría que se publicó en 1981 ( Wilson 2014 , 225). Había verificado alrededor del 40% de la parte inevitable y encontró un error significativo en el procedimiento de descarga ( Appel & Haken 1989 ). En 1986, el editor de Mathematical Intelligencer pidió a Appel y Haken que escribieran un artículo sobre los rumores de fallas en su prueba. Respondieron que los rumores se debían a una "mala interpretación de los resultados [de Schmidt]" y se vieron obligados con un artículo detallado ( Wilson 2014 , 225-226). Su obra maestra , Every Planar Map is Four-Colorable , un libro que reclama una prueba completa y detallada (con un suplemento de microfichas de más de 400 páginas), apareció en 1989; explicó y corrigió el error descubierto por Schmidt, así como varios errores adicionales encontrados por otros ( Appel & Haken 1989 ).
Simplificación y verificación
Desde la demostración del teorema, se han encontrado algoritmos eficientes para mapas de 4 colores que requieren solo O ( n 2 ) tiempo, donde n es el número de vértices. En 1996, Neil Robertson , Daniel P. Sanders , Paul Seymour , y Robin Thomas crearon un tiempo cuadrática algoritmo, mejorando en un cuártica algoritmo basado en la prueba -tiempo Appel y Haken de. [18] Esta nueva prueba 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 las partes de inevitabilidad como de reducibilidad de esta nueva prueba deben ser ejecutadas por computadora y no es práctico verificarlas a mano. [19] En 2001, los mismos autores anunciaron una prueba alternativa, demostrando la conjetura de snark . [20] Sin embargo, esta prueba permanece inédita.
En 2005, Benjamin Werner y Georges Gonthier formalizaron una prueba del teorema dentro del asistente de prueba Coq . Esto eliminó la necesidad de confiar en los diversos programas informáticos utilizados para verificar casos particulares; solo es necesario confiar en el kernel de Coq. [21]
Resumen de ideas de prueba
La siguiente discusión es un resumen basado en la introducción a Every Planar Map is Four Colorable ( Appel & Haken 1989 ). Aunque defectuosa, la supuesta prueba original de Kempe del teorema de los cuatro colores proporcionó algunas de las herramientas básicas que se usaron más tarde para demostrarlo. La explicación aquí se reformula en términos de la formulación de la teoría de grafos moderna anterior.
El argumento de Kempe es el siguiente. Primero, si las regiones planas separadas por el gráfico no están trianguladas , es decir, no tienen exactamente tres aristas en sus límites, podemos agregar aristas sin introducir nuevos vértices para hacer que cada región sea triangular, incluida la región exterior ilimitada. Si este gráfico triangulado se puede colorear con cuatro colores o menos, también lo es el gráfico original, ya que el mismo color es válido si se eliminan los bordes. Por tanto, basta con demostrar el teorema de los cuatro colores para gráficas trianguladas para demostrarlo para todas las gráficas planas, y sin pérdida de generalidad asumimos que la gráfica está triangulada.
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 borde es compartido por dos regiones, tenemos que 2 e = 3 f . Esto, junto con la fórmula de Euler , v - e + f = 2, se puede usar para mostrar que 6 v - 2 e = 12. Ahora, el grado de un vértice es el número de aristas contiguas. Si v n es el número de vértices de grado n , y D es el grado máximo de cualquier vértice,
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 hay un gráfico que requiere 5 colores, entonces hay un gráfico mínimo , donde la eliminación de cualquier vértice lo convierte en cuatro colores. Llame a este gráfico G . Entonces G no puede tener un vértice de grado 3 o menos, porque si d ( v ) ≤ 3, podemos quitar v de G , cuatricromar la gráfica más pequeña, luego volver a sumar v y extenderle los cuatro colores eligiendo un color diferente al de sus vecinos.
Kempe también demostró correctamente que G no puede tener vértice de grado 4. Como antes, eliminamos el vértice v y cuadricolor los vértices restantes. Si los cuatro vecinos de v son de colores diferentes, digamos rojo, verde, azul y amarillo en el sentido de las agujas del reloj, buscamos una ruta alterna de vértices de color rojo y azul que se unen a los vecinos rojo y azul. Este camino se llama cadena de Kempe . Puede haber una cadena de Kempe que une a los vecinos rojo y azul, y puede haber una cadena de Kempe que une a los vecinos verde y amarillo, pero no ambos, ya que estos dos caminos necesariamente se cruzarían y el vértice donde se cruzan no se puede colorear. Suponga que son los vecinos rojo y azul los que no están encadenados. Explore todos los vértices unidos al vecino rojo por caminos alternos rojo-azul, y luego invierta los colores rojo y azul en todos estos vértices. El resultado sigue siendo un cuatro colores válido, y ahora se puede volver a agregar v y colorear en rojo.
Esto deja solo el caso donde G tiene un vértice de grado 5; pero el argumento de Kempe fue defectuoso para este caso. Heawood notó el error de Kempe y también observó que si uno estaba satisfecho con probar que solo se necesitan cinco colores, uno podría ejecutar el argumento anterior (cambiando solo que el contraejemplo mínimo requiere 6 colores) y usar cadenas de Kempe en la situación de grado 5 para probar el teorema de los cinco colores .
En cualquier caso, lidiar con este caso de vértice de grado 5 requiere una noción más complicada que eliminar un vértice. Más bien, la forma del argumento se generaliza para considerar configuraciones , que son subgrafos conectados de G con el grado de cada vértice (en G) especificado. Por ejemplo, el caso descrito en el grado 4 situación vértice es la configuración que consiste en un solo vértice etiquetado como que tiene un grado 4 en G . Como se indicó anteriormente, basta con demostrar que si se elimina la configuración y el gráfico restante en cuatro colores, entonces el color se puede modificar de tal manera que cuando se vuelve a agregar la configuración, el cuatro colores se puede extender a él como bien. Una configuración para la que esto es posible se denomina 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 solo vértice con grado 1, un solo vértice con grado 2, ..., un solo vértice con grado 5) y luego procedió a mostrar que los primeros 4 son reducibles; exhibir un conjunto inevitable de configuraciones donde cada configuración en el conjunto es reducible probaría el teorema.
Como G es triangular, se conoce el grado de cada vértice en una configuración y se conocen todos los bordes internos de 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- ring, y la configuración junto con su anillo se llama configuración anillada . Como en los casos simples anteriores, se pueden enumerar todos los cuatro colores distintos del anillo; cualquier coloración que pueda extenderse sin modificación a una coloración de la configuración se llama inicialmente bueno . Por ejemplo, la configuración de un solo vértice anterior con 3 o menos vecinos fue inicialmente buena. En general, el gráfico circundante se debe volver a colorear sistemáticamente para que el color del anillo sea bueno, 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 colores distintos del anillo, este es el paso principal que requiere asistencia informática.
Finalmente, queda por identificar un conjunto inevitable de configuraciones susceptibles de ser reducidas por este procedimiento. El método principal utilizado para descubrir tal conjunto es el método de descarga . La idea intuitiva subyacente a la descarga es considerar el gráfico plano como una red eléctrica. La "carga eléctrica" inicialmente positiva y negativa se distribuye entre los vértices de modo que el total sea positivo.
Recuerde la fórmula anterior:
A cada vértice se le asigna una carga inicial de 6 grados ( v ). Entonces uno "hace fluir" la carga redistribuyendo sistemáticamente la carga desde un vértice a sus vértices vecinos de acuerdo con un conjunto de reglas, el procedimiento de descarga . Dado que la carga se conserva, algunos vértices todavía tienen carga positiva. Las reglas restringen las posibilidades de configuraciones de vértices cargados positivamente, por lo que enumerar todas esas configuraciones posibles da un conjunto inevitable.
Mientras algún miembro del conjunto inevitable no sea reducible, se modifica el procedimiento de descarga para eliminarlo (mientras se introducen otras configuraciones). El procedimiento de descarga final de Appel y Haken fue extremadamente complejo y, junto con una descripción del inevitable conjunto de configuraciones resultante, llenó un volumen de 400 páginas, pero las configuraciones que generó se pudieron verificar mecánicamente para que fueran reducibles. La verificación del volumen que describe el conjunto de configuración inevitable en sí se realizó mediante una revisión por pares durante un período de varios años.
Un detalle técnico que no se discute aquí pero que se requiere para completar la prueba es la reducibilidad por inmersión .
Falsas refutaciones
El teorema de los cuatro colores ha sido conocido por atraer un gran número de pruebas falsas y refutaciones en su larga historia. Al principio, The New York Times se negó como política a informar sobre la prueba de Appel-Haken, por temor a que la prueba se mostrara falsa como las anteriores ( Wilson 2014 ). Algunas supuestas pruebas, como las de Kempe y Tait mencionadas anteriormente, estuvieron bajo escrutinio público durante más de una década antes de ser refutadas. Pero muchos más, escritos por aficionados, nunca se publicaron.
Generalmente, los contraejemplos más simples, aunque inválidos, intentan crear una región que toque todas las demás regiones. Esto obliga a que las regiones restantes se coloreen con solo tres colores. Debido a que el teorema de los cuatro colores es cierto, esto siempre es posible; sin embargo, debido a que la persona que dibuja el mapa se enfoca en una región grande, no se da cuenta de que las regiones restantes pueden ser coloreadas con tres colores.
Este truco se puede generalizar: hay muchos mapas donde si los colores de algunas regiones se seleccionan de antemano, se vuelve imposible colorear las regiones restantes sin exceder los cuatro colores. Un verificador casual del contraejemplo puede no pensar en cambiar los colores de estas regiones, por lo que el contraejemplo parecerá válido.
Quizás un efecto subyacente a este error común es el hecho de que la restricción de color no es transitiva : una región solo tiene que ser coloreada de manera diferente a las regiones que toca directamente, no a las regiones que tocan las regiones que toca. Si esta fuera la restricción, los gráficos planos requerirían cantidades arbitrariamente grandes de colores.
Otras refutaciones falsas violan los supuestos del teorema, como usar una región que consta de múltiples partes desconectadas o no permitir que regiones del mismo color se toquen en un punto.
Tres colores
Si bien cada mapa plano se puede colorear con cuatro colores, es NP-completo en complejidad decidir si un mapa plano arbitrario se puede colorear con solo tres colores. [22]
Generalizaciones
Gráficos infinitos
El teorema de los cuatro colores se aplica no solo a los gráficos planos finitos, sino también a los gráficos infinitos que se pueden dibujar sin cruces en el plano, y aún más generalmente a los gráficos infinitos (posiblemente con un número incontable de vértices) para los cuales cada subgrafo finito es planar. Para probar esto, se puede combinar una prueba del teorema para grafos planos finitos con el teorema de De Bruijn-Erdős que establece que, si cada subgrafo finito de un grafo infinito es k -colorable, entonces el grafo completo también es k -colorable Nash- Williams (1967) . Esto también puede ser visto como una consecuencia inmediata de Kurt Gödel 's teorema de compacidad para lógica de primer orden , simplemente mediante la expresión de la capacidad de coloración de un gráfico de infinito con un conjunto de fórmulas lógicas.
Superficies más altas
También se puede considerar el problema de la coloración en superficies distintas al plano. [23] El problema de 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 χ según la fórmula
donde los corchetes más externos denotan la función de piso .
Alternativamente, para una superficie orientable , la fórmula se puede dar en términos del género de una superficie, g :
Esta fórmula, la conjetura de Heawood , fue propuesta por PJ Heawood en 1890 y, después de las contribuciones de varias personas, probada por Gerhard Ringel y JWT Youngs en 1968. La única excepción a la fórmula es la botella de Klein , que tiene la característica de Euler 0 (por lo tanto la fórmula da p = 7) pero requiere solo 6 colores, como lo mostró Philip Franklin en 1934.
Por ejemplo, el toro tiene la característica de Euler χ = 0 (y género g = 1) y por lo tanto p = 7, por lo que no se requieren más de 7 colores para colorear cualquier mapa en un toro. Este límite superior de 7 es nítido: ciertos poliedros toroidales como el poliedro de Szilassi requieren siete colores.
Una tira de Möbius requiere seis colores ( Tietze 1910 ) al igual que los gráficos de 1 plano (gráficos dibujados con como máximo un cruce simple por borde) ( Borodin 1984 ). Si tanto los vértices como las caras de un gráfico plano están coloreados, de tal manera que no haya dos vértices, caras o pares de vértice-cara adyacentes que tengan el mismo color, entonces nuevamente se necesitan seis colores como máximo ( Borodin 1984 ).
Regiones sólidas
No hay una extensión obvia del resultado de la coloración a regiones sólidas tridimensionales. Mediante el uso de un conjunto de n varillas flexibles, se puede hacer que cada varilla toque a las demás. Entonces, el conjunto requeriría n colores, o n +1 si considera el espacio vacío que también toca cada barra. El número n puede tomarse como un número entero, tan grande como se desee. Fredrick Guthrie conocía estos ejemplos en 1880 ( Wilson 2014 ). Incluso para los cuboides de ejes paralelos (considerados adyacentes cuando dos cuboides comparten un área límite bidimensional) puede ser necesario un número ilimitado de colores ( Reed y Allwright 2008 ; Magnant y Martin (2011) ).
Relación con otras áreas de las matemáticas
Dror Bar-Natan dio una declaración sobre las álgebras de Lie y los invariantes de Vassiliev que es equivalente al teorema de los cuatro colores. [25]
Usar fuera de las matemáticas
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 generalmente requieren solo tres. Los libros sobre cartografía e historia de la cartografía no mencionan la propiedad de los cuatro colores" ( Wilson 2014 , pág . 2). El teorema tampoco garantiza el requisito cartográfico habitual de que las regiones no contiguas del mismo país (como el enclave Kaliningrado y el resto de Rusia) tengan el mismo color.
Ver también
- Red apolínea
- Teorema de los cinco colores
- Coloración gráfica
- Teorema de Grötzsch : las gráficas planas sin triángulos son 3-coloreables.
- Problema de Hadwiger-Nelson : ¿cuántos colores se necesitan para colorear el plano de modo que no haya dos puntos separados por unidades de distancia que tengan el mismo color?
Notas
- ↑ De Gonthier (2008) : "Definiciones: Un mapa plano es un conjunto de subconjuntos disjuntos por pares del plano, llamados regiones. Un mapa simple es aquel cuyas regiones son conjuntos abiertos conectados. Dos regiones de un mapa son adyacentes si sus respectivos cierres tienen un punto común que no es una esquina del mapa. Un punto es una esquina de un mapa si y solo si pertenece a los cierres de al menos tres regiones. Teorema: Las regiones de cualquier mapa plano simple se pueden colorear con solo cuatro colores, de tal manera que dos regiones adyacentes tengan colores diferentes ".
- ^ Swart (1980) .
- ↑ Wilson (2014) , 216–222.
- ^ Hudson (2003) .
- ^ Thomas (1998 , p. 849); Wilson (2014) ).
- ↑ Existe cierta tradición matemática de que Möbius originó la conjetura de los cuatro colores, pero esta noción parece ser errónea. Véase Biggs, Norman ; Lloyd, E. Keith; Wilson, Robin J. (1986). Teoría de grafos, 1736-1936 . Prensa de la Universidad de Oxford. pag. 116 . ISBN 0-19-853916-9. Y Maddison, Isabel (1897). "Nota sobre la historia del problema de colorear mapas" . Toro. Amer. Matemáticas. Soc . 3 (7): 257. doi : 10.1090 / S0002-9904-1897-00421-9 .
- ^ Donald MacKenzie, Prueba de mecanización: Computación, riesgo y confianza (MIT Press, 2004) p103
- ^ FG (1854) ; McKay (2012)
- ^ a b 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
- ^ WW Rouse Ball (1960) El teorema de los cuatro colores , en Ensayos y recreaciones matemáticas, Macmillan, Nueva York, págs. 222-232.
- ^ Thomas (1998) , p. 848.
- ^ Heawood (1890) .
- ^ Tait (1880) .
- ^ Hadwiger (1943) .
- ↑ a b Wilson (2014) .
- ^ Gary Chartrand y Linda Lesniak, gráficos y dígrafos (CRC Press, 2005) p.221
- ^ Wilson (2014) ; Appel y Haken (1989) ; Thomas (1998 , págs. 852–853)
- ^ Thomas (1995) ; Robertson y col. (1996) ).
- ^ Thomas (1998) , págs. 852–853.
- ^ Thomas (1999) ; Pegg y col. (2002) ).
- ^ Gonthier (2008) .
- ^ Dailey, DP (1980), "La singularidad de la colorabilidad y la colorabilidad de las gráficas planas de 4 regulares son NP-completas", Discrete Mathematics , 30 (3): 289-293, doi : 10.1016 / 0012-365X (80) 90236-8
- ^ Ver Ringel (1974).
- ^ Branko Grünbaum, Lajos Szilassi, Realizaciones geométricas de complejos toroidales especiales , Contribuciones a las matemáticas discretas, Volumen 4, Número 1, Páginas 21-39, ISSN 1715-0868
- ^ Bar-Natan (1997) .
Referencias
- Allaire, Frank (1978), "Otra prueba del teorema de los cuatro colores. I.", en D. McCarthy; HC Williams (eds.), Proceedings, 7th Manitoba Conference on Numerical Mathematics and Computing, Congr. Numer. , 20 , Winnipeg, Man .: Utilitas Mathematica Publishing, Inc., págs. 3-72, ISBN 0-919628-20-6, MR 0535003
- Appel, Kenneth ; Haken, Wolfgang (1977), "Every Planar Map is Four Colorable. I. Discharging", 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 , 237 (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, 98 , Con la colaboración de J. Koch., Providence, RI: American Mathematical Society, doi : 10.1090 / conm / 098 , ISBN 0-8218-5103-9, MR 1025335
- Bar-Natan, Dror (1997), "Álgebras de mentira y el teorema de los cuatro colores", Combinatorica , 17 (1): 43–52, arXiv : q-alg / 9606016 , doi : 10.1007 / BF01196130 , MR 1466574
- Bernhart, Frank R. (1977), "Un compendio del teorema de los cuatro colores", Journal of Graph Theory , 1 (3), págs. 207-225, doi : 10.1002 / jgt.3190010305 , MR 0465921
- Borodin, OV (1984), "Solución del problema de Ringel sobre coloración vértice-cara de gráficas planas y coloración de gráficas 1-planas", Metody Diskretnogo Analiza (41): 12-26, 108, MR 0832128.
- Cayley, Arthur (1879), "Sobre los colores de los mapas", Actas de la Royal Geographical Society , Blackwell Publishing, 1 (4): 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 prueba , 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), "Tinting Maps" , The Athenaeum : 726.
- Gethner, E .; Springer, WM (2003), "¿Cuán falsa es la demostración de Kempe del teorema de los cuatro colores?", Congr. Numérico , 164 : 159-175, MR 2050581 , Zbl 1050.05049
- Gethner, Ellen ; Kalichanda, Bopanna; Mentis, Alexander S. (2009), "¿Cuán falsa es la prueba de Kempe del teorema de los cuatro colores? Parte II", involucra , 2 (3): 249-265, doi : 10.2140 / involucr.2009.2.249
- Gonthier, Georges (2005), Una prueba verificada por computadora del teorema de los cuatro colores (PDF) , inédito
- Gonthier, Georges (2008), "Prueba formal: el teorema de los cuatro colores" (PDF) , Notices of the American Mathematical Society , 55 (11): 1382-1393, MR 2463991
- Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zúrich , 88 : 133–143
- Heawood, PJ (1890), "Teorema del color del mapa", Quarterly Journal of Mathematics, Oxford , 24 , págs. 332–338
- Hudson, Hud (mayo de 2003), "Four Colors Do Not Suffice", 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
- Magnant, C .; Martin, DM (2011), "Colorear bloques rectangulares en 3 espacios" , 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), "Gráficos infinitos: una encuesta", 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
- Pegg, Ed, Jr .; Meléndez, J .; Berenguer, R .; Sendra, JR; Hernández, A .; Del Pino, J. (2002), "Book Review: The Colossal Book of Mathematics" (PDF) , Notices of the American Mathematical Society , 49 (9): 1084–1086, Bibcode : 2002ITED ... 49.1084A , doi : 10.1109 / TED.2002.1003756
- Reed, Bruce ; Allwright, David (2008), "Painting the office" , Estudios de casos de matemáticas en la industria , 1 : 1–8
- 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. EE . UU. , 60 (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), "Efficiently four-coloring planar graphs", Actas del 28º Simposio ACM sobre Teoría de la Computación (STOC 1996) , págs. 571–575, doi : 10.1145 / 237814.238005 , MR 1427555
- Robertson, Neil ; Sanders, Daniel P .; Seymour, Paul ; Thomas, Robin (1997), "El teorema de los cuatro colores", J. Combin. Teoría Ser. B , 70 (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", Science , Nueva York: Dover Publications, 202 (4366): 424, Bibcode : 1978Sci ... 202..424S , doi : 10.1126 / science. 202.4366.424 , ISBN 0-486-65092-8
- Swart, Edward Reinier (1980), "Las implicaciones filosóficas del problema de los cuatro colores" , American Mathematical Monthly , Mathematical Association of America, 87 (9), págs. 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 , 45 (7), págs. 848–859, MR 1633714
- Thomas, Robin (1995), El teorema de los cuatro colores
- Tietze, Heinrich (1910), "Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen" [Algunas observaciones sobre el problema de colorear los mapas en superficies unilaterales], Informe anual del DMV , 19 : 155-159
- Thomas, Robin (1999), "Teoremas menores excluidos recientes para gráficos", en Lamb, John D .; Preece, DA (eds.), Surveys in combinatorics, 1999 , London Mathematical Society Lecture Note Series, 267 , Cambridge: Cambridge University Press, págs. 201–222, doi : 10.1017 / CBO9780511721335 , ISBN 0-521-65376-2, MR 1725004
- Tait, PG (1880), "Observaciones sobre la coloración de mapas", Proc. R. Soc. Edimburgo , 10 : 729, doi : 10.1017 / S0370164600044643
- Wilson, Robin (2014) [2002], Four Colors Suffice , Princeton Science Library, Princeton, Nueva Jersey: Princeton University Press, ISBN 978-0-691-15822-8, MR 3235839
enlaces externos
- "Problema de los cuatro colores" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Weisstein, Eric W. "Blanuša snarks" . MathWorld .
- Weisstein, Eric W. "Colorear mapa" . MathWorld .
- Lista de generalizaciones del teorema de los cuatro colores en MathOverflow