AlGCo : algorithmes, graphes et combinatoire

Accueil | Annonces | Membres | Formation | Projets | Visiteurs | Publications | Séminaire

Le séminaire/groupe de travail AlGCo a lieu le jeudi de 10h à 11h (et quelques) en salle E.323.

Shalom Eliahou
Permutations signees et theoreme des quatre couleurs
Ce travail est en commun avec Cedric Lecouvey.

L'objet de cet expose est de presenter une nouvelle reformulation algebrique du theoreme des quatre couleurs. Etant donnees deux permutations dans le groupe symetrique Sn, de nombreux chemins vont de l'une a l'autre dans le graphe de Cayley de Sn relatif aux transpositions elementaires. Certains de ces chemins peuvent avoir une propriete supplementaire, appelee la signabilite. Celle-ci s'exprime en terme d'une comparaison entre les graphes de Cayley de Sn et du groupe hyperoctaedral Bn des permutations signees. On montrera que le theoreme des quatre couleurs est equivalent a l'affirmation que, pour tout n>=1 et toute paire de permutations dans Sn, il existe un chemin signable entre celles-ci.