Erdős–Rényi random graphs

Erdős–Rényi random graphs
Name	Erdős–Rényi random graphs
Notation	G(n,p), G(n,m)
Introduced	1959–1960
Introduced by	Paul Erdős; Alfréd Rényi
Field	Graph theory; Probability theory
Related	Random graph theory; Percolation theory; Combinatorics

Erdős–Rényi random graphs are fundamental probabilistic models in Graph theory and Probability theory introduced by Paul Erdős and Alfréd Rényi in 1959–1960. They formalize ensembles of graphs on a fixed vertex set with edges included independently with some probability or uniformly among graphs with a fixed number of edges, providing tractable settings to study typical structural properties and thresholds. The models underpin developments in Combinatorics, Statistical mechanics, and network science linked to work by Béla Bollobás, Fan Chung, and László Lovász.

Definition and models

Two classic variants define the Erdős–Rényi family. The G(n,p) model fixes an ordered vertex set of size n and includes each potential edge independently with probability p; this construction relates to binomial sampling used in Andrey Kolmogorov's probabilistic foundations and to sampling frameworks in Ronald Fisher's experimental design. The G(n,m) model selects uniformly at random from all graphs with n vertices and exactly m edges, a combinatorial counterpart studied by Paul Erdős alongside Alfréd Rényi and later by Nick Wormald and Béla Bollobás. Variants and couplings between G(n,p) and G(n,m) connect to work by Erdős on extremal graph theory and to the probabilistic method developed further in texts by Joel Spencer and Noga Alon.

Basic properties and distributions

Edge counts in G(n,p) follow a Binomial distribution determined by n(n−1)/2 trials; degree sequences concentrate by forms of the Chernoff bound and the Central limit theorem employed in analyses by Erdős, Rényi, and later refined by Alberto Frieze. Local structures—degrees, distances, and cycles—obey limiting distributions often approximated by Poisson distribution in sparse regimes, a perspective used in probabilistic combinatorics by Béla Bollobás and Svante Janson. Global invariants such as the number of triangles, clustering coefficients, and chromatic number admit asymptotic distributions proven using martingale inequalities attributed to Paul Erdős and tools popularized by Joel Spencer and Van Vu.

Connectivity and component structure

Component sizes and connectivity thresholds in Erdős–Rényi graphs were first characterized by Erdős and Rényi: for p below critical values the graph fragments into small components, while above critical p a giant component emerges, a phenomenon related to the Giant component concept studied in Béla Bollobás's survey literature. The precise threshold for connectivity ties to logarithmic scalings and to methods introduced by Paul Erdős, with refinements by Pál Erdős's collaborators and rigorous limit theorems by Svante Janson and Oliver Riordan. Results on the structure of finite components invoke branching process approximations developed by T. E. Harris and applied in works by David Aldous and Jean-Pierre Serre.

Phase transitions and threshold functions

Erdős–Rényi graphs exemplify sharp phase transitions: monotone graph properties often change from improbable to almost certain across narrow windows of p. The formalization of threshold functions owes to early contributions by Erdős and Rényi and was systematized in the probabilistic method literature by Noga Alon and Joel Spencer. Critical phenomena connect to universality classes studied in Statistical mechanics and to percolation thresholds investigated by Harry Kesten and Geoffrey Grimmett. Precise threshold locations for properties such as appearance of a Hamiltonian cycle, connectivity, or k-core emergence were settled by work of Béla Bollobás, Kurt Gödel’s contemporaries in combinatorics, and later by Michael Krivelevich and Eyal Lubetzky.

Subgraph counts and appearance of motifs

Counting small subgraphs (cycles, cliques, paths) in G(n,p) yields limit laws and concentration results central to motif detection in networks. Asymptotic counts for fixed subgraphs derive from linearity of expectation and variance estimates refined by Joel Spencer, Svante Janson, and Béla Bollobás; the Poisson paradigm describes counts in sparse regimes, while normal approximations apply in dense regimes via the Method of moments used in probabilistic combinatorics by Noga Alon. Thresholds for the appearance of given subgraphs relate to Turán-type extremal thresholds explored by Pál Turán and extended by Paul Erdős and Miklós Simonovits.

Graph limits, scaling limits, and random graph processes

Scaling limits of G(n,p) near critical windows connect to continuum random trees and to the Aldous continuum limit developed by David Aldous and extended by Joan van den Berg and Oliver Riordan. Graph limit theory for dense sequences, as formalized by László Lovász, places Erdős–Rényi sequences within the graphon framework and relates to exchangeability results by Oded Schramm and Donald Knuth's combinatorial foundations. Dynamic constructions, such as random graph processes adding edges sequentially, connect to Achlioptas processes studied by Dimitris Achlioptas and to percolation dynamics analyzed by Harry Kesten.

Applications and variations of the Erdős–Rényi model

The simplicity of Erdős–Rényi models makes them benchmarks in network science, serving as null models in studies by Duncan Watts, Mark Newman, and Albert-László Barabási contrasting random graphs with small-world and scale-free networks. Variations include inhomogeneous random graphs studied by Béla Bollobás and Svante Janson, geometric random graphs linked to problems addressed by Paul Erdős and Pál Turán, and directed or bipartite versions analyzed by Joel Spencer and Noga Alon. Applications span randomized algorithms in theoretical computer science influenced by Donald Knuth and Alan Turing, probabilistic combinatorics used in communication networks explored by Claude Shannon, and models of epidemic spread related to work by Anderson Gray McKendrick and William Ogilvy Kermack.

Category:Random graphs