Largest component of subcritical random graphs with given degree sequence

DOI10.1214/23-EJP921MaRDI QIDQ6164933zbMATH OpenOpenAlexFDO

Authors Matthew Coulson, Guillem Perarnau

Publication date 4 July 2023

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.11780, https://projecteuclid.org/journals/electronic-journal-of-probability/volume-28/issue-none/Largest-component-of-subcritical-random-graphs-with-given-degree-sequence/10.1214/23-EJP921.full

zbMATH Keywords

component structureconfiguration modellargest componentlocal limit theoremsrandom graph with given degree sequence

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

Abstract: We study the size of the largest component of two models of random graphs with prescribed degree sequence, the configuration model (CM) and the uniform model (UM), in the (barely) subcritical regime. For the CM, we give upper bounds that are asymptotically tight for certain degree sequences. These bounds hold under mild conditions on the sequence and improve previous results of Hatami and Molloy on the barely subcritical regime. For the UM, we give weaker upper bounds that are tight up to logarithmic terms but require no assumptions on the degree sequence. In particular, the latter result applies to degree sequences with infinite variance in the subcritical regime.

Recommendations

• On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase
• The largest component in a subcritical random graph with a power law degree distribution
• The Largest Component in Subcritical Inhomogeneous Random Graphs
• The largest component in a random subgraph of the \(n\)-cycle
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• On the largest component of the random graph at a nearcritical stage
• The component sizes of a critical random graph with given degree sequence
• On the largest component of subcritical random hyperbolic graphs
• The largest component in critical random intersection graphs

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
• An old approach to the giant component problem
• Component structure of the configuration model: barely supercritical case
• Critical percolation on random regular graphs
• Critical window for the configuration model: finite third moment degrees
• Heavy-tailed configuration models at criticality
• How to determine if a random graph with a fixed degree sequence has a giant component
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3504208 (Why is no real title available?)
• Introduction to Random Graphs
• Local Limit Theorems for Distributions of Sums of Independent Random Vectors
• Local Limit Theorems for Lattice Random Variables
• On tail probabilities for martingales
• On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase
• One-sided local large deviation and renewal theorems in the case of infinite mean
• Probability
• Random graph dynamics
• The component sizes of a critical random graph with given degree sequence
• The largest component in a subcritical random graph with a power law degree distribution
• The phase transition in the configuration model
• The probability that a random multigraph is simple
• The scaling window for a random graph with a given degree sequence

Cited in

(8)

• On the largest component of subcritical random hyperbolic graphs
• The Largest Component in Subcritical Inhomogeneous Random Graphs
• The component sizes of a critical random graph with given degree sequence
• Central limit theorem for statistics of subcritical configuration models
• Component structure of the configuration model: barely supercritical case
• How to determine if a random graph with a fixed degree sequence has a giant component
• On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase
• The largest component in a subcritical random graph with a power law degree distribution

This page was built for publication: Largest component of subcritical random graphs with given degree sequence

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