La combinatoria, ayer y hoy. Entrevista con Pierre Duchet

Pierre Duchet es uno de los escasos especialistas franceses en combinatoria. Ha sido testigo privilegiado de los grandes avances de las matemáticas discretas, desde los descubrimientos de Erdös sobre los números primos en progresión aritmética hasta la demostración del teorema de los cuatro colores o de la conjetura de Berge (Claude Berge fue su director de tesis).

¿A qué época se remontan los inicios de la combinatoria? La combinatoria, en el sentido moderno del término, es el estudio sistemático de las estructuras. Puede remontarse a los años treinta. Incluso pueden situarse sus orígenes geográficos: ¡Hungría es el país donde la combinatoria cuenta con mayor reconocimiento y desarrollo! Por ejemplo, Erdös, Turán, Halmos, Szemerédi, Bollobás, Lovász, Frankl… Todos estos célebres matemáticos nacieron en Hungría. ¡Casi sería más difícil citar especialistas en combinatoria que no fueran húngaros! Hoy, aparte de Hungría, existen escuelas de combinatoria en Norteamérica, en la antigua URSS, en algunos países de Europa del Este y, en menor medida, en Francia; más recientemente, también en Japón (desde hace treinta años) y en China (desde hace unos diez años). Dicho esto, la combinatoria podría remontarse al genial Euler y a su problema de los puentes de Königsberg [véase FOCUS]. Es combinatoria estructural, es decir, una «forma poco rígida de hablar del espacio». O a Laplace y su visión atomista del espacio y del universo. O incluso a Leibniz, que, para «predecir el futuro», se ve llevado a «recortar» superficies [alusión al cálculo integral]. ¡También habría que hablar de Poincaré y de su Analysis situs! Pero hay que reconocerlo: la combinatoria no despega de verdad hasta la explosión de la investigación operativa (IO) y la aparición de los grafos [véase FOCUS] como estructura matemática por derecho propio. Un ejemplo arquetípico de la IO es el problema del viajante de comercio: imaginemos a un representante que viaja en coche y debe visitar cada una de las N ciudades de un país para reunirse con clientes. Su itinerario debe minimizar el número total de kilómetros recorridos, porque la gasolina es cara. Entre los N! itinerarios posibles, ¿cuál es óptimo? ¿Y quid si todas las distancias valen 1 y el viajante debe pasar una sola vez por cada ciudad (problema del circuito hamiltoniano)? Este es el tipo de problemas que plantea la investigación operativa. Para valores pequeños de N, conocemos la solución, pero enseguida solo disponemos, en el mejor de los casos, de heurísticas para ayudar al viajante de comercio. Este problema es extremadamente difícil. [Se dice que es NP-difícil.] Y hoy volvemos a los problemas planteados en el siglo 18^.º. La combinatoria no apareció por azar: forma parte de un continuo histórico.

Problemas NP-difíciles -----------------------

**El siglo 18^.º, Poincaré a comienzos del 20^.º, los años treinta y la teoría de grafos, el nacimiento de la IO durante la Segunda Guerra Mundial… ¿Y qué sucede después?**

La IO ha producido numerosísimos problemas de optimización discreta, como el coloreado de grafos. La búsqueda de un algoritmo es la finalidad de estos problemas. Una variante importante del problema de coloreado de un grafo es el problema del 5-flujo, enunciado por William Thomas Tutte en 1954 [véase FOCUS].

La IO, la teoría de grafos, la algorítmica, pero también el estudio de los sistemas de conjuntos (set systems), llamados asimismo hipergrafos (hypergraphs), siguen siendo grandes proveedores de problemas para la combinatoria: problemas de packing (encontrar apilamientos de objetos tan densos como sea posible en un espacio dado), problemas de covering (¿una estructura combinatoria cubre otra?), la conjetura de los cuatro colores —hoy teorema—, la conjetura de Hadwiger… La teoría de grafos era su base, y estos grandes problemas generaban la actividad y toda la investigación del campo. Pero hoy ya no es realmente así.

####

