Clément Legrand-Duchesne - "Dirac's theorem and the switch geometry of perfect matchings"

A talk by Clément Legrand-Duchesne, Jagiellonian University, given on April 29, 2026.

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≥1/2 contain many perfect matchings, that 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, becomes connected, or becomes an expander. For k≥3, these thresholds concentrate around c=1/2. Finally, we also show that the threshold at which this space exhibits positive minimum degree is related to the notorious Caccetta-Häggkvist conjecture.

Видео Clément Legrand-Duchesne - "Dirac's theorem and the switch geometry of perfect matchings" канала TCS Group at Jagiellonian