Polynomial mixing time for edge flips on quadrangulations.
Probabilités et Statistique
This talk will revolve around recent joint work with Alexandre Stauffer in which we give the first polynomial upper bound for the relaxation time of the edge flip Markov chain on rooted quadrangulations. A quadrangulation of size n is a connected planar graph endowed with a cellular embedding in the sphere such that all of its n faces have degree 4, considered up to orientation-preserving homeomorphisms of the sphere itself; we call it rooted when it is endowed with a distinguished oriented edge. Given a (rooted) quadrangulation of size n, a step of the Markov chain we are interested in – a so-called “edge flip” – consists in choosing an edge uniformly at random, deleting it and replacing it with one of the three possible edges (two when the original edge is adjacent to only one face) which, if drawn, recreate a quadrangulation. We will see how one can relate the edge flip chain on quadrangulations to a “leaf translation” chain on plane trees (which has a natural interpretation as a chain on the set of Dyck paths, and on other Catalan structures as well). Having discussed how to set up a successful comparison between the two chains which exploits the well-known bijection by Schaeffer and a specific construction of leaf translations as sequences of edge flips, we shall estimate the relaxation time of the leaf translation chain by improving on a result by Movassagh and Shor
- Accueil
- Annuaire
- Equipes
- Evènements
- Congrès
- Invités
- Séminaires, Groupes de Travail et Colloquium
- Séminaires
- Analyse Complexe et Equations Différentielles
- Analyse Fonctionnelle
- Analyse Numérique et Equations Aux Dérivées Partielles
- Arithmétique
- Formes Automorphes
- Géométrie Algébrique
- Géométrie des espaces singuliers
- Géométrie Dynamique
- Histoire des Mathématiques
- Physique Mathématique
- Probabilités et Statistique
- Singularités et Applications
- Théorie Analytique et Analyse Harmonique
- Topologie
- Colloquium
- Groupes de Travail
- Analyse harmonique et théorie analytique
- Autour des fractales
- Calcul de Malliavin et processus fractionnaires
- Déformations des singularités de surfaces
- Equations aux dérivées partielles
- Extraction du signal
- Fondements mathématiques du deep learning
- Géométrie Non-Archimédienne
- Géométrie Stochastique
- Idéaux de Hodge
- Leçons d'Analyse
- Matrices Aléatoires
- Probabilités
- Statistique et Grande Dimension
- Systèmes Dynamiques
- Topologie
- W-algèbres
- Doctorants et Post-doctorants
- Séminaires
- Soutenances
- Anciens Séminaires et Groupes de Travail
- Formation par la Recherche
- Laboratoire
- Liens utiles
- Projets
- Recrutements
- Services