Con cuatro no basta: el número cromático del plano

Hace mucho que los especialistas se las ven y se las desean con el problema de Hadwiger-Nelson, pero ahora un profano (experto en antienvejecimiento) delimita la solución con la ayuda de los ordenadores.

 

Según diversos especialistas, el informático e investigador del envejecimiento Aubrey de Grey ha logrado un gran avance en un importante problema formulado hace 70 años. Como explica en un artículo publicado en arXiv, hacen falta al menos cinco colores para colorear los puntos del plano de forma que no haya dos puntos separados por una unidad de distancia que sean del mismo color. Hasta ahora se creía que el número

201805_003
El biogerontólogo Aubrey de Grey cree que el envejecimiento se podrá evitar y revertir. Ha sido cofundador de la Fundación Matusalén y de la Fundación de Investigaciones sobre Estrategias para la Senescencia Insignificante mediante Ingeniería (SENS, concepto acuñado por De Grey). Ahora parece haber logrado un avance en el problema matemático del número cromático del plano [Bruce Klein y Susan Fonseca-Klein].
mínimo de colores estaba entre cuatro y siete. De Grey ha definido en el ordenador una red de nudos conectados por líneas que representan una unidad de distancia que solo se pueden colorear, respetando las normas del problema, con cinco colores. Los especialistas están buscando si hay alguna posibilidad de hacerlo con cuatro, pero algunos, como, por ejemplo, Gil Kalai, de la Universidad Hebrea de Jersusalén, han hecho saber que aceptan la prueba.

El problema investigado por De Grey, que se conoce como número cromático del plano o problema de Hadwiger-Nelson, se asemeja al problema de los cuatro colores de la teoría de grafos. En este, sin embargo, las aristas del grafo no se pueden cortar y su longitud es indiferente. En el problema de Hadwiger-Nelson es casi al revés: se toman en consideración puntos con una separación predeterminada y no importa si las líneas que los conectan se cortan o no. Como en el problema de los cuatro colores, el ordenador desempeña en este otro problema cromático un papel esencial; solo con ayuda técnica se pueden examinar los numerosísimos grafos posibles.

El grafo de De Grey tiene 1581 nudos. No es posible verificar el número de colores mínimo con un ordenador en un tiempo aceptable. Por eso, este matemático no profesional ideó un procedimiento que encuentra un atajo para la verificación. El nuevo grafo está formado por grafos de Moser sistemáticamente interconectados. Un grafo de Moser es un grafo ideado hace casi 60 años consistente en siete puntos que demuestra que el número de los colores ha de ser como poco cuatro. Con esa construcción se obtiene el grafo para el que cuatro colores no bastan. Está por saberse aún si el número cromático del plano es cinco, seis o siete. O si no tendremos que esperar otros setenta años para conocer la respuesta.

 

Lars Fischer / spektrum.de
Artículo traducido y adaptado por Investigación y Ciencia con permiso de Spektrum der Wissenschaft.
Esta información ha sido publicada originalmente en Investigación y Ciencia

 

 

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s