“La llamada optimización discreta conecta las matemáticas con intrigantes problemas del mundo real”

Tiempo de lectura estimado: 8 minutos

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.

¿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.

¿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.

¿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.

¿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.

¿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.