Random matchings in regular graphs

DOI10.1007/PL00009817MaRDI QIDQ1280305zbMATH OpenFDO

Publication date 14 March 1999

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00009817

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Review text

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})\).

Recommendations

Cited in

(39)

This page was built for publication: Random matchings in regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1280305)