The number of perfect matchings, and the nesting properties, of random regular graphs

2021/04/24 by Pu Gao, Gao, Pu · 3 citations
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2104.11850

openalex publication_date 2021/04/24 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

Abstract

We prove that the number of perfect matchings in \mathcal G(n,d) is asymptotically normal when n is even, d→∞ as n→∞, and d=O(n^1/7/log² n). This is the first distributional result of spanning subgraphs of \mathcal G(n,d) when d→∞. Moreover, we prove that \mathcal G(n,d-1) and \mathcal G(n,d) can be coupled so that \mathcal G(n,d-1) is a subgraph of \mathcal G(n,d) with high probability when d→∞ and d=o(n^1/3). Further, if d=Ω(log⁷ n), d=O(n^1/7/log²n), and d≤ d'≤ n-1 then \mathcal G(n,d) and \mathcal G(n,d') can be coupled so that asymptotically almost surely \mathcal G(n,d) is a subgraph of \mathcal G(n,d').

Cited by

• Sandwiching between random regular graphs and Erdős-Rényi graphs: configuration model and unions of perfect matchings
• Sums along the edges of bounded degree graphs
• Monotonicity and decompositions of random regular graphs

Related

• Monotonicity and decompositions of random regular graphs
• Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs
• A transition of limiting distributions of large matchings in random graphs
• On random irregular subgraphs
• Sandwiching random regular graphs between binomial random graphs