Random Graph

Origin. Wilhelm Ackermann's "Die Widerspruchsfreiheit der allgemeinen Mengenlehre" (1937) constructed the graph first, on the hereditarily finite sets — the same paper that codes V_ω into ℕ (see Hereditarily Finite Set Theory.md). Paul Erdős and Alfréd Rényi, "Asymmetric graphs" (Acta Mathematica Academiae Scientiarum Hungaricae 14, 1963), proved that almost all finite graphs are rigid and, as the contrast case, that the countable random graph almost surely has infinitely many automorphisms — an argument that also makes it one graph up to isomorphism, a uniqueness the paper leaves implicit. Richard Rado, "Universal graphs and universal functions" (Acta Arithmetica 9, 1964), gave the explicit universal graph on ℕ. Haim Gaifman (1964) proved the extension axioms complete; Ronald Fagin, "Probabilities on finite models" (Journal of Symbolic Logic, 1976), tied the theory to the asymptotics of finite graphs.

Models. One countable graph, reachable from three directions that have no reason to agree: sample countably many vertices with independent coin-flip edges and with probability 1 the result is this graph; take the Fraïssé limit of all finite graphs and it is this graph; take the almost-sure first-order theory of large finite graphs and its unique countable model is this graph. Randomness, genericity, and asymptotic truth name the same object, R — the Rado graph. Beside its Structure siblings it is the relational case: where ACF and RCF decide field questions, Th(R) decides everything expressible about adjacency, and does so from the extension property alone.

Formalism.

Language: E, one binary relation; axioms making it irreflexive and symmetric.

Extension axioms: E_{m,n}: for all distinct x₁ … x_m, y₁ … y_n there is z, distinct from all of them, adjacent to every xᵢ and to no yⱼ. The theory of the random graph = graph axioms + all E_{m,n}.

Uniqueness (back-and-forth): any two countable graphs satisfying every E_{m,n} are isomorphic, by extending finite partial isomorphisms one vertex at a time; so the theory is ℵ₀-categorical, hence complete (Gaifman 1964), hence decidable. Erdős–Rényi: a countable graph with independent edges of probability ½ (any fixed probability strictly between 0 and 1) satisfies every E_{m,n} almost surely.

Quantifier elimination: R is ultrahomogeneous in a finite relational language, so Th(R) eliminates quantifiers in the pure graph language — every formula is equivalent to a Boolean combination of adjacencies and equalities.

Not finitely axiomatizable: each finite fragment of the theory holds in some finite graph (large Paley graphs satisfy all E_{m,n} with m + n bounded), while the whole theory has no finite models.

Explicit constructions: Rado: vertices ℕ; for x < y, join x and y iff bit x of the binary expansion of y is 1. Ackermann: vertices V_ω; join u and v iff u ∈ v or v ∈ u — membership, symmetrized.

Fraïssé limit: R is the Fraïssé limit of the class of all finite graphs, which has HP, JEP, and AP; ultrahomogeneity and universality follow (see Fraisse Limits.md).

Zero-one law: every first-order sentence of graphs is almost surely true or almost surely false in large finite graphs, and the almost-sure theory is exactly Th(R) (Glebskii–Kogan–Liogon'kii–Talanov 1969; Fagin 1976) — first-order logic cannot tell large finite graphs apart from the random graph (see Zero-One Laws.md).

Robustness: deleting finitely many vertices or edges, adding finitely many edges, and complementation all preserve the extension property, so all return R.

Partition property: for every partition of the vertices into two parts, at least one part induces a copy of R.

Classification-theoretic position: unstable, with the independence property — the extension axioms realize every adjacency pattern over every finite set, which is the independence property verbatim. Simple, of SU-rank 1, and therefore without the strict order property: the standard example of a simple unstable theory.

Symbols.

Metatheory. Complete, ℵ₀-categorical, decidable, with quantifier elimination in the pure graph language — the extension axioms do all of it, through back-and-forth and Ryll-Nardzewski. Deciding whether a sentence holds is PSPACE-complete, so the decidability is, as usual in this division, not feasibility. The stability-theoretic facts carry the entry's weight: Th(R) is unstable with the independence property yet simple of SU-rank 1 and so without the strict order property, which separates the two sources of instability — order and independence — and exhibits independence occurring alone; it is the standard first example of a simple unstable theory, as (ℚ, <) is of the order side. The three constructions agreeing is itself the theorem to remember: Erdős–Rényi randomness, Fraïssé genericity, and the Glebskii–Fagin almost-sure theory each determine the same countable graph, so "the random graph" is a definite description.

Applies to. Finite model theory, where Th(R) is the almost-sure theory and the engine of the zero-one law. Fraïssé theory and the classification of homogeneous structures, where it is the paradigm limit. Ramsey theory of countable structures and the topological dynamics of automorphism groups. Constraint satisfaction over ω-categorical templates. Universal graphs in combinatorics, through Rado's construction.

Limitations. The theory describes no finite graph — every finite graph fails some E_{m,n} — so its asymptotic statements say nothing about any particular instance, the zero-one framing's standing caveat. It describes the dense regime only: sparse random graphs G(n, n^(−α)) have different almost-sure theories, with the limit behaviour controlled by the rationality of α (Shelah–Spencer; see Zero-One Laws.md). Uniqueness is a countable phenomenon: the back-and-forth runs along a countable enumeration, and the extension property determines no single graph of size ℵ₁. And the theory that decides everything about adjacency carries almost no structure to use — SU-rank 1 with trivial geometry, no definable group, no definable order — so it anchors the simple unstable corner of the classification map while supporting none of the geometric model theory that runs through ACF, RCF, and DCF₀.

© 2026 Lingenic LLC