2021/03/15 by Farzam Ebrahimnejad, Ebrahimnejad, Farzam, Ansh Nagda +3
Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2103.08683
openalex publication_date 2021/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the ratio of the number of near perfect matchings to the number of perfect matchings in d-regular strong expander (non-bipartite) graphs, with 2n vertices, is a polynomial in n, thus the Jerrum and Sinclair Markov chain [JS89] mixes in polynomial time and generates an (almost) uniformly random perfect matching. Furthermore, we prove that such graphs have at least Ω(d)n any perfect matchings, thus proving the Lovasz-Plummer conjecture [LP86] for this family of graphs.