An elementary approach to component sizes in critical random graphs

2021/01/17 by Umberto De Ambroggio, De Ambroggio, Umberto
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2101.06625

openalex publication_date 2021/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Upper bounds for the largest components in critical inhomogeneous random graphs
• Small maximal clusters are very unlikely in critical random graphs
• A simple path to component sizes in critical random graphs
• Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdős-Rényi random graph
• Critical scaling limits of the random intersection graph