Daniel Kráľ (Masaryk University, República Checa) fue el ponente del último coloquio conjunto ICMAT-UAM-UC3M-UCM, “Analytic approach to extremal combinatorics”, que tuvo lugar el viernes 23 de junio en el Departamento de Matemáticas de la Universidad Autónoma de Madrid. El investigador se centró en su trabajo más reciente, que estudia la interacción entre la teoría de Ramsey –un “conjunto de resultados que establece la imposibilidad del caos completo”–, y la combinatoria extrema. Entrevistamos a Kráľ con motivo del coloquio.
Imagen cedida por el investigador
Laura Moreno Iraola (ICMAT)
En su coloquio, “Analytic approach to extremal combinatorics”, se centró en las herramientas analíticas y la teoría de los límites combinatorios, ¿podría explicar de qué trata esta teoría?
La combinatoria se ha centrado, tradicionalmente, en el estudio de objetos discretos. Sin embargo, los objetos 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 discretas tradicionales. Por ello, es necesario aproximar los objetos discretos con los que trabajamos. Esto 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–. Este 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 con objetos continuos, 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. Además, en algunos casos, es posible entender grafos muy grandes y densos como operadores autoadjuntos y analizar sus propiedades espectrales, que se pueden relacionar con el número de caminos cerrados que tiene el grafo.
¿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 veinte 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. De hecho, esta teoría, junto con el álgebra de banderas (flag algebras), desarrollada por Sasha Razborov y muy estrechamente ligada a los límites combinatorios, cambiaron la perspectiva de la combinatoria extrema moderna.
“Los objetos que encontramos en las matemáticas discretas modernas y en sus aplicaciones informáticas tienen un tamaño enorme”
¿Cómo se relacionan la combinatoria extrema y la teoría de Ramsey, el tema de 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.
¿Podría destacar algunos de los principales avances en este campo en los últimos años?
En mi opinión, una gran parte de la combinatoria extrema moderna se basa en el método de regularidad de Szemerédi y sus extensiones a varios escenarios. Esta permite ver los objetos analíticos que representan los grandes objetos discretos como límites de particiones de regularidad que se aproximan a objetos discretos. Como he comentado, esto dio como resultado el método del álgebra de banderas. Y todos estos desarrollos juntos condujeron a avances en numerosos problemas clásicos abiertos durante décadas. Entre tantos resultados recientes, algunos de los específicos que primero me vienen a la mente son el trabajo de Sasha Razborov sobre el problema de Erdős-Rademacher y sus extensiones, de Christian Reiher. También, el trabajo sobre la conjetura de Erdős-Faber-Lovász de Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku y Deryk Osthus.
¿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.
¿Cuáles son los principales retos en este momento en la teoría de límites combinatorios?
Dentro de la teoría de los límites combinatorios destaca la conjetura de Aldous-Lyons sobre la aproximación de límites de grafos dispersos. Esta conjetura –casi– equivale a decir que todos los grupos generados finitamente son sofic. Aunque hay diferencias técnicas entre estas dos cuestiones, se cree –en general– que el avance en uno de los problemas implicará, inmediatamente, progreso en el otro.
“La teoría de los límites combinatorios abre nuevas perspectivas sobre muchos problemas en otros campos, como cuestiones sobre los algoritmos probabilísticos de lectura masiva de datos y nuevos enlaces con la estadística”
Y, ¿en combinatoria extrema?
Me gustaría destacar dos. El primero es la conjetura de Sidorenko, una pregunta muy natural de enunciar, pero, a la vez, muy complicada. Timothy Gowers [matemático del Collège de France] ha comentado sobre esta conjetura en su blog lo siguiente: “Parece el tipo de afirmación que podemos probar que es falsa con un contraejemplo simple o verdadera con una prueba sencilla, pero esta impresión es incorrecta”. De hecho, la conjetura supone un enorme desafío y, seguramente, se tendrán que desarrollar nuevos métodos para resolverla. El segundo es el llamado problema del tetraedro, que trata sobre la densidad mínima de conjunto. Aunque el método del álgebra de banderas permitió mejorar los límites existentes, también se tendrán que desarrollar nuevas técnicas para resolverlo.
¿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.
“La teoría de Ramsey es un conjunto de resultados que establece la imposibilidad del caos completo”
¿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.
Los límites de grafos determinados por un número finito de densidades de subgrafos –límites de grafos finitamente forzados– forman puntos extremos del espacio límite del grafo y, por lo tanto, están estrechamente relacionados con la combinatoria de extremos, ya que son soluciones únicas de ciertas preguntas naturales de teoría de grafos de extremos. Se esperaba –según los primeros resultados obtenidos– que disponer de estructura especial de límites grafos finitamente forzados, permitiría dar con nuevos métodos para ciertos problemas extremos difíciles. Sin embargo, mis colaboradores y yo descartamos por completo esta idea, al proporcionar un marco universal para construir límites de grafos complejos finitamente forzados, construido sobre nuestro método de restricciones decoradas. En particular, mostramos que cualquier límite de un grafo –por complejo que sea– puede integrarse en un límite de un grafo finitamente forzado. Lászsló Lovász presentó este resultado al recibir el Premio Abel en 2021, y fue algo 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 optimización discreta. Me fascina la forma en que la optimización discreta interconecta matemáticas con algoritmos y, estos, con intrigantes problemas del mundo real.
Actualmente, junto con mis estudiantes, exploro el vínculo entre la teoría de matroides y los precondicionadores para la programación de enteros y métodos de diseño que permiten reemplazar matrices complejas con matrices en las que la mayoría de las entradas son iguales a cero, sin cambiar el problema de optimización asociado.
El coloquio está disponible en YouTube.
Más información
Página personal de Daniel Král’
Una versión de esta entrevista ha sido publicada en SINC a fecha 03/07/2023.