nLab countable random graph

model theory

Dimension, ranks, forking

• forking and dividing?

• Morley rank?

• Shelah 2-rank?

• Lascar U-rank?

• Vapnik–Chervonenkis dimension?

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 $\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.