Este experto en grafos estudia problemas en la frontera entre las matemáticas y las ciencias de la computación, con aplicaciones en el diseño de algoritmos, para la lectura masiva de datos, por ejemplo, o el análisis de estructuras complejas, como las redes sociales. Recientemente lo ha contado en Madrid.
Especialista en teoría estructural y algorítmica de grafos [nodos relacionados por aristas], en los últimos años Daniel Kráľ, profesor de la Universidad Masaryk (República Checa), analiza problemas que se encuentran en la intersección entre la matemática discreta y la informática. En este campo ha realizado importantes contribuciones, como la resolución de las llamadas conjetura de Lovász-Plummer y conjetura de Steinberg.
Le interesa especialmente la denominada teoría de los límites combinatorios, que permite estudiar objetos discretos enormes –que aparecen, por ejemplo, al estudiar las redes sociales o sistemas– a partir de aproximaciones. De hecho, ha desarrollado dos proyectos europeos ERC sobre la conexión entre esta teoría y otra: la teoría de Ramsey, un “conjunto de resultados que establece la imposibilidad del caos completo”.
Sobre estos temas habló recientemente en un coloquio conjunto organizado por el Instituto de Ciencias Matemáticas (ICMAT) y las universidades Autónoma, Carlos III y Complutense de Madrid.
¿De qué trata la teoría de los límites combinatorios?
La combinatoria se ha centrado, tradicionalmente, en el estudio de objetos discretos. Sin embargo, los que encontramos en las matemáticas discretas modernas y en sus aplicaciones informáticas tienen un tamaño enorme, lo que dificulta el uso de las herramientas tradicionales. Por ello, es necesario aproximar los objetos discretos con los que trabajamos. Es lo que propone, por ejemplo, el conocido lema de regularidad de Szemerédi –uno de los resultados que le valió al matemático el Premio Abel en 2012–. El resultado aproxima un grafo grande con uno pequeño que captura las propiedades clave del grande.
La teoría de los límites combinatorios proporciona buenas aproximaciones de grandes objetos discretos, de manera parecida a como se extienden los números racionales a los números reales, o como se usa la integración en lugar de la suma, para fines contables.
¿Con qué motivación se empezó a trabajar en este campo? ¿Qué tipo de preguntas se trataban de resolver?
La teoría de los límites combinatorios se originó hace unos 20 años a partir de la investigación liderada por Christian Borgs, Jennifer Chayes y László Lovász en Microsoft Research. Su objetivo principal era desarrollar herramientas para aproximar y analizar grandes redes informáticas, y consiguieron cimentar una teoría que no solo es adecuada para analizar estas grandes redes, sino que también se puede aplicar en diversos contextos de matemáticas discretas. Esta teoría, junto con el álgebra de banderas (flag algebras), desarrollada por Sasha Razborov, cambió la perspectiva de la combinatoria extrema moderna.
La teoría de los límites combinatorios se originó en Microsoft Research con el objetivo de desarrollar herramientas para aproximar y analizar grandes redes informáticas
¿Cómo se relacionan la combinatoria extrema y la teoría de Ramsey, el tema en el que se centró su charla?
La teoría de Ramsey es un conjunto de resultados que establece la imposibilidad del caos completo. Entre todos ellos, uno de los más simples es el conocido como el principio del palomar. Una de sus variantes dice que, si se colorean 10n bolas con 10 colores, siempre habrá n bolas del mismo color. La teoría de Ramsey extiende esta simple observación a escenarios mucho más complejos. Una afirmación típica de esta teoría dice, básicamente, que todo objeto discreto lo suficientemente grande tiene una parte que se comporta ‘bien’. La combinatoria extrema nos permite estimar el número de partes de estos objetos grandes que se comportan bien.
Según la teoría de Ramsey, del total de estrellas del cielo nocturno, siempre podemos seleccionar un subconjunto de ellas para dibujar diferentes objetos como: un triángulo, un cuadrilátero, un paraguas o un pulpo. / NASA, ESA, AURA/Caltech, Palomar Observatory et al.
¿La teoría tiene alguna aplicación a otros campos?
La teoría de los límites combinatorios abre nuevas perspectivas sobre muchos problemas en otros campos. Por ejemplo, permite entender cuestiones sobre los algoritmos probabilísticos de lectura masiva de datos, llamados ‘algoritmos de prueba de propiedades’. También ha abierto nuevos enlaces con la estadística: un vínculo bastante obvio consiste en proporcionar modelos para redes; otro, menos evidente, es con pruebas de cuasialeatoriedad e independencia.
La teoría de los límites combinatorios permite, por ejemplo, entender cuestiones sobre los algoritmos probabilísticos de lectura masiva de datos
¿Cómo comenzó a investigar en esta área?
Me fascinó la naturaleza multifacética de la teoría de los límites combinatorios. Ofrece un conjunto muy amplio y versátil de herramientas, que son aplicables en diversas áreas de investigación que siempre me han interesado, como la teoría de grafos y la informática teórica. Me atrajo mucho la cantidad de conexiones que tiene con otras áreas, en particular, con el análisis, la combinatoria, la teoría ergódica, la teoría de grupos, la teoría de la probabilidad y la estadística. Además, me interesó avanzar en los métodos de la teoría de los límites combinatorios y proporcionar una comprensión más profunda de algunos de los conceptos clave.
Daniel Kráľ es especialista en combinatoria extrema e informática teórica. / Foto cedida par el entrevistado
¿Qué aportes ha realizado?
He contribuido tanto al desarrollo de la teoría de los límites combinatorios como a la ampliación del rango de aplicaciones en combinatoria extrema. Dentro de la teoría de límites combinatorios, me han interesado principalmente los límites de grafos densos, sobre el que tengo un resultado, junto a mis colaboradores, que Lászsló Lovász presentó al recibir el Premio Abel en 2021 y por lo que me sentí muy honrado.
Hemos obtenido un resultado sobre límites de grafos densos que Lászsló Lovász presentó al recibir el Premio Abel en 2021
¿Qué otros campos de investigación le interesan?
Mi investigación siempre ha estado enfocada en temas en la interfaz entre las matemáticas y la informática. Además de trabajar en aplicaciones de técnicas analíticas en combinatoria y estudiar problemas en combinatoria extrema, desde hace poco también estudio el uso de métodos combinatorios en la llamada optimización discreta. Me fascina la forma en que esta interconecta matemáticas con algoritmos y, estos, con intrigantes problemas del mundo real.
Ecuaciones para modelar el crecimiento de tumores, algoritmos para probar futuras máquinas, avanzadas teorías de computación y una fórmula para marcar un gol son algunos de los temas que se han tratado esta semana en la capital andaluza durante el 9º Congreso Europeo de Matemáticas.
La frecuencia con la que los animales voladores, sean aves, insectos o murciélagos, agitan sus alas es proporcional a la raíz cuadrada de su masa corporal dividida por el área alar. Investigadores daneses han dado con esta fórmula, que también se puede aplicar para animales nadadores como las ballenas y los pingüinos.
