Random perfect matchings in regular graphs

DOI10.1002/RSA.21172zbMATH Open1529.05130arXiv2301.10131OpenAlexW4384133444MaRDI QIDQ6144573FDOQ6144573

Authors: Bertille Granet, Felix Joos 

Publication date: 5 January 2024

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We prove that in all regular robust expanders $G$ every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|McapE(N)|$ 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.

Full work available at URL: https://arxiv.org/abs/2301.10131

Recommendations

• Random matchings in regular graphs
• The number of perfect matchings, and the nesting properties, of random regular graphs
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma

zbMATH Keywords

perfect matchingsexpander graphsrandom matchings

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Expander graphs (05C48)

Cites Work

• The robust component structure of dense regular graphs and applications
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Random matchings in regular graphs
• Cycle partitions of regular graphs
• Perfect matchings in \(\varepsilon\)-regular graphs
• A blow-up lemma for approximate decompositions
• Fractional cycle decompositions in hypergraphs

Cited In (1)

• Counting deranged matchings

This page was built for publication: Random perfect matchings in regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6144573)