An elementary approach to component sizes in critical random graphs

DOI10.1017/JPR.2022.13MaRDI QIDQ5049906zbMATH OpenOpenAlexFDO

Authors Umberto De Ambroggio

Publication date 14 November 2022

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

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

zbMATH Keywords

ballot theoremrandom walk

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Combinatorial probability (60C05) Sums of independent random variables; random walks (60G50)

Abstract: In this article we introduce a simple tool to derive polynomial upper bounds for the probability of observing unusually large maximal components in some models of random graphs when considered at criticality. Specifically, we apply our method to a model of random intersection graph, a random graph obtained through $p$-bond percolation on a general $d$-regular graph, and a model of inhomogeneous random graph.

Recommendations

• The critical random graph, with martingales
• The largest component in critical random intersection graphs
• Size of the largest component in a critical graph
• On the largest component of the random graph at a nearcritical stage
• The probability of unusually large components in the near-critical Erdős-Rényi graph

Cites work

• A note on the component structure in random intersection graphs with tunable clustering
• Asymptotic equivalence and contiguity of some random graphs
• Ballot theorems, old and new
• Component evolution in random intersection graphs
• Connected components in random graphs with given expected degree sequences
• Critical behavior in inhomogeneous random graphs
• Critical percolation on random regular graphs
• Critical percolation on random regular graphs
• Evolution of a modified binomial random graph by agglomeration
• Inhomogeneous random graphs, isolated vertices, and Poisson approximation
• On a conditionally Poissonian graph process
• On the largest component of the random graph at a nearcritical stage
• Random graphs.
• RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING
• The Average Distance in a Random Graph with Given Expected Degrees
• The critical random graph, with martingales
• The Hitting Time Theorem Revisited
• The phase transition in inhomogeneous random graphs
• The phase transition in random graphs: a simple proof
• The probability of unusually large components in the near-critical Erdős-Rényi graph
• The Structure of a Random Graph at the Point of the Phase Transition
• The vertex degree distribution of random intersection graphs
• The Volume of the Giant Component of a Random Graph with Given Expected Degrees

Cited in

(10)

• The largest component in critical random intersection graphs
• Size of the largest component in a critical graph
• The Maximum Block Size of Critical Random Graphs
• The component sizes of a critical random graph with given degree sequence
• Expected Maximum Block Size in Critical Random Graphs
• Unusually large components in near-critical Erdős–Rényi graphs via ballot theorems
• The probability of unusually large components for critical percolation on random d-regular graphs
• Upper bounds for the largest component in critical inhomogeneous random graphs
• A simple path to component sizes in critical random graphs
• Finite size scaling for the core of large random hypergraphs

This page was built for publication: An elementary approach to component sizes in critical random graphs

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