Flips sur les triangulations de la sphère : une borne inférieure pour le temps de mélange

-- Thomas Budzinski (ENS & Paris-Sud)

Time: 11:00 -- Location: Salle Philippe Flajolet du LIX

Une des manières les plus naturelles de simuler une triangulation uniforme de la sphère à n faces est d'utiliser une méthode de Monte-Carlo : on démarre avec une triangulation quelconque puis, de manière répétée, on choisit une arête uniformément et on la "flippe", i.e. on l'efface et on la remplace par l'autre diagonale du quadrilatère qui se forme. On montrera que le temps de mélange de la chaîne de Markov obtenue est au moins en \(n^{5/4}\).

Category: seminars
Tags: Combi seminar combinatorics