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

DOI10.1002/RSA.20394zbMATH Open1247.05218arXiv0907.4211OpenAlexW2094948820MaRDI QIDQ2909244FDOQ2909244

Authors: Hamed Hatami, Michael Molloy 

Publication date: 30 August 2012

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

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

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

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

zbMATH Keywords

double--jump threshold

Mathematics Subject Classification ID

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

Cites Work

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

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
• Upper bounds for the largest component in critical inhomogeneous random graphs
• Depth first exploration of a configuration model
• 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
• Title not available (Why is that?)
• 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
• Random graphs with given vertex degrees and switchings
• Scale-free percolation
• 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)