Random perfect matchings in regular graphs

Bertille Granet, Felix Joos

Research output: Contribution to journalArticleResearchpeer-review

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 languageEnglish
Pages (from-to)3-14
Number of pages12
JournalRandom Structures and Algorithms
Volume64
Issue number1
DOIs
Publication statusPublished - Jan 2024
Externally publishedYes

Keywords

  • expander graphs
  • perfect matchings
  • random matchings

Cite this