Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
summary
Gives a randomized algorithm that approximates and samples perfect matchings in d-regular ε-spectral expanders in time n^{o(log d)} (more precisely n^{o(log d) or log(1/ε)}), and proves a nearly tight lower bound m_n ≥ (d/e)^n times a negligible error when ε is small. Key tools are a bound on the ratio m_k/m_{k+1}, showing any size n−1 matching admits a short augmenting path of length O(log_{1/ε} n), and a novel analysis using random bipartite subgraphs to transfer alternating BFS arguments to the non-bipartite case.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 3:00Algorithmic
- 4:06Van der Ley
- 6:04Second Theorem
- 7:27Proof
- 10:28Main Lemma
- 11:17Proof of Main Lemma
- 13:39Proof of Non-Bipartite
- 18:31Future Directions
related talks
01h 07mMarrying Graph Convergence and Cascade Models
35mSuperlinear Lower Bounds for Multipass Graph Processing
27mList Recovery and Local Decoding of Expander Codes
01h 31mGraphons and Graph Limits 2
47mService Rates Of Mds Codes & Fractional Matchings In Quasi-Uniform Hypergraphs
10mQuery, Communication and Discrepancy
58mExponential-Time Algorithms
23mTowards General and Tight Hardness Results for Graph Problems