A transition of limiting distributions of large matchings in random graphs

DOI10.1016/J.JCTB.2015.07.001MaRDI QIDQ895995zbMATH OpenOpenAlexFDO

Authors Pu Gao, Cristiane M. Sato

Publication date 11 December 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.5009

zbMATH Keywords

distributionrandom graphsmatchings

Mathematics Subject Classification ID

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

Abstract: We study the asymptotic distribution of the number of matchings of size $ell=ell(n)$ in $G(n,p)$ for a wide range of $p=p(n)in(0,1)$ and for every $1leelllelfloorn/2floor$. We prove that this distribution changes from normal to log-normal as $ell$ increases, and we determine the critical value of $ell$, as a function of $n$ and $p$, at which the transition of the limiting distribution occurs.

Recommendations

• A normal law for matchings
• Largest planar matching in random bipartite graphs
• Random matchings in regular graphs
• The Structure of a Random Graph at the Point of the Phase Transition
• A local limit theorem for the critical random graph

Cites work

• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 1335045 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Distributions of sparse spanning subgraphs in random graphs
• Induced subgraphs in sparse random graphs with given degree sequences
• Matchings in random biregular bipartite graphs
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Random graphs.
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
• The asymptotic distribution of short cycles in random regular graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Uniform generation of random regular graphs of moderate degree
• Weighted enumeration of spanning subgraphs in locally tree-like graphs
• When are small subgraphs of a random graph normally distributed?

Cited in

(4)

• The number of perfect matchings, and the nesting properties, of random regular graphs
• Triangles and subgraph probabilities in random regular graphs
• Limiting distribution of maximal crossing and nesting of Poissonized random matchings
• Bivariate fluctuations for the number of arithmetic progressions in random sets

This page was built for publication: A transition of limiting distributions of large matchings in random graphs

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