Random matchings in regular graphs
type: Item
instance of: scholarly article
title: Random matchings in regular graphs
zbMATH Open document ID: 0910.05050
DOI: 10.1007/PL00009817
author: Han Kim Jeong
author: J. Kahn
published in: Combinatorica
publication date: 1999-03-14T00:00:00Z
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})\).
reviewed by: András Pluhár
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1261227
zbMATH Keywords: \(d\)-regular graphs
zbMATH Keywords: random matchings
MaRDI profile type: Publication
Recommended article: The number of matchings in random graphs
Recommended article: Matchings in random biregular bipartite graphs
Recommended article: The number of matchings in random regular graphs and bipartite graphs
Recommended article: Random-link matching problems on random regular graphs
Recommended article: Random matching problems on the complete graph
Recommended article: Combinatorial Geometry and Graph Theory
Recommended article: Maximum matchings in a class of random graphs
Recommended article: Perfect matchings in random intersection graphs
Recommended article: On the number of matchings in regular graphs
Recommended article: Perfect matchings in random subgraphs of regular bipartite graphs
description: scientific article; zbMATH DE number 1261227