Hoy, los grandes problemas ya no son los principales proveedores de investigación: muchos están muy avanzados o resueltos (la conjetura de Berge, hoy teorema fuerte de los grafos perfectos, o el teorema de los cuatro colores). En los años setenta se desarrolla una teoría de la complejidad para abordar los problemas de decisión (aquellos a los que puede responderse sí o no). Están los problemas «fáciles», de complejidad polinómica. Forman lo que se denomina la clase P (de «polynomial»). Para resolver estos problemas, sabemos encontrar un algoritmo cuyo tiempo de cálculo está acotado superiormente por un polinomio del tamaño de la entrada. Después están los problemas «difíciles, incluso francamente imposibles», que forman la denominada clase NP. Son aquellos para los que conocemos una forma «rápida» de verificar una solución. Por último, hay problemas para los que no sabemos si son P, NP u otra cosa, ¡y problemas que por su propia naturaleza no pertenecen a la teoría de la complejidad! Todos los investigadores están convencidos de que NP no está incluida en P. Pero nadie es capaz de demostrarlo. El problema del viajante de comercio es NP-difícil, es decir, al menos tan difícil como un problema NP-completo. [Un problema es NP-completo si resolverlo en tiempo polinómico conlleva resolver en tiempo polinómico cualquier problema NP.] En la práctica, un problema NP-difícil es insoluble. Y con los años se ha comprobado que muchos de los grandes problemas que suscitaban investigaciones en combinatoria eran NP-difíciles. Es el caso del problema del número cromático total, bastante fácil de explicar: se conjetura que el número cromático total de un grafo G es inferior a D(G) + 2, donde D(G) es el grado máximo de los vértices de G. Veamos qué significa esto. Colorear un grafo G con k colores (una k-coloración de G) consiste en asignar a cada vértice y a cada arista de G uno de entre k colores, de modo que dos objetos adyacentes (arista-vértice, vértice-vértice o arista-arista) tengan siempre colores distintos. El número cromático total de G es el menor número entero k para el que existe una k-coloración de G. Determinar este número es un problema NP-difícil. Pero a veces puede caracterizarse o acotarse. La conjetura de Hadwiger es otro problema de coloreado no resuelto. Supongamos que el número cromático del grafo no dirigido G es superior a m (lo que significa que es imposible colorear los vértices de G con menos de m colores sin que dos vértices unidos reciban el mismo color). Entonces G posee m subgrafos conexos disjuntos conectados entre sí por al menos una arista.

¿Qué herramientas matemáticas han permitido resolver, o al menos abordar, los problemas de las matemáticas discretas? La caja de herramientas del especialista en combinatoria contiene un número muy reducido de resultados fundamentales. El primero de ellos, probablemente el más importante, es el teorema de los matrimonios. [Sean un conjunto de chicos, un conjunto de chicas y la aplicación que asocia a cada chico las chicas que le gustan. Si, para cada subgrupo de chicos, el número de chicas que les gustan es superior al número de chicos de ese subgrupo, entonces puede emparejarse a cada chico con una chica que le gusta y que aún no está emparejada.] Al intentar generalizar esta problemática, se llega a una «teoría de emparejamientos» bastante potente, en la que la teoría de matroides desempeña un papel importante.

Claude Berge (1926–2002).**

Por lo demás, existen metodologías. Por ejemplo, Paul Seymour y su equipo abordan los problemas de teoría de grafos siempre con el mismo enfoque de «descomposición»: se trata de conseguir «romper» un grafo dado, de manera que los únicos grafos «irrompibles» posean una estructura conocida. Cuando se quiere ensamblar un grafo cualquiera a partir de bloques elementales conocidos, el arte consiste en encontrar el «pegamento» adecuado. Debo reconocer que no creía que este enfoque llegaría algún día a resolver la conjetura de Berge y, sin embargo… En los problemas de optimización discreta, a menudo se intenta reformularlos linealmente: las restricciones se modelizan mediante un sistema de inecuaciones lineales sobre los datos variables, y entonces el problema se reduce a maximizar (o minimizar) cierta función de los datos, que también es lineal. Nos encontramos así en las condiciones de aplicación del teorema fundamental de la programación lineal [véase también en este número], con la importante diferencia de que los óptimos del problema combinatorio deben corresponder a valores enteros de las variables, y no a valores racionales (o reales) cualesquiera. Cuando las estructuras que modelizan el problema son «amables», puede demostrarse que el óptimo en valores enteros coincide con el óptimo fraccionario. Por lo demás, existen muy pocos resultados generales que permitan analizar las estructuras. Se procede por analogía. El equipo de Seymour, de nuevo, tuvo la idea de comparar los grafos con palabras sobre una superficie. Así, al generalizar un teorema de Kuratowski (¡que era polaco!), elaboraron una teoría de menores de grafos. En una veintena de artículos publicados a lo largo de más de veinticinco años, lograron demostrar la célebre conjetura de Wagner [según la cual, en toda familia infinita de grafos, uno de los grafos es isomorfo a un menor de otro].

