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

preprint2022arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.