Revistes Catalanes amb Accés Obert (RACO)

El gran teorema de la combinatòria moderna

Marc Noy

Resum


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 K5 i K3,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ó.

Text complet: PDF