web analytics

Posts etiquetados con ‘Teoría de grafos’

El Premio Abel 2021, concedido a Laszló Lovász y Avi Wigderson

La Academia Noruega de Ciencias y Letras ha anunciado su decisión sobre el Premio Abel 2021, que ha recaído en los matemáticos László Lovász, del Instituto de Matemáticas Alfréd Rényi y de la Universidad Eötvös Loránd de Budapest, Hungría, y Avi Wigderson, del Instituto de Estudios Avanzados de Princeton (EE.UU.), “por sus contribuciones fundacionales a la informática teórica y a la matemática discreta, y por su papel destacado en la configuración de éstas como campos centrales de la matemática moderna”.

Trazaremos unas breve biografías de ambos matemáticos. László Lovász nació  en 1948 en Budapest, y es fruto de la excelente escuela matemática húngara, especialmente brillante en algunos temas como la matemática discreta. László Lovász fue un alumno superdotado, ganador de medallas de oro en tres Olimpiadas Matemáticas Internacionales (164, 1965 y 1966), en dos ocasiones con la puntuación máxima.

 

László Lovász

Lovász obtuvo su grado de Ph.D. en 1970 de la Universidad Eötvös Loránd, Budapest, donde trabajó hasta 1975. Sin abandonar Hungría, pasó a la Universidad de Szeged, hasta 1982, regresando entonces a Eötvös  y crear el Departamento de Ciencias de la Computación. Después fue profesor de la Universidad de Yale durante la década de 1990, colaborando como investigador en el Microsoft Research Center hasta 2006. Entonces volvió a Hungría para dirigir el Instituto de Matemáticas de la Academia de Ciencias.

Entre los premios que ha ganado, están el Premio Wolf de 1999, el Premio Knuth de 1999, el Premio Gödel de 2001, el Premio Bolyai en 2007 y el Premio Kyoto de 2010, todos ellos de un indudable prestigio.

Su trabajo de investigación se centra en la combinatoria y la teoría de grafos, y sus aplicaciones a la complejidad en computación, un ejemplo extraordinario de cómo una investigación básica incide en las aplicaciones de frontera. Su labor se traduce en más de 300 artículos y libros que han conseguido un impacto enorme.

Reunión del Comité Ejecutivo de IMU en Perth (Australia)

 

Tuve la oportunidad de trabajar 8 años con Laci Lovász, de 2007 a 2010 como Presidente de la Unión Matemática Internacional (IMU) y de 2011 a 2014 como exPresidente. Tras su labor en IMU, fue elegido presidente de la Academia de Ciencias de Hungría entre 2014 y 2020.

En 2007 lo invitamos a Madrid para participar en un Simposio de la Fundación Areces, Las fronteras de las Matemáticas, que coordiné con mi colega de la Real Academia de Ciencias, Manuel López Pellicer. En todos estos años, he podido apreciar no sólo su extraordinaria calidad matemática, pero también su calidad humana, su sencillez y su siempre bonhomía.

 

En cuanto al otro premiado, Avi Wigderson nació en Haifa (Israel) en 1956. Ingresó en el Technion en 1977, y se licenció en Ciencias de la Computación en 1980. Se trasladó a Princeton para realizar sus estudios de posgrado, y se doctoró en 1983. En 1986 Wigderson regresó a Israel para ocupar un puesto en la Universidad Hebrea de Jerusalén. Al año siguiente fue nombrado profesor titular en 1991. En 1999 también aceptó un puesto en el Instituto de Estudios Avanzados (IAS) de Princeton, y en 2003 renunció a su puesto en la Universidad Hebrea para residir a tiempo completo en el IAS.

Avi Widgerson

Además de la medalla Nevanlinna, concedido por la IMU en el Congreso Internacional de Matemáticos (ICM) en Zúrich en 1994, obtuvo como Lovasz los Premios Gödel (2009) y Knuth (2019).

