Reducts of the random graph

Extract

Let Γ be the unique (up to isomorphism) countable graph with the following property: (*) Given any two finite disjoint subsets U and V of Γ, there exists a vertex z ∈ Γ joined to every vertex in U and to none in V.

Thus Γ is the countable, universal, homogeneous graph; also known as the random graph. In this paper, we shall study the reducts of Γ Here a reduct of Γ is defined to be a permutation group (G, Γ) such that:

(i) Aut(Γ) ≤ G; and

(ii) G is a closed subgroup of Sym(Γ).

Equivalently, there exists a structure for some language L such that:

(iii) has universe Γ;

(iv) for each R ∈ L, is definable without parameters in Γ; and

(v) G = Aut().