Random matchings in regular graphs (Q1280305): Difference between revisions

For a simple \(d\)-regular graph \(G\), let \(M\) be chosen uniformly at random from the set of all matchings of \(G\), and let \(p(\bar x)\) be the probability that \(M\) does not cover \(x\). Furthermore, let \(\xi=| M| \), i.e. a random variable whose value is the size of the random matching \(M\), \(\mu= E\xi\) and \(\sigma= \text{Var}(\xi)\). The authors show that for large \(d\) the values of \(p(\bar x)\), \(\mu\) and \(\sigma\) are determined to within small tolerances by \(d\) and \(| V(G)| \). Namely, \(p(\bar x) \sim d^{-1/2}\), \(| V(G)| -2 \mu \sim | V(G)| /\sqrt{d}\), and \(\sigma^2 \sim | V(G)| /(4\sqrt{d})\).