nLab
countable random graph

Contents

Idea

The countable random graph, also known as the Rado graph, is the “generic finite graph”: it contains every finite graph as an induced subgraph, models the almost-sure first-order theory of the class of finite graphs, and is axiomatized by the extension property: given any two finite subsets of vertices, there exists a vertex not in either subset which is connected to all the points in one subset and disconnected from the other.

Definition

The usual probabilistic construction is given by taking a countably infinite set of vertices and percolating the edges: for any pair of vertices, connect them with probability 12\frac{1}{2}; almost surely the end result will be the countable random graph, which is unique up to isomorphism.

Remarks

  • The extension property implies that every formula in the random graph has infinite Vapnik–Chervonenkis dimension?.

  • Here is an example of a way that the automorphisms of a first-order structure are not generally captured by its theory: a finite graph will almost surely have no nontrival automorphisms while the countable random graph is ω\omega-categorical and thus has infinitely many nontrivial automorphisms.

References

Last revised on May 19, 2017 at 03:13:26. See the history of this page for a list of all contributions to it.