Análisis del problema de los cuatro colores.

Abstract

[EN]The four color theorem establishes that any map in a plane can be coloured with just four colours so that the regions sharing a common limit —as long as it is not one single point— do not share the same color. It is also referred to as Guthrie’s theorem in honor of F. Guthrie who conjectured the theorem for the first time in 1852. The conjecture was communicated afterwards to De Morgan and from there to the community in general. In 1878, Cayley wrote the first article about the conjecture. Kempe (1879) and Tait (1880) independently showed fallacious proofs. Kempe’s proof was accepted for a decade until Heawood showed a mistake using a map with 18 faces —although a map with nine faces is enough to show the fallacy. Heawood’s conjecture provided a very general statement to color maps, showing that in a space of genre 0 —including a sphere or a plane— for colors are enough. Ringel and Youngs (1968) demonstrated that for the genre, the superior limit given by Heawood’s conjecture, with the exception of Klein’s bottle, genre > 0 —where Heawood’s formula gives as a result seven, but the correct limit is six. It can be proved that six colors are enough for the case of genre 0. This number can be easily reduced to five, but reducing the number of colors to four was very difficult. This was eventually obtained by Appel and Haken (1977), who developed assisted evidence on a computer showing that four colors were enough. However, as part of the demonstration lay in a thorough analysis of plenty of discrete cases by a computer, many mathematicians do not accept it. Mistakes in the analysis have not been found yet, that’s why the demonstration seems acceptable.

[ES]El teorema de los cuatro colores establece que cualquier mapa en un plano puede colorearse con cuatro colores de tal manera que las regiones que comparten unlímite común (que no sea un solo punto) no comparten el mismo color. Este problema a veces también se denomina problema de Guthrie en honor a F. Guthrie, quien conjeturó el teorema por primera vez en 1852. La conjetura se comunicó luego a De Morgan y de allí a la comunidad en general. En 1878, Cayley escribió el primer artículo sobre la conjetura. Kempe (1879) y Tait (1880) dieron pruebas falaces de forma independiente. Laprueba de Kempe fue aceptada durante una década hasta que Heawood mostró un error usando un mapa con 18 caras (aunque un mapa con nueve caras basta para mostrar la fala cia). La conjetura de Heawood proporcionó una afirmación muygeneral para colorear mapas, mostrando que en un espacio de género 0 (incluyendo l a esfera o el plano), cuatro colores son suficientes. Ringel y Youngs (1968) demostraron que para el género, el límite superior proporcionado por la conjetura de Heawood también da el número necesario de colores, con la excepción de la botella de Klein, género > 0 (caso en que la fórmul a de Heawood da siete, pero el límite correcto es seis). Se puede demostrar que seis colores son suficientes para el caso de género 0, y este número se puede reducir fácilmente a cinco, pero reducir el número de colores hasta cuatro resultó muy difícil. Este resultado fue finalmente obtenido por Appel y Haken (1977), quienes construyeron una prueba asistida por computadora de que cuatro colores eran suficientes. Sin embargo, debido a que parte de la demostración consistió en un análisis exhaustivo de muchos casos discretos por una computadora, algunos matemáticos no la aceptan. Aún no se han encontrado fallos en el análisis, por ello la demostración parece válida.