An old approach to the giant component problem

DOI10.1016/J.JCTB.2015.03.002MaRDI QIDQ2347852zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Oliver Riordan

Publication date 10 June 2015

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

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

zbMATH Keywords

configuration modelgiant componentrandom graphssprinkling

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: In 1998, Molloy and Reed showed that, under suitable conditions, if a sequence of degree sequences converges to a probability distribution $D$, then the size of the largest component in corresponding $n$-vertex random graph is asymptotically $ho(D)n$, where $ho(D)$ is a constant defined by the solution to certain equations that can be interpreted as the survival probability of a branching process associated to $D$. There have been a number of papers strengthening this result in various ways; here we prove a strong form of the result (with exponential bounds on the probability of large deviations) under minimal conditions.

Recommendations

• A new approach to the giant component problem
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Giant components in random graphs
• A general critical condition for the emergence of a giant component in random graphs with given degrees
• 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 new approach to the giant component problem
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Edge percolation on a random regular graph of low degree
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• On percolation in random graphs with given vertex degrees
• Percolation on sparse random graphs with given degree sequence
• The asymptotic number of labeled graphs with given degree sequences
• The Critical Phase for Random Graphs with a Given Degree Sequence
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• The phase transition in inhomogeneous random graphs
• The phase transition in the configuration model
• The scaling window for a random graph with a given degree sequence
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Thek-Core and Branching Processes

Cited in

(34)

• Mesoscopic scales in hierarchical configuration models
• A simple branching process approach to the phase transition in \(G_{n,p}\)
• Epidemic spreading and equilibrium social distancing in heterogeneous networks
• Depth first exploration of a configuration model
• Chase-escape on the configuration model
• The Volume of the Giant Component of a Random Graph with Given Expected Degrees
• Giant component in random multipartite graphs with given degree sequences
• A new approach to the giant component problem
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Critical percolation on random regular graphs
• Maximizing the size of the giant
• Percolation on random graphs with a fixed degree sequence
• A Dynamic Contagion Risk Model with Recovery Features
• Random graphs with given vertex degrees and switchings
• Asymptotic normality in random graphs with given vertex degrees
• Component structure of the configuration model: barely supercritical case
• The probability that a random multigraph is simple. II
• On the method of typical bounded differences
• On local weak limit and subgraph counts for sparse random graphs
• Phase transition in random intersection graphs with communities
• Contagion risks and security investment in directed networks
• Locality of random digraphs on expanders
• Largest component of subcritical random graphs with given degree sequence
• Discursive voter models on the supercritical scale-free network
• Percolation on dense random graphs with given degrees
• Connectivity of random graphs after centrality-based vertex removal
• How to determine if a random graph with a fixed degree sequence has a giant component
• Universal `winner-takes-it-all' phenomenon in scale-free random graphs
• Local limit of the random degree constrained process
• Components, large and small, are as they should be. II: Supercritical percolation on regular graphs of constant degree
• Exact enumeration of graphs and bipartite graphs with degree constraints (extended abstract)
• Dynamic random intersection graph: dynamic local convergence and giant structure
• Counting triangles in power-law uniform random graphs
• The largest component in a subcritical random graph with a power law degree distribution

This page was built for publication: An old approach to the giant component problem

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