Name
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 [JS89] mixes in polynomial time and generates an (almost) uniformly random perfect matching. Furthermore, we prove that such graphs have at least $\Omega(d)^n$ any perfect matchings, thus proving the Lovasz-Plummer conjecture [LP86] for this family of graphs. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.4230/LIPIcs.ITCS.2022.61 | ITCS |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Farzam Ebrahimnejad | 1 | 0 | 1.01 |
| Ansh Nagda | 2 | 0 | 0.68 |
| Shayan Oveis Gharan | 3 | 323 | 26.63 |