moteur de recherche

Séminaire Algo - Matěj Stehlík
Séminaire Algo - Matěj Stehlík
29-Jan-2019 14:00
Age: 84 days





Matěj Stehlík (Université Grenoble Alpes)

Quadrangulations projectives et bornes topologiques sur le nombre chromatique

Seminar room 4B125 (Copernic building)

Abstract: Le nombre chromatique d'un graphe est le plus petit nombre de couleurs qu'on peut affecter à ses sommets, de sorte qu'aucune arête ne soit monochrome. Il s'agit peut-être du paramètre le plus étudié de la théorie des graphes. En 1978, Lovász a résolu une conjecture sur le nombre chromatique des graphes de Kneser en utilisant le théorème topologique de Borsuk-Ulam. Schrijver a affiné ce résultat en montrant que certains sous-graphes induits des graphes de Kneser, maintenant appelés graphes de Schrijver, ont le même nombre chromatique. 

Dans cet exposé, je vais me concentrer sur la classe des graphes appelés quadrangulations projectives. Ce sont des graphes qu'on peut plonger d'une certaine manière dans l'espace projectif réel RP^d, et leur nombre chromatique peut être borné par le théorème de Borsuk-Ulam. Des exemples de quadrangulations projectives incluent des sous-graphes des graphes de Schrijver, ce qui conduit à un raffinement des théorèmes de Lovász et de Schrijver. Je discuterai également comment les complexes simpliciaux associés à ces graphes fournissent la seule triangulation simpliciale connue de RP^d avec un nombre de sommets polynomial en d. 

Travail en commun avec Tomas Kaiser.








<- Back to: Accueil