Random matchings in regular graphs
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})\).
scientific article; zbMATH DE number 1261227