miércoles, 1 de junio de 2016

Un misterio de las matemáticas resuelto tras 40 años #Ciencia Kanija 2.0 #noticias


Artículo publicado por Bill Condie el 30 de mayo de 2016 en COSMOS Magazine

Matemáticos de Georgia Tech han ofrecido una demostración para la conjetura de Kelmans-Seymour de la teoría de grafos.

Matemáticos de Georgia Tech creen haber llegado a una demostración para un problema matemático de hace 40 años – la conjetura de Kelmans-Seymour de la teoría de grafos.

Grafo K5

Grafo K5 completo Crédito: Wikimedia Commons

La teoría de grafos trata de puntos, o vértices, conectados por líneas, llamadas aristas, que a veces forman unas marañas aparentemente imposibles. Pueden usarse para describir mucho problemas prácticos que implican relaciones entre elementos en sistemas sociales y de información.

Es la rama de las matemáticas que ayuda a planificar un uso más eficiente de las rutas de vuelo, o que tu GPS tome una decisión sobre cómo evitar problemas de tráfico, o incluso cómo gestionar tus amigos en Facebook.

La estructura de un sitio web, por ejemplo, puede representarse mediante un grafo indirecto, y Google usa la teoría de grafos como parte de los algoritmos del motor de búsqueda para comprobar los enlaces entre páginas.

La conjetura de Kelmans-Seymour toma su nombre de Paul Seymour, de la Universidad de Princeton, y Alexander Kelmans, que describieron la conjetura de forma independiente – Seymour en 1977 y Kelmans en 1979.

La conjetura se enuncia del siguiente modo: "Si un grafo G tiene cinco conexiones y no es planar, entonces G tiene un TK5".

Siempre hay una forma de dibujar un grafo planar de forma que las líneas entre puntos no se crucen. Esto tiene su importancia también en el mundo real.

Como explica Ben Brumfield, de Georgia Tech: "En el mundo real, un microprocesador envía electrones de un punto a otro a través de una miríada de caminos conductores. Si los cruzas, el procesador se cortocircuita".

En otras palabras, se necesita un grafo planar – o lo más cercano a uno que se pueda conseguir – para realizar esta tarea, y los grafos y los algoritmos de grafos pueden ayudar a modelar un sistema adecuado.

Y aquí es donde entra en juego el TK5.

"Del TK5 se puede decir que el demonio está en los detalles", escribe Brumfield. "Los TK5 son parientes mayores de los K5, una formación muy simple que tiene el aspecto de una estrella de cinco puntos insertada en un pentágono. Recuerda a un símbolo ocultista, y eso encaja con nuestra idea. Un TK5 en un grafo nos garantiza que no habrá ningún estado 'planar' claro y simple".

El matemático de Georgia Tech Xingxing Yu, que ayudó a completar la demostración de la Conjetura de Kelmans-Seymour, dice que esto es lo que hace que la conjetura sea tan importante, dado que ayuda a identificar un TK5 en grafos más complejos.

"Es de ayuda en redes detalladas para lograr rápidas soluciones que son razonables y requieren poca complejidad computacional", comenta a Brumfield.

Yu asumió la tarea de completar la demostración de Robin Thomas, antiguo colaborador de Seymour y ahora profesor en Georgia Tech.

"Intenté con gran tesón demostrar la conjetura de Kelmans-Seymour en la década de 1990, pero no lo logré", comenta. "Yu es una matemático excepcional, y esto lo demuestra. Estoy encantado de que haya logrado completar la demostración".

Yu si hizo cargo de la conjetura hace unos ocho años.

"Estaba convencido de que estaba listo para trabajar en la conjetura", comenta Yu. Atrajo al proyecto a los estudiantes graduados Jie Ma en 2008, y Yan Wang y Dawei en 2010.

El equipo ha enviado dos artículo sobre la demostración, y hay dos más en camino. Ahora se enfrentan a ver su demostración puesta a prueba por otros matemáticos. Sólo si no logran que falle se mantendrá como demostración.

Pero Wang está seguro del trabajo de su equipo.

"Hemos pasado muchísimo tiempo intentando encontrar fallos, y no hemos podido, por lo que esperamos que todo vaya bien", comenta.