Su investigación es muy amplia en intereses que incluyen la teoría de la complejidad, los algoritmos paralelos, la teoría de grafos, la criptografía, la computación distribuida y las redes neuronales.

Según la Academia Noruega, la teoría de la “complejidad computacional” -que se ocupa de la velocidad y la eficiencia de los algoritmos- surgió en la década de los 70 y ahora es un campo establecido tanto en las matemáticas como en la informática teórica. “Lovász y Wigderson han sido las principales fuerzas de este desarrollo en las últimas décadas. Sus trabajos se entrelazan de muchas maneras y, en particular, ambos han hecho contribuciones fundamentales para entender la aleatoriedad en la computación y para explorar los límites de la computación eficiente”, afirmó Hans Munthe-Kaas, presidente del Comité Abel.

Este es el vídeo del anuncio

Imagen de previsualización de YouTube

Un premio muy merecido por ambos científicos.

___________

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias, Real Academia Galega de Ciencias).

 

Etiquetas: , , , , ,
Categorias: General

Elogio del matemático aficionado

El anuncio de un reciente resultado conseguido por un aficionado a las matemáticas nos lleva a hacer una reflexión sobre este tipo de aportaciones.

El pasado 17 de abril, la revista Quanta Magazine recogía un excelente artículo de Evelyn Lamb titulado Decades-Old Graph Problem Yields to Amateur Mathematician. Evelyn Lamb se define a sí misma como matemática y escritora, y trabaja como tal en la Universidad de Utah. Este resultado ha sido tratado también en numerosos medios de comunicación nacionales e internacionales.

El grafo presentado por Aubrey de Grey

El artículo en cuestión se refería al logro de un aficionado a las matemáticas, Aubrey de Grey, sobre un conocido problema en teoría de grafos, el llamado Problema de Hadwiger–Nelson. Hugo Hadwiger y Edward Nelson se preguntaron en 1950 sobre el número mínimo de colores que se deberían usar para colorear un plano de tal manera que puntos distanciados en una unidad no tuviesen el mismo color.

El problema se puede plantear de esta manera simple. Suponemos que tenemos un grafo en un plano, de manera que todas las líneas que conecten dos vértices tengan la misma longitud (podía ser la unidad). Tengan en cuenta que no todos los vértices del grafo tienen que estar conectados entre sí. Ahora coloreamos cada punto, de manera que dos puntos conectados no tengan el mismo color. La pregunta de Nelson fue: ¿cuál es el número mínimo de colores que necesitamos?

Se sabe que la respuesta tiene que estar entre 4 y 7, y no ha habido más avances hasta que  Aubrey D.N.J. de Grey colgó el 8 de abril en arxiv su artículo The chromatic number of the plane is at least 5,  donde descartaba el 4. Su contraejemplo era un gráfico de 1581 vértices, cifra que fue después mejorada con otro contraejemplo de 633 vértices, mediante un proyecto de Polymath, lanzado por el propio de Grey el pasado 10 de abril, Polymath proposal: finding simpler unit distance graphs of chromatic number 5.

Gráfico de 826 vértices que necesita al menos 5 colores

De Grey es un jugador aficionado de Othelo, creado por Goro Hasegawa, un estudiante de Mito, Japón, en esas fechas, y patentado en 1971. Parece ser que es una actualización de otro juego, Reversi, comercializado independientemente por los británicos Lewis Waterman y John W. Mollett, en 1880. De Grey conoció a unos cuantos matemáticos como jugador de Othelo, y ellos lo iniciaron en la teoría de grafos. Desde entonces, confiesa que las matemáticas son muchas veces el tema al que vuelve cuando quiere descansar.

