El gran teorema de la combinatòria moderna Autors/ores 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ó. Descàrregues Text complet Publicat 2012-03-02 Com citar Noy, M. (2012). El gran teorema de la combinatòria moderna. Butlletí De La Societat Catalana De Matemàtiques, 26(2), 103–136. Retrieved from https://revistes.iec.cat/index.php/BSCM/article/view/73748.001 Més formats de citació ACM ACS APA ABNT Chicago Harvard IEEE MLA Turabian Vancouver Descarregar citació Endnote/Zotero/Mendeley (RIS) BibTeX Número Vol. 26 Núm. 2 (2011) Secció Articles Llicència La propietat intel·lectual dels articles és dels respectius autors. Els autors en el moment de lliurar els articles a la revista Butlletí de la Societat Catalana de Matemàtiques per a sol·licitar-ne la publicació accepten els termes següents: Els autors cedeixen a la Societat Catalana de Matemàtiques (filial de l’Institut d’Estudis Catalans) els drets de reproducció, comunicació pública i distribució dels articles presentats per a ser publicats a la revista Butlletí de la Societat Catalana de Matemàtiques. Els autors responen davant la Societat Catalana de Matemàtiques, de l'autoria i l'originalitat dels articles presentats. És responsabilitat dels autors l’obtenció dels permisos per a la reproducció de tot el material gràfic inclòs en els articles. La Societat Catalana de Matemàtiques, està exempta de tota responsabilitat derivada de l’eventual vulneració de drets de propietat intel·lectual per part dels autors. Els continguts publicats a la revista estan subjectes —llevat que s’indiqui el contrari en el text o en el material gràfic— a una llicència Reconeixement - No comercial - Sense obres derivades 3.0 Espanya (by-nc-nd) de Creative Commons, el text complet de la qual es pot consultar a https://creativecommons.org/licenses/by-nc-nd/3.0/es/deed.ca. Així doncs, s’autoritza el públic en general a reproduir, distribuir i comunicar l’obra sempre que se’n reconegui l’autoria i l’entitat que la publica i no se’n faci un ús comercial ni cap obra derivada. La revista Butlletí de la Societat Catalana de Matemàtiques no es fa responsable de les idees i opinions exposades pels autors dels articles publicats.