Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 06 mai 2014 à 14h00 en B107, Lionel Pournin nous parlera de : Sur les diamètres de certains graphes de flips

Résumé : Considérons une surface orientable S de genre g avec k>0 bords. Plaçons un ensemble E de n points sur S de manière que chaque bord contienne au moins un de ces points. Le graphe des flips de E est le graphe G dont les sommets sont les triangulations de E et dont les arêtes joignent deux triangulations qui peuvent être transformées l'une en l'autre par un flip (cette opération consiste à échanger les diagonales d'un quadrilatère). Le graphe G est connexe. Si on considère les triangulations de E à homéomorphisme près, les sommets de E étant marqués, le diamètre de ce graphe est borné. Lorsque S est un disque dont le bord contient tous les points de E, G est le graphe de l'associaèdre de dimension n-3. Il a été montré récemment que le diamètre de ce graphe est 2n-10 dès que n est supérieur à 12. La preuve de ce résultat sera esquissée. Plusieurs autres résultats sur le diamètre de G seront ensuite donnés et discutés dans le cas où S n'est pas un disque.


Dernière modification : mardi 09 janvier 2018 Valid HTML 4.01! Valid CSS! Organisateurs : Cyril.Banderier & Gerard.Duchamp at lipn.univ-paris13.fr