El gran teorema de la combinatòria moderna

Resumen

Si pregunteu a un expert quin és el resultat estrella de la combinatòria de les últimes dècades, és probable que contesti: el teorema dels menors de Robertson i Seymour. Aquest resultat, una de les grans fites de la matemàtica del segle passat, afirma el següent: si G és una classe de grafs tancada per menors, llavors hi ha un nombre finit d'obstruccions que determinen si un graf és a G. L'exemple clàssic és el teorema de Kuratowski: si G és la classe dels grafs planaris, les obstruccions són els grafs K₅ i K_3,3. La prova ocupa uns vint articles, amb un total de més de cinc-centes pàgines. En aquest treball expliquem el contingut del teorema i donem una idea de les seves implicacions, de les relacions amb l'algorísmia i amb la lògica, de les eines fonamentals a què ha donat lloc i de la seva demostració.