The random graph and its

relations

Peter J. Cameron School of Mathematical Sciences Queen Mary and Westfield College

London E1 4NS

Set Theory and its Neighbours

De Morgan House, London 8 April 1999

The random graph

Theorem 1 (Erdős and Rényi) There is a countable graph R with the property that a random countable graph (edges chosen independently with probability \frac{1}{2}) is almost surely isomorphic to R.

The graph R has the properties that

• it is universal: any finite (or countable) graph is embeddable as an induced subgraph of R;

• it is homogeneous: any isomorphism between finite induced subgraphs of R extends to an automorphism of R.

Universal homogeneous structures

Theorem 2 (Fraïssé) R is the unique countable universal homogeneous graph.

There are many other examples to which Fraïssé’s theorem or variants apply:

• the random tournament, digraph, hypergraph, etc.;

• the universal total order ℚ (Cantor), partial order, etc.;

• the universal triangle-free graph (Henson), N-free graph (Covington), locally transitive tournament (Lachlan), two-graph, etc.;

• the universal locally finite group (Hall), Steiner triple system (Thomas), etc.

More generally …

There is a more general and powerful version due to Hrushovski. It constructs pseudoplanes, distance-transitive graphs, and examples related to sparse random graphs (among other things).

See the survey article by Wagner in Kaye and Macpherson, Automorphisms of First-Order Structures.

Constructions of R

Construction 1. Take any countable model of ZF, and join x to y if x ∈ y or y ∈ x.

In fact we don’t need all of ZF, only the null set, pairing, union, and foundation axioms. So the standard model of finite set theory (the set ℕ, with x ∈ y if the xth binary digit of y is 1) gives an explicit construction (Rado).

Construction 2. Let ℙ_{1} be the set of primes congruent to 1 mod 4. Join p to q if p is a quadratic residue mod q.

If we use instead ℙ_{−1}, the set of primes congruent to −1 mod 4, we obtain the random tournament.

First-order graph properties

The graph R ‘controls’ first-order properties of finite random graphs.

Theorem 3 (Glebskii et al.) A first-order sentence in the language of graphs holds in almost all finite graphs if and only if it holds in R.

In particular, there is a zero-one law for first-order sentences.

Of course, most interesting graph properties are not first-order!

Pigeonhole property

A structure X has the pigeonhole property if, whenever X is partitioned into two parts, one of the parts is isomorphic to X.

Theorem 4 The countable graphs with the pigeonhole property are the complete graph, the null graph, and the random graph.

Theorem 5 The countable tournaments with the pigeonhole property are the random tournament, ordinal powers of ω, and their converses.

Reducts

A subgroup of the symmetric group is closed in the topology of pointwise convergence if and only if it is the automorphism group of a first-order structure (which can be taken to be a homogeneous relational structure).

Theorem 6 (Thomas) There are five closed subgroups of Sym (R) containing Aut(R), viz. Aut(R), the group of automorphisms and anti-automorphisms of R, the group of switching-automorphisms of R, the group of switching-automorphisms and anti-automorphisms of R, and Sym (R).

Similar results are known in a few other cases, e.g. ℚ (as ordered set), random hypergraphs.

Reconstruction

The perfect graph theorem (Lóvasz) asserts that the complement of a perfect graph is perfect.

The P_{4}-structure of a graph is the collection of subsets which induce paths on four vertices. The semi-strong perfect graph theorem (Reed) asserts that a graph which has the same P_{4}-structure as a perfect graph is perfect.

Cameron and Martins proved that for almost all finite graphs G, the only graphs with the same P_{4}-structure as G are G and its complement. The analogous statement is true with any finite collection of finite graphs in place of {P_{4}}.

The proof uses Theorems 6 and 3, and some elementary model theory.

B-groups

A B-group is a group X with the property that any primitive permutation group G which contains the right regular action of X is doubly transitive.

Theorem 7 For almost all n, every group of order n is a B-group.

The proof uses the Classification of Finite Simple Groups.

By contrast, no countable B-groups are currently known.

Countable non-B-groups

A square-root set in a group X is a set of the form

√a = {x : x^{2} = a}.

It is non-principal if a ≠ 1.

Theorem 8 (Cameron and Johnson) Suppose that the countable group X is not the union of finitely many translates of non-principal square-root sets. Then a random Cayley graph for X is isomorphic to R. Hence X is not a B-group.

Countable non-B-groups

Theorem 9 There is no countable abelian B-group.

Proof. Let X_{2} = {x ∈ X : x^{2} = 1}. If |X : X_{2}| is infinite, then Theorem 8 applies. Otherwise, X has finite exponent and so X = Y × Z with Y and Z infinite; then X is contained in the primitive group Sym (ℕ) ≀ Sym (2) (with the product action).

Theorem 10 A countable simple group with more than two conjugacy classes is not a B-group.

Proof. Consider {x ↦ a^{−1}xb : a, b ∈ X}.

Problems on B-groups

• Can one use other countable homogeneous structures to find further non-B-groups? What about Hrushovski’s method?

• Are there any countable B-groups?

• Is the hypothesis of Theorem 8 necessary?

References

P. J. Cameron, The random graph, pp. 331–351 in The Mathematics of Paul Erdős, (ed. J. Nešetřil and R. L. Graham), Springer, Berlin, 1996.

P. J. Cameron. and K. W. Johnson, An essay on countable B-groups, Math. Proc. Cambridge Philos. Soc. 102 (1987), 223–232.

P. J. Cameron and C. Martins, A theorem on reconstructing random graphs, Combinatorics, Probability and Computing 2 (1993), 1–9.

J. Covington, A universal structure for N-free graphs, Proc. London Math. Soc. (3) 58 (1989), 1–16.

P. Erdős and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963), 295–315.

R. Fraïssé, Sur certains relations qui généralisent l’ordre des nombres rationnels, C. R. Acad. Sci. Paris 237 (1953), 540–542.

Y. V. Glebskii, D. I. Kogan, M. I. Liogon’kii and V. A. Talanov, Range and degree of realizability of formulas in the restricted predicate calculus, Kibernetika 2 (1969), 17–28.

P. Hall, Some constructions for locally finite groups, J. London Math. Soc. 34 (1959), 305–319.

C. W. Henson, A family of countable homogeneous graphs, Pacific J. Math. 38 (1971), 69–83.

E. Hrushovski, A new strongly minimal set, Ann. Pure Appl. Logic 62 (1993), 147–166.

A. H. Lachlan, Countable homogeneous tournaments, Trans. Amer. Math. Soc. 284 (1984), 431–461.

L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972), 253–267.

R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340.

B. Reed, A semi-strong perfect graph theorem, J. Combinatorial Theory (B) 43 (1987), 223–240.

S. R. Thomas, Reducts of the random graph, J. Symbolic Logic 56 (1991), 176–181.

F. O. Wagner, Relational structures and dimensions, pp. 153–180 in Automorphisms of First-Order Structures (ed. R. W. Kaye and H. D. Macpherson), Oxford University Press, Oxford, 1994.