Abstract
We prove that in all regular robust expanders (Formula presented.), every edge is asymptotically equally likely contained in a uniformly chosen perfect matching (Formula presented.). We also show that given any fixed matching or spanning regular graph (Formula presented.) in (Formula presented.), the random variable (Formula presented.) is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.
| Original language | English |
|---|---|
| Pages (from-to) | 3-14 |
| Number of pages | 12 |
| Journal | Random Structures and Algorithms |
| Volume | 64 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - Jan 2024 |
| Externally published | Yes |
Keywords
- expander graphs
- perfect matchings
- random matchings
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver