A transition of limiting distributions of large matchings in random graphs

DOI10.1016/J.JCTB.2015.07.001zbMATH Open1327.05303arXiv1305.5009OpenAlexW1658178599MaRDI QIDQ895995FDOQ895995

Authors: Pu Gao, Cristiane M. Sato 

Publication date: 11 December 2015

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• The number of perfect matchings, and the nesting properties, of 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
• Triangles and subgraph probabilities in random regular graphs

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)