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 : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr