2026-07-21T12:58:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15657 2024-03-06T10:55:52Z ddc:004 open_access

Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs Ebrahimnejad, Farzam Nagda, Ansh Gharan, Shayan Oveis perfect matchings approximate sampling approximate counting expanders 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 [Jerrum and Sinclair, 1989] mixes in polynomial time and generates an (almost) uniformly random perfect matching. Furthermore, we prove that such graphs have at least Ω(d)ⁿ many perfect matchings, thus proving the Lovasz-Plummer conjecture [L. Lovász and M.D. Plummer, 1986] for this family of graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Farzam Ebrahimnejad and Ansh Nagda and Shayan Oveis Gharan 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.61 urn:nbn:de:0030-drops-156579 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.61 eng https://creativecommons.org/licenses/by/4.0/legalcode