El interés de este resultado ha venido no sólo de su valor intrínseco (el artículo son 12 páginas y está todavía sin publicar en una revista), sino del propio autor. Aubrey de Grey es un conocido gerontólogo, nacido el 20 de abril de 1963 en Londres, Inglaterra, y educado en la prestigiosa Universidad de Cambridge, en el Reino Unido. De Grey es autor del libro The Mitochondrial Free Radical Theory of Aging (La teoría del envejecimiento de los radicales libres mitocondriales), muy controvertido. Defiende una ingeniería de tejidos para su rejuvenicimento que prolongaría la vida hasta los 1000 años. Esta charla TED, A roadmap to end aging resume sus puntos de vista. Esta entrevista es también esclarecedora:

Imagen de previsualización de YouTube

Aubrey de Grey es un aficionado a las matemáticas, como en su día lo fue Pierre de Fermat, que era notario, aunque su pasión fueran las matemáticas y nos dejara importantes logros. Y esto nos lleva a una reflexión sobre los aficionados a las matemáticas que se aparecen como investigadores.

Pierre de Fermat

Desde que comencé como profesor en la Universidad de Santiago de Compostela, he recibido más de una vez las cartas o visitas de aficionados que aportaban supuestos resultados matemáticos, generalmente referidos a la cuadratura del círculo, la trisección del ángulo, la conjetura de Fermat, la conjetura de Goldbach, … , es decir, problemas que son fácilmente explicables y que aparentan tener soluciones también simples (la cuadratura del círculo y la trisección del ángulo no requieren respuesta, las matemáticas hace ya siglos que los resolvieron).

Estas cartas y visitas se intensificaron desde que me incorporé en 1986 como investigador al Consejo Superior de Investigaciones Científicas (CSIC). Una de las características de los aficionados es su afán de que quede bien establecido que ellos son los autores de tales demostraciones, y así sus insistencia en llevarlos al Registro de la Propiedad Intelectual o “patentarlos”. Mi respuesta ha sido desde hace ya unos cuantos años: “Escríbalo usted en LaTex y envíelo al arxiv y a una revista especializada”.

Es evidente que la mayoría de estos artículos no tienen pies ni cabeza, otros, sin embargo, están razonados. De ahí mi respuesta, si lo envía usted a los expertos, tendrá una buena respuesta (también están los amigos de las conspiraciones, y ahí no cabe la razón).

En cualquier caso, creo que debemos respetar que haya personas que tengan curiosidad por las matemáticas, y que hagan sus pinitos en el tema, aunque, hoy en día, todos tenemos acceso a mucha información para aquilatar hasta donde podemos llegar con nuestros esfuerzos.

Respetemos pues al aficionado, proporcionémoles la información necesaria para que encamine adecuadamente sus esfuerzos, sigamos trabajando en la buena divulgación matemática para el público general, mejoremos las enseñanzas en las aulas para nuestros estudiantes. Todo ello redundará en una mayor apreciación de nuestra disciplina.

____

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias, ICSU).

Etiquetas: ,
Categorias: General

La danza de las moléculas

Para Esther

 

Ich bin hier,
Weil ich hier hingehör.
Vom Kopf bis Fuß bin ich verliebt.
Du bist mutig,
Weil du mir,Treue schwörst.
Zwischen all den schönen Souveniers.

Sprich mich an,
In dem Takt,
Der dieses Lied zu unserem Hit macht.
Brich den Beat,
Mit Gefühl.
Du bist so schön,
Weil du lachst.

Uhu…Uhuhuu,
Mein herz tanzt!
Uhuhu!
Und jedes Molekül bewegt sich!

Tanz Der Molekule, de M.I.A.

La Química y las Matemáticas son ciencias que han tenido y mantienen muchas mas relaciones de las que uno podría pensar. En esta entrada (y en otras que iremos publicando en las próximas semanas) iremos desgranando algunas de ellas, con la confianza de que el lector aprecie una vez mas el valor añadido de las matemáticas para cualquier disciplina.

Imagen de previsualización de YouTube