Cuando el Loto inspira un problema no resuelto ------------------------------------------------

La «estructura» parece fundamental en combinatoria. ¿Qué es una «estructura»? ¡Hay que desconfiar de la palabra «estructura»! Un árbol, un grafo, un hipergrafo, un sistema de conjuntos… todo ello define herramientas de modelización que un matemático puede manipular cualitativa y cuantitativamente. En cambio, un grafo bipartito [un grafo que puede colorearse usando solo dos colores] proporciona una herramienta de modelización, pero no es manipulable. La combinatoria estructural se interesa por todo lo que puede modelizarse de forma inmediata como un conjunto de conjuntos finitos; ¡es muy amplio! En realidad, hay que desarrollar una intuición de lo que es una «buena estructura», y para ello se necesitan herramientas de representación. Los diagramas de Venn, o «patatoides», son una herramienta de representación, igual que la geometría o la topología lo son para el espacio. Otros campos que estudian las estructuras son el álgebra y la combinatoria algebraica. Pero en álgebra siempre se define al menos una operación sobre la estructura en cuestión. ¡Nosotros ni siquiera tenemos eso! Nos interesamos por la conectividad entre los elementos (saber si están unidos, conectados).

¿Cuáles son las grandes teorías elaboradas para estudiar las estructuras? La teoría de grafos plantea muchísimos problemas interesantes, más de los que resuelve. Y además, al pasar de los grafos no dirigidos a los dirigidos, ¡se da un salto de complejidad fenomenal! ¡Es la jungla! También hemos hablado de la combinatoria estructural. Hay que mencionar asimismo la combinatoria enumerativa, vinculada al recuento (contar con una metodología dada). El recuento se refiere al aspecto cuantitativo de las estructuras (¿son numerosas, escasas? ¿Cuántas hay exactamente, asintóticamente?). Los problemas de recuento abundan. Hacer combinatoria sobre los números, por ejemplo, equivale a revelar estructuras aritméticas particulares. Otro campo importante es la teoría de Ramsey, según la cual siempre hay orden en una estructura, con tal de que sea «lo bastante grande». Una pregunta típica de esta teoría es: «¿Cuál es el número mínimo de elementos que hay que reunir para estar seguro de que se cumple tal propiedad?» En realidad, esta teoría procede de problemas extremales muy generales. Un ejemplo sencillo es el problema del Loto: ¿cuántos boletos distintos hay que marcar como mínimo para tener la certeza de acertar, pongamos, cuatro números ganadores? ¡Este problema, pese a numerosas investigaciones, sigue sin resolverse! Un problema extremal, en el sentido general, consiste en minimizar una función de tres parámetros k, n y t. El número entero n es el tamaño del conjunto de referencia (n = 49 números en el caso del Loto), k es el número de elementos de los subconjuntos considerados (siempre se marcan k = 6 números en un boleto de Loto). Por último, t es el número mínimo de elementos de los subconjuntos que se exige cubrir (para el Loto, se pide garantizar t = 4 aciertos). Eso es un problema extremal: minimizar la cardinalidad de la familia T de subconjuntos de k elementos tal que, cualquiera que sea el subconjunto E de t elementos, se tenga la certeza de encontrar un conjunto F, perteneciente a la familia T, que contenga E. Salvo algunos casos triviales, no sabemos resolver estos problemas. Para continuar con los grandes campos de la combinatoria, hay que hablar de la teoría de diseños (design theory). Es una teoría de estructuras regulares. He aquí un ejemplo: en un dodecaedro, se trata de la disposición de todos los cubos formados por ocho de los vértices del dodecaedro. Los poliedros regulares, los códigos correctores de errores y las redes son configuraciones. Uno de los grandes problemas de esta teoría es la clasificación de los planos proyectivos [véase FOCUS]. Es un problema muy antiguo. Más en general, se plantea la cuestión de la existencia de t-configuraciones. Recientemente se ha logrado demostrar que no existe ningún plano proyectivo de orden 10. Pero más allá de 10, y más allá de los planos proyectivos, no sabemos gran cosa… La teoría de nudos y trenzas también pertenece a la combinatoria: ¡el diagrama de un nudo es la combinatoria de una curva! ¿Cómo reconocer si un nudo es trivial? ¿Cómo deshacer un nudo que sabemos que es trivial? Estas cuestiones son de una dificultad temible.

