The scaling window for a random graph with a given degree sequence

DOI10.1002/RSA.20394MaRDI QIDQ2909244zbMATH OpenOpenAlexFDO

Authors Hamed Hatami, Michael Molloy

Publication date 30 August 2012

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

double--jump threshold

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07)

Abstract: We consider a random graph on a given degree sequence $calD$, satisfying certain conditions. We focus on two parameters $Q=Q(calD),R=R(calD)$. Molloy and Reed proved that Q=0 is the threshold for the random graph to have a giant component. We prove that if $|Q|=O(n^{-1/3}{R}^{2/3})$ then, with high probability, the size of the largest component of the random graph will be of order $Theta(n^{2/3}{R}^{-1/3})$. If $|Q|$ is asymptotically larger than $n^{-1/3}{R}^{2/3}$ then the size of the largest component is asymptotically smaller or larger than $n^{2/3}{R}^{-1/3}$. Thus, we establish that the scaling window is $|Q|=O(n^{-1/3}{R}^{2/3})$.

Recommendations

• scientific article; zbMATH DE number 6297796
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• How to determine if a random graph with a fixed degree sequence has a giant component
• A new approach to the giant component problem
• A critical point for random graphs with a given degree sequence

Cites work

• A critical point for random graphs with a given degree sequence
• A general critical condition for the emergence of a giant component in random graphs with given degrees
• A new approach to the giant component problem
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A random graph model for massive graphs
• Component behavior near the critical point of the random graph process
• Component sizes of the random graph outside the scaling window
• Concentration Inequalities and Martingale Inequalities: A Survey
• Logarithmic combinatorial structures: A probabilistic approach
• Novel scaling limits for critical inhomogeneous random graphs
• Scaling limits for critical inhomogeneous random graphs with finite third moments
• The Critical Phase for Random Graphs with a Given Degree Sequence
• The Evolution of Random Graphs
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• The Structure of a Random Graph at the Point of the Phase Transition
• The asymptotic number of labeled graphs with given degree sequences
• The critical random graph, with martingales
• The phase transition in inhomogeneous random graphs
• The probability that a random multigraph is simple
• The transitive closure of a random digraph

Cited in

(23)

• Random graphs with a fixed maximum degree
• Tail bounds for the height and width of a random tree with a given degree sequence
• Universality for critical heavy-tailed network models: metric structure of maximal components
• Novel scaling limits for critical inhomogeneous random graphs
• Component structure of the configuration model: barely supercritical case
• Critical window for the vacant set left by random walk on the configuration model
• SIR epidemics on random graphs with a fixed degree sequence
• Percolation on complex networks: theory and application
• Depth first exploration of a configuration model
• Upper bounds for the largest component in critical inhomogeneous random graphs
• An old approach to the giant component problem
• Bipartite and directed scale-free complex networks arising from zeta functions
• Percolation on random graphs with a fixed degree sequence
• scientific article; zbMATH DE number 6297796 (Why is no real title available?)
• Phase transition for the vacant set left by random walk on the giant component of a random graph
• The critical window in random digraphs
• The probability of unusually large components for critical percolation on random \(d\)-regular graphs
• Largest component of subcritical random graphs with given degree sequence
• Percolation on dense random graphs with given degrees
• Scale-free percolation
• Random graphs with given vertex degrees and switchings
• How to determine if a random graph with a fixed degree sequence has a giant component
• Continuum limit of critical inhomogeneous random graphs

This page was built for publication: The scaling window for a random graph with a given degree sequence

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