Para los antiguos griegos, el mundo extaba compuesto de cuatro elementos, que identificaron con cuatro de los poliedros reguales, reservando el quinto para el éter, tal y como describimos en una entrada anterior.

Una observación importante es que, a medida que la química fue evolucionando y conociendo mejor como estaba constituida la materia (y aquí comenzó a confundirse con la física), así fue también evolucionando su relación con las matemáticas.

Alexander Crum Brown

Quizás el primer intento serio de matematizar la química se debe al químico escocés Alexander Crum Brown (1838 – 1922). Médico de formación, Brown se dedicó después a la investigación de la química. Pasó un tiempo en Alemania, retornando finalmente a la Universidad de Edinburgo. Fue elegido acdémico de la Royal Society of Edinburgh en 1863, institución de la que fue Vicepresidente de 1905 a 1911.

Artículo seminal de Crum Brown

Crum Brown desarrolló un trabajo pionero en la representación de los componentes químicos en forma de diagramas. Los símbolos de los átomos se rodeaban de un círculo, y los conectaba con líneas de puntos para representar las valencias. Los dobles enlaces los representaba con dos líneas paralelas. Sus contribuciones se dieron también en la fisiología, fonética, matemáticas y cristalografía.

Esta asociación de compuestos químicos con gráficos fue muy estudiada posteriormente y ha resultado extremadamente interesante para la química. Uno de los nombres relevantes es el del científico croata-americano Milan Randić, nacido en Belgrado en 1930, donde sus padres, de origen croata, vivían temporalmente. Mas tarde se trasladaron a Zagreb, en cuya universidad estudió Randic la carrera de física teórica, realizando después su tesis doctoral en la universidad de Cambridge. Su interés se centró mas tarde en la matemática discreta, que aplicó a las representaciones de moléculas y biomoléculas. Aunque actualmente su trabajo se desarrolla en los Estados Unidos, pasa tres meses cada año en Lubliana. En 1975 introdujo el llamado índice de Randić, el primer índice de conectividad. Randic es sin duda uno de los creadores de la llamada Química matemática.

Milan Randic

Otro de los pioneros es otro químico croata, Nenad Trinajstić, nacido en Zagreb en 1936. De hecho, Nenad Trinajstić fue alumno de doctorado de Randic. Después de varias estancias en Estados Unidos, es ahora profesor emérito en la Universidad de Zagreb. Es el autor de la primera monografía sobre la teoría de grafos química.

Es curioso que fuera el matemático Arthur Cayley el primero en considerar grafos moleculares en 1874, cuando ni siquiera se había utilizado el término grafo en matemáticas. Otro gran matemático que trabajó en esos temas fue James Sylvester. Recordemos que Cayley y Sylvester son los grandes creadores de la actual teoría de matrices.

Y es que una estructura molecular nos lleva intuitivamente a la noción de grafo (veáse figura).

Grafo químico y matriz adyacente

La matriz de adyacencia es el instrumento algebraico que asociamos a un grafo, por la sencilla regla de poner un 1 si los dos átomos están ligados, y un cero en otro caso. Y una vez obtenida la matriz, ya sabemos calcular el polinomio característico y el espectro.

Otra matriz asociada al grafo es la matriz de distancia, que da la longitud mínima para unir dos átomos, y 0 si son el mismo. Y existen mas tipos de matrices para caracterizar la molécula.

Otro elemento matemático, en este caso topológico, son los índices como el de Randic, basado en la matriz de adyacencia. Otros, como el índice de Wiener está basado en la matriz de distancia. Y hay mas índices, algunos basados en la teoría de la información.

¿Para que puede ser utilizado todo esto? Son muchas las aplicaciones, como la predición de propiedades específicas y selección de nuevas moléculas, apliacaciones biológicas y farmacológicas, etc.

Un claro ejemplo de cómo las matemáticas, guiando a la química (y a veces al revés, la química delante), produce resultados insospechados.

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias, ICSU)

Etiquetas: ,
Categorias: General