Hacemos combinatoria sin saberlo -----------------------------------------

Al oírle, ¡la combinatoria parece omnipresente! ¿Qué lugar ocupa dentro de las matemáticas? Muchos matemáticos hacen combinatoria sin saberlo. Pero, en realidad, en 2010 las matemáticas discretas todavía no son reconocidas como un campo autónomo. Ausentes de los grandes congresos internacionales, aún se las considera una herramienta, no un objeto de estudio. ¡Incluso simples consideraciones de informáticos! Es muy injusto: si los problemas parecen a priori más fáciles en el mundo continuo que en el discreto —donde a menudo son inabordables—, quizá se deba a que lo continuo es una aproximación de la realidad. Veo los reales como una comodidad de modelización que oculta el bosque de la realidad. ¡Lo discreto tiene numerosas aplicaciones en química molecular y física atómica! Existe una auténtica visión combinatoria del mundo. Aun así, sigue siendo difícil atraer a los estudiantes hacia la combinatoria. ¿La razón? Las matemáticas discretas no son objeto de una teoría bien jerarquizada. No se encuentra en ellas verdadera profundidad teórica; los problemas apenas se pueden relacionar [sic.] unos con otros. Pero es un defecto de juventud: esta teoría solo pide madurar. Mi colega estadounidense Jack Edmonds sabe plantear buenos problemas de optimización. *\En la misma sala, Edmonds está hojeando [Tangente 131, dedicado a las matemáticas en Estados Unidos.\]* Un «buen problema» es un problema que está en NP y en co-NP.

¿Cuáles son, pues, las grandes problemáticas generales que abordan hoy los especialistas en combinatoria? Pues bien, todo teorema min-max se considera importante, porque revela la existencia de una estructura. Así, una generalización de la problemática de los matrimonios consiste en buscar el número máximo de conjuntos disjuntos en una familia dada de conjuntos. Es el problema de empaquetamiento (o packing problem). El problema dual de optimización consiste en cubrir todos los elementos con el menor número posible de conjuntos: es el problema de cobertura (o covering problem). Los grafos perfectos constituyen un ejemplo de teorema min-max: el número mínimo de colores necesarios para colorear un grafo perfecto —su número cromático— coincide con el número máximo de vértices unidos dos a dos —su clique máxima—. Esta propiedad caracteriza los grafos perfectos. Por otra parte, para cambiar por completo de registro y hablar de objetos más sencillos, están todos los problemas relativos a los poliominós, esos objetos geométricos elementales formados por pequeños cuadrados unitarios pegados unos a otros. Al unir dos cuadrados obtenemos… un dominó. Pues bien, no sabemos contar el número de poliominós formados por n cuadrados, ni siquiera asintóticamente (se conjetura que hay menos de una constante multiplicada por 4ⁿ). Otro problema sintomático del infierno que nos hacen pasar estos pequeños bichos: consideremos un poliominó cualquiera. Se busca teselarlo con barras horizontales de tamaño 3 —triminos horizontales— y dominós verticales, de modo que todo el poliominó quede cubierto y que ni los triminos ni los dominós se superpongan. ¡Saber si se puede teselar así un poliominó es un problema NP-completo! Es desconcertante… Dicho esto, conjeturo que, si nos restringimos a los poliominós simplemente conexos —es decir, sin agujeros—, el problema vuelve a ser tratable…

#### **

Endre Szemeredi (nacido en 1940).**

Por último, la teoría de números está llena de problemas abiertos, en particular gracias a Erdös (las conjeturas de Erdös-Szemeredi y de Erdös-Turan, el problema de discrepancia de Erdös, objeto actualmente de intensas investigaciones…). Pero aquí los matemáticos dieron un golpe de efecto: Ben Green y Terence Tao demostraron en 2005 que existen progresiones aritméticas de longitud arbitraria en el conjunto de los números primos. Utilizan herramientas de combinatoria aditiva y una teoría nueva que ahora se denomina teoría ergódica. ¡Así que a veces también hay éxitos!