Agenda depuis 2026

Seminaire : Séminaire ACRO : Clément Legrand-Duschesne (12/01, 10h00, REU 4.05)

12/01/2026 à 10h00

Le séminaire de l'équipe ACRO aura lieu lundi 12 janvier à 10h en salle REU 04.05 du TPR2. On aura le plaisir d’écouter Clément Legrand-Duschesne (Jagiellonian University, Kraków) qui nous parlera de théorème de Dirac et de géométrie de couplages parfaits. Title: Dirac’s theorem and the geometry of perfect matchings Abstract: Dirac's theorem states that all $n$-vertex graphs with minimum degree $n/2$ contain a perfect matching. This is tight and graphs with minimum degree $cn$ are more generally called $c$-Dirac graphs. In fact, a phase transition occurs at $c=1/2$: $c$-Dirac graphs with $c \ge 1/2$ contain $(\frac{cn}{e+o(1)})^{n/2}$ perfect matchings [Cuckler, Kahn 2009]. Moreover, for any fixed $c$-Dirac graph $G$ with $c\ge 1/2$, there exist nice probability distributions on the perfect matchings of $G$ called spread distributions [Pham, Sah, Sawhney, Simkin 2024]; as a result, if the edges of $G$ are sampled with probability $O(\log(n)/n)$, the resulting graph still contains a perfect matching with good probability, thereby witnessing that these matchings are "everywhere" in $G$. With Ross Kang, we give a new understanding of this phase transition by describing how the perfect matchings of a Dirac graph cluster. More precisely, we analyse the geometrical properties of the space of perfect matchings of $G$, endowed with the graph metric such that perfect matchings differing on at most $k$ edges are at distance one. For any fixed $k$, we pinpoint sharp thresholds at which this space is shattered into exponentially many components, has isolated perfect matchings, becomes connected, or becomes an expander. https://acro.lis-lab.fr/seminars