Résumé de séminaire

Résumé :

Considérons le graphe dont les sommets sont les parties à k éléments de l'ensembles des entiers de 1 à n, et dont les arêtes relient les parties disjointes. Ce graphe, le "graphe de Kneser" KG(n,k), a pour nombre chromatique n-2k+2. C'est un célèbre théorème de Lovasz, démontré en 1979 avec l'utilisation du théorème de Borsuk-Ulam. La même année, L. Schrijver renforçait ce théorème, toujours à l'aide du théorème de Borsuk-Ulam: même en ne gardant que les parties à k éléments "stables", i.e., ne contenant ni entiers consécutifs, ni simultanément les entiers 1 et n (graphes de Schrijver), le nombre chromatique reste égal à n-2k+2.

En 2003, J. Matousek proposait la première preuve combinatoire de ce résultat (sans fonction continue, sans approximation simliciale, sans groupe d'homologie), et, en 2005, G. Ziegler donnait une preuve combinatoire du théorème de Schrijver. Ces deux preuves s'appuient sur une formulation adéquate du lemme de Tucker, version discrète du théorème de Borsuk-Ulam.

Nous présenterons au cours de ce séminaire une formule que K. Fan découvrit en 1952 et qui généralise le lemme de Tucker. Nous en donnerons une preuve plus compacte que celle connue auparavant, et nous montrerons qu'elle peut s'appliquer efficacement au calcul du nombre chromatique des graphes de Schrijver, simplifiant la preuve de Ziegler.