Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.61
URN: urn:nbn:de:0030-drops-156579
URL: https://drops.dagstuhl.de/opus/volltexte/2022/15657/
Ebrahimnejad, Farzam ; Nagda, Ansh ; Gharan, Shayan Oveis
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{ebrahimnejad_et_al:LIPIcs.ITCS.2022.61,
author = {Ebrahimnejad, Farzam and Nagda, Ansh and Gharan, Shayan Oveis},
title = {{Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {61:1--61:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15657},
URN = {urn:nbn:de:0030-drops-156579},
doi = {10.4230/LIPIcs.ITCS.2022.61},
annote = {Keywords: perfect matchings, approximate sampling, approximate counting, expanders}
}
| Keywords: | perfect matchings, approximate sampling, approximate counting, expanders | |
| Seminar: | 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 25.01.2022 |
