Random perfect matchings in regular graphs

DOI10.1002/RSA.21172MaRDI QIDQ6144573zbMATH OpenOpenAlexFDO

Authors Bertille Granet, Felix Joos

Publication date 5 January 2024

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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.

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

Cites work

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

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)