Homogeneous Cayley objects

Peter J. Cameron

Abstract

We examine a number of countable homogeneous relational structures with the aim of deciding which countable groups can act regularly on them. Since a group X acts regularly on a graph G if and only if G is a Cayley graph for X, we will extend the terminology and say that M is a Cayley object for X if X acts regularly on M. We consider, among other things, graphs, hypergraphs, metric spaces and total orders.

1 Introduction

Let X be a group. A Cayley graph for X is a graph G with vertex set X having the property that, for all g ∈ X, right multiplication by g (the map x ↦ xg) is an automorphism of G. In other words, the image of X in the symmetric group Sym(X), under Cayley’s isomorphism, is a subgroup of the automorphism group of G.

The problem of describing all Cayley graphs for X is relatively straightforward. Let S be a subset of X having the properties

• 1 ∉ S;

• s ∈ S implies s^{−1} ∈ S.

Now define a graph Cay(X, S), on the vertex set X, by the rule that x and y are adjacent if and only if yx^{−1} ∈ S. Then Cay(X, S) is a Cayley graph for X; and every Cayley graph arises for some choice of subset S. (Note that the elements of S are the neighbours of the identity in Cay(X, S).)

The inverse problem, that of describing all groups X for which a given graph G is a Cayley graph, is less straightforward, and motivates the present paper. First note that the action of X on the vertices of a Cayley graph is regular: that is, it is transitive, and the stabiliser of a vertex is the identity. So any Cayley graph for X must be vertex-transitive. Now it is well-known (and easy to prove) that, if X is a group of automorphisms of a graph G which acts regularly on the vertex set of G, then G is a Cayley graph for X. So the groups for which a given vertex-transitive graph G is a Cayley graph are precisely those which are isomorphic to regular subgroups of Aut(G).

At this point, note that treatments of Cayley graphs in the literature may differ from the above account in two inessential ways. First, it is fairly common to let X act by left (rather than right) multiplication. Second, the definition of a Cayley graph is sometimes strengthened to include connectedness. In fact, Cay(X, S) is connected if and only if S is a generating set for X.

A Cayley graph is said to be normal if it admits both left and right multiplication by elements of X. It is easily seen that an equivalent formulation is as follows. The Cayley graph Cay(X, S) is normal if and only if S is a normal subset of X (one which is fixed by conjugation by all elements of X). (The composition of left multiplication by g^{−1} and right multiplication by g is conjugation by g.) In particular, every Cayley graph for an abelian group is normal.

In this paper, I extend the terminology to other types of objects (hypergraphs, tournaments, metric spaces and so on). Thus, an object O of any type is a Cayley object for the group X if its point set is X and right multiplication by any element of X is an automorphism of O; it is a normal Cayley object if both left and right multiplication by elements of X are automorphisms.

Part of the motivation for this paper is the search for countable B-groups. Recall that a permutation group on a set X is said to be primitive if it leaves invariant no equivalence relation except for the trivial ones (equality and the ‘universal’ relation X × X); it is doubly transitive if it leaves invariant no binary relations at all except for the trivial ones (equality, inequality, the universal relation, and the empty relation). Now the group X is a Bgroup if every primitive subgroup of Sym(X) which contains the regular representation of X is doubly transitive. The B stands for Burnside, who showed that cyclic groups of composite prime-power order are B-groups. It is now known, as a consequence of the classification of finite simple groups, that for almost all positive integers n (a set of density 1), every group of order n is a B-group. This is simply because of the paucity of primitive permutation groups. In the infinite case, there is no such paucity; and, indeed, no countable B-group is yet known.

The notion of Cayley objects is a tool for showing that various groups are not B-groups. For the homogeneous objects that we consider, it is easy to decide whether the automorphism group is primitive; and, in almost all cases, it is. Now if the object O has the property that its automorphism group is primitive but not 2-transitive, then any group for which O is a Cayley object is shown not to be a B-group. This approach was exploited for the ‘random graph’ (Rado’s graph) by Cameron and Johnson [5].

We will restrict our search to homogeneous objects. An object O is homogeneous if every isomorphism between finite subobjects of O extends to an automorphism of O. This asserts that O has the maximum possible amount of symmetry. A countable homogeneous relational structure is determined by, and can be recognised by, the class of its finite substructures; this theory, developed by Fraïssé, is briefly outlined in Section 2. Another clear account is in Cherlin [6].

The most powerful technique for constructing Cayley objects which are homogeneous is that of Baire category: we show that, under appropriate hypotheses on the group X, almost all X-invariant objects of the appropriate type (in the sense of category; that is, a residual set) are homogeneous. The method is outlined in Section 3.

The remainder of the paper treats particular examples: graphs, directed graphs, hypergraphs, metric spaces, orders, and n-tuples of orders. In some cases, we are close to a complete characterisation of the groups for which the structure in question is a Cayley object. In other cases, the analysis is much less developed, and we are content to give a few examples.

2 Homogeneous structures

The existence and uniqueness of homogeneous structures is described by Fraïssé’s Theorem [9]. We consider only relational structures, or sets carrying specified relations, though the theorem holds much more generally. The structure M is homogeneous if every isomorphism between induced substructures of M can be extended to an automorphism of M. The age Age(M) of M is the class of all finite structures which are embeddable in M as induced substructures. A class C of structures satisfies the amalgamation property if, whenever A, B_{1}, B_{2} ∈ C and f_{i} : A → B_{i} are embeddings for i = 1, 2, there exist C ∈ C and embeddings g_{i} : B_{i} → C for i = 1, 2 such that f_{1}g_{1} = f_{2}g_{2}. Contrary to the normal practice of logicians here, we permit the case where A is the empty structure. (In this case the condition is called the joint embedding property and simply asserts that any two members of C can be embedded in some member of C.)

Theorem 2.1 The class C of finite relational structures is the age of a countable relational structure M if and only if it is closed under isomorphism, closed under taking induced substructures, contains only countably many members up to isomorphism, and has the amalgamation property. Moreover, if these conditions hold, then M is unique up to isomorphism.

A class C satisfying these conditions is called a Fraïssé class, and the countable homogeneous structure M is its Fraïssé limit.

The following test will be important in the sequel for recognising countable homogeneous structures.

Theorem 2.2 The countable relational structure M is homogeneous if and only if, for all A, B ∈ Age(M) with A ⊆ B, every embedding of A into M can be extended to an embedding of B into M. It suffices to require this when |B| = |A| + 1.

This is referred to as the I-property of M, since it is very similar to injectivity in a category.

For a more detailed description of these ideas, see the account in the first chapter of Cherlin [6].

3 Residual sets

Many of our existence proofs are based on the technology of Baire category. In this section we describe the simplified form of the Baire category theorem which is required. Informally, if some object is specified by a countable sequence of choices, we try to show that an object with a given property P exists by showing that P holds for ‘almost all’ choices.

A subset of a metric space is called residual if it contains a countable intersection of open dense sets. The Baire category theorem states that a residual subset of a complete metric space is non-empty. The interpretation is that residual sets are ‘large’, much like the complements of null sets in measure spaces. For example, the intersection of countably many residual sets is residual and hence non-empty.

The complete metric spaces to which the theorem will be applied all arise from paths in rooted trees of countable height. Let T be such a tree, and let P(T) denote the set of paths of countable length starting at the root of T. We define the distance between distinct paths p and p′ to be f(n), where n is the height of the last node at which p and p′ agree, and f is any strictly decreasing function tending to zero. The metric space axioms are easily verified; indeed, the ultrametric inequality

d(p, p′′) ≤ max{d(p, p′), d(p′, p′′)}

holds. A Cauchy sequence in this metric space is a sequence of paths agreeing on longer and longer initial segments, and so has a unique limiting path. So the metric space is complete.

To understand residual sets in this space, we must first interpret the conditions of openness and denseness. An open ball consists of all paths which contain a given node. So a set S of paths is open if it has the property that, for any path p ∈ S, there is a node x on p with the property that every path containing x is in S. (Such a set is called finitely determined.) A set S is dense if it meets every open ball; that is, for any node x, there is a path in S which contains x. (Such a set is called always reachable.) In this special case, it is not difficult to prove the Baire category theorem directly.

We say that a property of a path p is generic if it holds for a residual set of paths.

4 The random graph

The result of this section appear in Cameron and Johnson [5]. It is repeated here partly for completeness, and partly as a simple introduction to the technique.

The random graph, or Rado’s graph (which will be here denoted by R) is the Fraïssé limit of the class of all finite graphs (which is clearly a Fraïssé class). It was constructed explicitly by Rado [13], and implicitly by Erdős and Rényi [8], who showed that a countable random graph (with edges chosen independently with probability \frac{1}{2}) is almost surely isomorphic to R. The Baire category analogue of this fact is that the isomorphism class of R is residual in the class of all graphs (on a given countable vertex set).

Now let X be a group. As we have seen, a Cayley graph for X has the form Cay(X, S), where S is an inverse-closed subset of X \ {1}. If X is countable, we can enumerate the inverse pairs of non-identity elements of X as {x_{1}, x_{1}^{−1}}, {x_{2}, x_{2}^{−1}}, . . .. Now the Cayley graphs are specified by paths in a binary tree: the two descendants of a node at level n correspond to including or excluding x_{n+1} and x_{n+1}^{−1} in S. So we can talk about ‘a residual set of Cayley graphs for X’.

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

\sqrt{a} = \{x ∈ X : x^{2} = a\}

for a ∈ X; it is non-principal if a ≠ 1. A translate of a square-root set has the form

(\sqrt{a})h = \{xh : x ∈ \sqrt{a}\}.

Note that left and right translates give the same sets; more precisely,

(\sqrt{a})h = h(\sqrt{h^{−1}ah}).

Theorem 4.1 Let X be a countable group which cannot be expressed as the union of a finite number of translates of non-principal square root sets and a finite set. Then the set of Cayley graphs for X which are isomorphic to R is residual.

Proof We must show that, for any finite graphs A, B with A ⊆ B and |B| = |A| + 1, and any subset C of X with |C| = |A|, the set X (A, B, C) of Cayley graphs for which

(C ≅ A) ⇒ (∃z)(C ∪ {z} ≅ B)

is open and dense. As usual, the openness is clear, since membership in this set depends only on a finite number of choices of elements of S (viz., all yx^{−1} for x, y ∈ C (or C ∪ {z}, where z is the witness). So we have to show that this set is dense.

So assume that decisions about the first n inverse pairs have been made and that, as a result of these decisions, a finite subset S_{0} of S has been chosen. We can assume that these decisions include all yx^{−1} for x, y ∈ C, so that the structure of the induced subgraph on the set C is determined. If these decisions already imply that C ≅ A̸, we are done, so suppose not. Now we require an element z which is adjacent to a given subset U of C and non-adjacent to the complementary subset V = C \ U. We must disqualify certain elements:

(a) All x for which some adjacency or non-adjacency to C is already determined.

(b) All x for which there exist u ∈ U and v ∈ V with ux^{−1} = xv^{−1}; for, whatever decisions we make, such x will be joined to both or neither of u and v.

Now there are only finitely many elements under (a), namely those of the form x_{i}c or x_{i}^{−1}c for i ≤ n: this is a finite set. For given u and v, the set disqualified in (b) is

\{x : (xv^{−1})^{2} = uv^{−1}\} = (\sqrt{uv^{−1}})v,

a translate of a non-principal square root set; and there are finitely many such sets to be excluded. Now the hypotheses of the theorem guarantee that some element z not in C is not disqualified by these rules, and we can make subsequent decisions so that z is the required witness.

Many groups satisfy the hypothesis of the theorem. For example, they hold if X has a homomorphism θ onto the infinite cyclic group, since a square-root set maps onto a single element under θ.

The hypothesis of the theorem is close to being necessary for X to have R as a Cayley graph. For, if it does so, then X cannot be a union of translates of square-root sets of the specific form (\sqrt{uv^{−1}})v for u ∈ U and v ∈ V, where U and V are disjoint finite subsets of X, together with the finite set U ∪ V. Indeed, the above proof shows that this condition is also sufficient. It is not known whether there exists a countable group which satisfies this but not the stronger condition of the theorem.

Similar remarks apply in later sections, where the sufficient conditions we give are simpler than the best that can be derived by this technique.

5 Henson’s graphs

Henson’s graph H_{p} is the unique countable homogeneous K_{p}-free graph. In the paper [10] in which Henson introduced these graphs, he showed that H_{3} admits a cyclic automorphism (and so is a Cayley object for the infinite cyclic group ℤ), while H_{p} does not for p > 3. We will generalise these results to wider classes of groups. The argument for p > 3 is a simple modification of Henson’s.

For any group X and any a_{1}, …, a_{n} ∈ G, we define

S(a_{1}, a_{2}, …, a_{n}) = {x ∈ X : a_{1}^{−1}xa_{2}^{−1}x ⋯ a_{n}^{−1}x = 1}.

Note that S(a_{1}) = {a_{1}}, and S(a_{1}, a_{2}) is a translate of a square-root set (specifically S(a_{1}, a_{2}) = (\sqrt{a_{2}a_{1}^{−1}})a_{1}. Also, for a, b ∈ X, let

C(a, b) = {x ∈ X : x^{−1}ax = b};

this set is empty if a and b are not conjugate, and is a coset of the centraliser of a if they are conjugate.

Theorem 5.1 Let X be a countable group. Suppose that X cannot be expressed as a finite union of sets of the form S(a), S(a, b) (a ≠ b), S(a, b, c), or C(a, b). Then Henson’s graph H_{3} is a Cayley graph for X. If X is abelian, then we may assume that no sets of the form C(a, b) occur.

Proof As usual, we identify a Cayley graph Cay(X, S) with a sequence of choices of inverse pairs of non-identity elements of X for inclusion in S. This time, however, the choices are not independent, since we want the resulting graph to be triangle-free. Thus, let {x_{1}, x_{1}^{−1}}, {x_{2}, x_{2}^{−1}}, … be the inverse pairs of non-identity elements. Suppose that we have chosen a subset S_{0} by making decisions about the first n pairs, so that Cay(X, S_{0}) is trianglefree. If Cay(X, S_{0} ∪ {x_{n+1}, x_{n+1}^{−1}}) contains a triangle, then we must omit the elements x_{n+1} and x_{n+1}^{−1}; if not, then we may include or omit them. We never get stuck, since omitting elements is always possible. So the set of triangle-free Cayley graphs is identified with the set of paths in a tree.

We claim that the set of graphs isomorphic to H_{3} is residual. The Iproperty for H_{3} asserts that, for any two finite disjoint sets U and V of vertices such that U contains no edge, there is a vertex z joined to everything in U and nothing in V. Take finite subsets U, V of X. We must show that the set of paths for which either U contains an edge or there exists z joined to everything in U and nothing in V is open and dense. That it is open is clear. So assume that we have already made finitely many decisions, and have chosen a set S_{0}. If we have put an element u_{1}^{−1}u_{2} into Δ_{0}, for u_{1}, u_{2} ∈ U, then U contains an edge, and we are done. So suppose not.

Looking for an appropriate z, we first disqualify points z already nonadjacent to something in U or adjacent to something in V: there are finitely many of these. Next, we disqualify points z for which a join to U would force a join to V also: these satisfy u^{−1}z = zv^{−1} for some u ∈ U and v ∈ V, or z ∈ u\sqrt{u^{−1}v}. (This much is exactly as for the random graph.) Finally, we disqualify all those z for which forcing all joins to U would create a triangle. These points must satisfy one of the following:

• u_{1}^{−1}zu_{2}^{−1}zu_{3}^{−1}z = 1, that is, z ∈ S(u_{1}, u_{2}, u_{3}).

• u_{1}^{−1}zu_{2}^{−1}z = u_{3}^{−1}z, that is, z = u_{1}u_{3}^{−1}u_{2}.

• u_{1}^{−1}zu_{2}^{−1}z = s, where s is already included, so z ∈ S(u_{1}s, u_{2}) — note that u_{1}s ≠ u_{2}, since otherwise the edge {u_{1}, u_{2}} in U would be forced, contrary to assumption.

• u_{1}^{−1}zz^{−1}u_{2} = s — impossible since u_{1}s ≠ u_{2}.

• z^{−1}u_{1}u_{2}^{−1}z = s, or z ∈ C(u_{1}u_{2}^{−1}, s).

• ss′ = u^{−1}z, or z = uss′.

• ss′s′′ = 1 — impossible, since then a triangle has already been forced.

By assumption, there is an element z not yet disqualified, so we may make further choices so that z has the required adjacencies and non-adjacencies.

If X is abelian, then u_{1}u_{2}^{−1} = u_{2}^{−1}u_{1} cannot be equal to s, so we can remove the sets C(a, b) from the list in this case.

It is not known whether H_{p} is a Cayley graph for any countable group if p > 3. I prove a weaker result:

Theorem 5.2 H_{p} is not a normal Cayley graph (and in particular, is not a Cayley graph for an abelian group) for p ≥ 4.

Proof Suppose that Cay(X, S) ≅ H_{p}, where S = g^{−1}Sg for all g ∈ X. Choose g_{1}, …, g_{p−2} such that {g_{1}, …, g_{p−2}} induces K_{p−2}. Choose h ∈ X joined to 1 but to none of g_{i}^{−1}g_{j} for i ≠ j (that is, h ∈ S

but g_{j}^{−1}g_{i}h ∉ S for i ≠ j).

Hence g_{i} ∼ g_{i}h but g_{i} ≁ g_{j}h for i ≠ j, and the induced subgraph on the set {gi, g_{i}h : 1 ≤ i ≤ p − 2} is isomorphic to the Cartesian product K_{2} □ K_{p−2}.

This subgraph contains no K_{p−1} (here we use the fact that p ≥ 4), so there is an element k joined to all its vertices. Thus g_{i}^{−1}k, h^{−1}g_{i}^{−1}k ∈ S for all i.

Consider the set {1, h, g^{−1}k, …, g_{p−2}^{−1}k}. Since S is normal, k^{−1}g_{i}^{−1}g_{j}k ∈ S for i ≠ j, so the last p − 2 vertices are all connected. Also, g_{i}^{−1}k ∈ S, so 1 ∼ g_{i}^{−1}k; and h^{−1}g_{i}^{−1}k ∈ S, so h ∼ g_{i}^{−1}k. Finally, 1 ∼ h by choice of h. So the graph contains K_{p}, a contradiction.

6 Other graphs

Part of the importance of Henson’s graphs derives from a theorem of Lachlan and Woodrow [11] determining all countable homogeneous graphs. Note that a graph is homogeneous if and only if its complement is homogeneous. Now Lachlan and Woodrow showed:

Theorem 6.1 Up to complementation, a countable homogeneous graph is isomorphic to one of the following:

• the disjoint union of m copies of K_{n}, where m and n are at most countable and at least one is infinite;

• Henson’s graph H_{p} for some p ≥ 3;

• the random graph R.

We have discussed the difficult cases; it remains only to treat the easy ones. The following result is straightforward.

Theorem 6.2 The disjoint union of m copies of K_{n} is a Cayley graph for X if and only if X has a subgroup of index m and order n; it is a normal Cayley graph for X if and only if X has a normal subgroup with these properties.

There are other interesting countable graphs G which are almost homogeneous, in the following sense: there is a relation R having a first-order definition without parameters in the graph G such that the structure consisting of the graph equipped with the relation R is homogeneous. (The definition of R from G does not necessarily apply in finite subgraphs of G; thus the mappings which are required to extend to automorphisms are more restricted.)

The easiest example is the almost homogeneous bipartite graph B. It is a graph with a bipartition, having the properties • every finite graph with bipartition is embeddable in B;

• every mapping between finite subsets of B which is a graph isomorph-

ism respecting the bipartition extends to an automorphism of B. For example, all pairs of non-adjacent vertices are isomorphic as subgraphs of B, but they fall into two types as ‘subgraphs with bipartition’, according as they are in the same or different parts of the bipartition. The additional relation means that decisions about the bipartition, which are not forced by the structure of a finite subgraph, are made consistently.

Theorem 6.3 Let X be a countable group. Suppose that

(a) X is not the union of a finite number of translates of non-principal square root sets and a finite set;

(b) X has a subgroup of index 2. Then the almost homogeneous bipartite graph B is a Cayley graph for X.

Proof We follow closely the proof of Theorem 4.1. The I-property in this case asserts that, if U and V are finite disjoint sets in the same bipartite block, then there is a point in the other bipartite block joined to every vertex in U and none in V. We must check that, if a finite set of choices have already been made, it is still possible to make further choices so that this holds for given U and V. We take the bipartition to consist of the cosets of the given subgroup Y of index 2. The condition could fail only if the coset X \ Y were the union of finitely many sets of the form (\sqrt{uv^{−1}})v. But then, choosing w ∈ X \ Y, the translates of these sets by w would cover Y, so that X itself would be the union of a finite number of translates of non-principal square-root sets, contrary to assumption.

Note that (b) is the same condition as in Theorem 4.1; if it holds, then different subgroups of index 2 in X give rise to different Cayley graphs for X isomorphic to B.

A permutation graph on the vertex set X is defined as follows: take two total orders <_{1} and <_{2} on X, and let x and y be adjacent if and only if the order of x and y is different in <_{1} and <_{2}. (If X is finite, the second order is obtained from the first by a permutation of X, so the edges of the graph are the inversions of some permutation; hence the name. But this description is not available in the infinite case.) There is a unique countable almost homogeneous permutation graph which contains all finite permutation graphs. We defer consideration of it until Section 11.

The final example to be considered here is the countable almost homogeneous N-free graph constructed by Covington [7]. A graph is N-free if it does not contain a path of length 3 as induced subgraph.

The additional relation required to make such a graph homogeneous is a ternary relation resembling ‘betweenness’, which distinguishes one vertex from each set of three. Consider the possible 3-vertex subgraphs. For those containing one or two edges, one vertex is distinguished by the graph structure. Now if T = {x, y, z} is a 3-clique in an N-free graph, there is at most one vertex in T with the property that it is the unique vertex of T joined to some outside vertex; this vertex is distinguished by the relation (if it exists). (So, for any 3-clique T, the ternary relation distinguishes a vertex of T which may be the unique neighbour of an outside vertex in some larger graph.) The dual applies for a 3-coclique. Covington shows that there is a unique countable homogeneous structure C which consists of an N-free graph with a ternary relation as described embedding all such finite structures.

Much less is known about groups for which C is a Cayley graph; but the following holds.

Theorem 6.4 Covington’s graph C is a Cayley graph for the countable elementary abelian 2-group but not for the infinite cyclic group ℤ.

Proof For the first assertion, we give an explicit construction of C. Let X be the set of all finite subsets of ℚ. (Then X, with the operation of symmetric difference, is an elementary abelian 2-group). Given A, B, C ∈ X, consider the three sets A △ B, A △ C and B △ C. Since the symmetric difference of these three sets is empty, two of them (without loss A △ B and A △ C) have the same minimum element, which is different from the minimal element of the third; in this case, the ternary relation distinguishes A. To obtain the compatible N-free graph, we colour the rationals with two colours, say black and white, so that each colour class is dense. (This can be done uniquely, up to order-automorphisms of ℚ.) Them we join A to B if the minimum element of A △ B is black. It is readily checked that this gives Covington’s structure and that it is a Cayley object for the group X.

For the second part of the theorem, we give a complete description of N-free Cayley graphs for ℤ, and observe that none is isomorphic to C. Note, first, that a graph is N-free if and only if its complement is, and that C is connected, since it is isomorphic to its complement. (This contrasts with the situation for finite N-free graphs, where a such graph is connected if and only if its complement is disconnected.)

Let Cay(ℤ, S ∪ (−S)) be N-free, where S is a set of positive integers. Replacing S by its complement if necessary, we may assume that 1 ∈ S.

Now let (m_{1}, m_{2}, …) be a finite or infinite sequence of integers greater than 1. Let p_{n} = m_{1}m_{2} ⋯ m_{n} for n ≥ 1, with p_{0} = 1. Let S(m_{1}, m_{2}, …) be the set of positive integers s such that the maximum k for which p_{k} divides s is even. We claim that the corresponding Cayley graph is N-free, and that every N-free Cayley graph for ℤ in which 0 is joined to 1 has this form. But no such graph is isomorphic to C, since its complement is disconnected. (The components of the complement are the congruence classes modulo n_{1}.)

The N-freeness of the graph is a simple calculation. To prove the other part of the claim, it suffices to show the following: if Cay(ℤ, S ∪ (−S)) is N-free, 1 ∈ S, and n_{1} is the least positive integer not in S, then all positive integers not divisible by n_{1} are in S. For then the induced subgraph on the set of multiples of n_{1} is a cyclic N-free graph, and the result follows by induction. Now, if x were the smallest number not divisible by n_{1} which is not in S, then the induced subgraph on {0, x − n_{1}, n_{1}, x} would be a path of length 3; so no such x can exist.

7 Hypergraphs

No classification of countable homogeneous hypergraphs is known. We restrict attention to the analogues of Rado’s graph. For each k > 2, there is a unique countable homogeneous k-uniform hypergraph R_{k} which contains all finite k-uniform hypergraphs (the Fraïssé limit of the class of all finite k-uniform hypergraphs). Thus, R_{2} is the graph R. For k > 2, we can answer the question completely.

Theorem 7.1 For k > 2, the hypergraph R_{k} is a Cayley object for every countable group.

Proof The I-property for R_{k} asserts the following: if C is a finite set carrying a (k − 1)-uniform hypergraph C, then there exists a vertex x such that, for any (k − 1)-subset B of C, B ∪ {x} is an edge of R_{k} if and only if B ∈ C.

In searching for such a point, we must disqualify any point x for which B ∪ {x} and B′ ∪ {x} lie in the same orbit. If this occurs, then B′ ∪ {x} = (B ∪ {x})y for some y ∈ X. Thus we have k equations of the form b′ = by, x = by, or b′ = xy. Since k ≥ 3, there is at least one equation of the first type; but this determines y as b^{−1}b′, and hence x as one of the finitely many elements of the form by for b ∈ B. Thus each pair of (k − 1)-sets exclude a finite number of points x. So infinitely many choices for x remain valid.

8 Directed graphs

In a major recent piece of work, Cherlin [6] has determined all the countable homogeneous directed graphs. There are uncountably many of them. So it would be possible to pose the question: for which countable groups do there exist homogeneous Cayley digraphs? The goal here is much more modest: I consider just two of these digraphs, namely the digraph and tournament analogous to the random graph (that is, the homogeneous structures D and T whose ages are the classes of all finite digraphs and all finite tournaments respectively).

Theorem 8.1 Let X be a countable group which cannot be expressed as the union of finitely many translates of square root sets and a finite set.

(a) The digraph D is a Cayley object for X.

(b) If the only square root of 1 is 1, then the tournament T is a Cayley object for X.

Proof The proof follows the usual lines. Note that, by contrast with Theorem 4.1, we include the square root set of the identity. This is because we might be required to join the new vertex x to an existing vertex u by a directed edge; but, if (xu^{−1})^{2} = 1, this would not be possible, so such points x, lying in (\sqrt{1})u, must be excluded. Moreover, in a tournament, every point has this property, so there can be no non-trivial square roots of 1 at all. (Said otherwise, a tournament can have no automorphism of order 2.)

9 Metric spaces

We consider integral metric spaces, or IMSs for short, those in which all distances are integers. Now a homogeneous metric space is certainly distancetransitive, in the sense that, if d(x, y) = d(u, v) then there is an isometry carrying (x, y) to (u, v). As observed in Cameron [4], if M is an IMS in which the distance-1 graph is connected, then the metric in M coincides with the path metric in the distance-1 graph (which is thus itself distance-transitive).

It was observed in [4] that the following classes of finite IMSs are Fraïssé classes, so that their Fraïssé limits are countable homogeneous IMSs:

• the class M_{d} of all finite IMSs of diameter at most d, where d is a positive integer or d = ∞;

• the class H_{d,p} of all finite IMSs of diameter at most d which contain no unit (p − 1)-simplex (set of p points mutually at distance 1), where d is as above and p ≥ 3.

We denote the Fraïssé limits of M_{d} and H_{d,p} by M_{d} and H_{d,p} respectively. Note that M_{2} and H_{2,p} are the graphs R and H_{p} respectively, with the path metric.

It is also possible to obtain ‘bipartite’ analogues, by specifying that the perimeter of every triangle should be even. The bipartite analogue of M_{3} is the graph B with the path metric.

The results here are much less complete. The following two positive results are given as examples of what can be done, rather than as approximations to a definitive result.

Theorem 9.1 For any d, including d = ∞, the metric spaces M_{d} and H_{d,3}, together with their bipartite analogues, are Cayley objects for the countable elementary abelian 2-group.

Proof Let x_{1}, x_{2}, … be a basis for the countable elementary abelian 2-group X. We describe metric spaces for the group as follows. Suppose that distances from the identity to elements of X_{n} = ⟨x_{1}, …, x_{n−1}⟩ have been specified. Then all distances within X_{n} are determined. Consider the point x_{n}. Choose any integral metric on X_{n} ∪ {x_{n}} compatible with the appropriate conditions. Then all distances in X_{n+1} = ⟨X_{n}, x_{n}⟩ are determined, by translation. Moreover, no contradiction arises. For any triangle in X_{n+1} is equivalent under translation to either a triangle in X_{n}, or a triangle with one vertex at x_{n} and the other two in X_{n}.

Now let B = A ∪ {a} be a member of the age of the appropriate homogeneous object, and let C be a subset of X. We have to show that the class of metrics on X for which the I-property holds is open and dense. As usual, the openness is clear. Suppose that C is isometric to A once the metric on ⟨C⟩ = X_{n} has been specified. We specify distances from x_{n} to C so that C ∪ {x_{n}} is isometric to B. Because of the amalgamation property, we can extend this to specify distances from x_{n} to all of X_{n}, and then continue the construction as before.

Theorem 9.2 For every d, including d = ∞, the metric spaces M_{d} and H_{d,3} are Cayley objects for the infinite cyclic group.

Proof In the case d = 2, the metric is the path metric of the graph R or H_{3}, so assume that d ≥ 3.

Identify the points of the metric space with the integers. Then a cyclic IMS is specified by a function f on the positive integers, taking positive integer values, and values in the set {1, 2, …, d} in the case of an IMS of diameter d: the metric is given by d(x, y) = f(|x−y|). The triangle inequality holds provided that f satisfies

|f(y) − f(x − y)| ≤ f(x) ≤ f(y) + f(x − y)

for all y ≤ x, with the convention that f(0) = 0.

We consider first the metric space M_{d} of finite diameter d, and postpone the remaining cases until the end of the proof.

First, we show that, if the values f(1), f(2), … are chosen in turn, no conflict arises: this will prove that the cyclic metric spaces are described by infinite paths in a tree. A conflict would arise only if a lower bound f(y) − f(x − y) for f(x) turned out to be greater than d or greater than an upper bound f(z) + f(x − z) for f(x), where 0 < y, z < x. We cannot have f(y) − f(x − y) > d, since f(y) ≤ d and f(x − y) ≥ 0. Suppose that

f(y) − f(x − y) > f(z) + f(x − z).

Then f(y) − f(z) > f(x − z) + f(x − y), which is impossible since

f(y) − f(z) ≤ f(|y − z|) ≤ f(x − z) + f(x − y)

(all the arguments in this equation being less than x).

Now the point of substance required in the Baire category argument is that, given C ≅ A, we can find z such that C ∪ {z} ≅ B, where A, B are finite IMSs in (M)_{d} with B = A ∪ {a}. By translation, we may assume that C ⊆ {0, 1, …, n}; and by the Amalgamation Property, we may assume that in fact C = {0, 1, …, n}, where the values of f(x) have been chosen appropriately for x ≤ n. We have to assign the point z and the values f(n + 1), …, f(z) so that f(z − c′) = d(b, a′), where a′ corresponds to c′ under the isometry.

We take z = nd + 1. Then the values assigned to f(x) for x = n(d − 1) + 1, …, nd + 1 are prescribed, and we have to fill in the intervening values without violating the triangle inequality. We do this by prescribing values which satisfy the following extra condition. Let I_{i} = {in + 1, …, (i + 1)n}. Then, for x ∈ I_{i}, we require

i + 1 ≤ f(x) ≤ d − i if i ≤ (d − 1)/2;
d − i ≤ f(x) ≤ i + 1 if i ≥ (d − 1)/2.

Note that these conditions are vacuous for i = 0 and for i = d − 1, the values which are already assigned. We choose f(x) and then f(dn + 1 − x) in turn for x = n + 1, …, ⌊(dn + 1)/2⌋. We have to show that no conflicts arise.

We begin by disposing of one possible conflict. It could happen that, for some x ≤ (dn + 1)/2, we have already chosen f(2x), in which case f(x) must satisfy 2f(x) ≥ f(2x). But in this case, if x ∈ I_{i}, then 2x ∈ I_{2i} ∪ I_{2i+1}, with 2i ≥ (d − 1)/2 or 2i + 1 ≥ (d − 1)/2 respectively; and so

f(2x)/2 ≤ (2i + 2)/2 = i + 1.

So provided that the lower bound i + 1 ≤ f(x) does not conflict, neither will this bound.

The remaining bounds for x ≤ (nd + 1)/2 can be stated as follows:

|f(y) − f(x − y)| ≤ f(x) ≤ f(y) + f(x − y)  (1)
|f(x + y) − f(y)| ≤ f(x) ≤ f(x + y) + f(y)  (2)
i + 1 ≤ f(x) ≤ d − i  (3)

We denote a potential conflict arising because the left-hand side of inequality (X) is greater than the right-hand side of (Y) by (X).(Y) – there are nine cases to consider. Many of the arguments are similar, and only a few representative cases will be given.

In case (1).(1), conflict doesn’t occur: this is precisely the argument we used to show that no conflict arises when values of f(x) are chosen in order.

In case (2).(1), we would have

|f(x + z) − f(z)| > f(y) + f(x − y),

with y, z < x and x + z > dn + 1 − x. Suppose that z ∈ I_{j}. Then j + 1 ≤ f(z) ≤ d − j and d − i − j − 1 ≤ f(x + z) ≤ i + j + 2. These inequalities imply that both f(x + z) − f(x) and f(x) − f(x + z) are at most i + 1. But, if y ∈ I_{k}, then

f(y) + f(x − y) ≥ (k + 1) + (i − k) = i + 1,

and there is no conflict.

Finally, case (3).(3) is consistent, by our choice of x ≤ (dn + 1)/2.

Now, for the choice of f(nd + 1 − x), there are three similar pairs of inequalities; the proof of consistency is very similar to the cases just considered.

Now consider the case where d = ∞. In this case, simply replace d in the above proof by the largest distance that occurs between points of the metric space A ∪ {a}.

Finally, consider the Henson variation. In this case, we may not assign f(x) = 1 if we already have f(y) = f(x−y) = 1 or f(y) = f(x+y) = 1. But, in the above proof, we never assign f(x) = 1 at all: the lower bound is either i + 1or d − i if x ∈ I_{i} for 1 ≤ i ≤ d − 2; the values of f(x) for x ∈ I_{0} ∪ I_{d−1} are given.

Remark In the case when d = 3, we only ever assign the value 2 to f(x). Clearly no conflict arises, since the only violation of the triangle inequality would be a possible triangle with sides 1, 1, 3, while for the Henson metric space, a violation would have sides 1, 1, 1.

Problem For which countable groups X is M_{d} or H_{d,3} a Cayley metric space for X?

On the negative side, we have the following:

Theorem 9.3 For any d (including d = ∞) and any p ≥ 4, the metric space H_{d,p} is not a normal Cayley object for any countable group.

The proof follows the similar proof for K_{n}-free graphs (Theorem 5.2): simply replace ‘adjacent’ and ‘non-adjacent’ by ‘distance 1’ and ‘distance 2’ respectively.

10 Linear orders

There is a unique countable homogeneous linear order, namely ℚ. In fact, Cantor’s Theorem characterises ℚ as the unique countable linear order which is dense (that is, if x < y then there exists z with x < z < y) and without endpoints (that is, for all x there exist u, v with u < x < v). These conditions express the I-property for sets of cardinality at most 2.

A group has a total order as a Cayley object if and only if it is rightorderable; it has a total order as a normal Cayley object if and only if it is orderable. There is a considerable literature on these concepts (see Mura and Rhemtulla [12]). However, the question of when this order is dense has not been discussed much. Here are a couple of remarks.

The infinite cyclic group ℤ has a unique order (up to reversal), namely the usual one. This is not dense. However, for m ≥ 2, ‘almost all’ orders of ℤ^{m} are dense. For, given any order of ℤ^{m}, there are real numbers α_{1}, …, α_{m}, not all zero, such that

(x_{1}, …, x_{m}) ≤ (y_{1}, …, y_{n}) ⇒ α_{1}(y_{1} − x_{1}) + ⋯ + α_{m}(y_{m} − x_{m}) ≥ 0.

If α_{1}, …, α_{m} are linearly independent over ℚ (which holds generically), then the implication reverses and the order is determined; in this case, it is easily seen that the order is dense. Otherwise, there is a proper subgroup H of ℤ^{m} consisting of elements whose relation to 0 is not determined by the displayed condition, and we are free to choose any order on this subgroup. The order on ℤ^{m} is dense if and only if the order on H is dense.

So ℚ (as ordered set) is a Cayley object for ℤ^{m} if and only if m > 1. Consider the special case m = 2. Any order on ℤ^{2} is given by a pair

α, β of real numbers, not both zero, with (x, y) > 0 if αx + βy > 0. If the ratio of α and β is irrational, this determines the order, which is dense. Otherwise, there are two possible choices for the order, which is not dense: it is isomorphic to the lexicographic order.

There are three important types of relation derived from a linear order: betweenness, circular order, and separation. See [1, 2, 3] for details. Much less is known about their occurrence as Cayley objects. I conclude this section with some brief remarks about the first two of these. First, a general comment: if a linear order is a Cayley object for X, then so are the betweenness, circular order and separation derived from it.

If < is a linear order on X, the derived betweenness relation is a ternary relation defined as follows: y is between x and z if either x < y < z or z < y < x.

Theorem 10.1 Suppose that the betweenness derived from the countable dense linear order < is a Cayley object for the group X. Then either (a) X has a dense right order: or

(b) X has a subgroup Y of index 2 with a dense right order.

Proof Every element of X preserves or reverses the order <. If every element preserves the order, then alternative (a) holds. Otherwise, there is a subgroup Y of X of index 2 consisting of elements which preserve the order.

Suppose that the order on Y is not dense. We colour elements of Y red and elements of X \ Y blue. Then there exist two red points x, y with no red point between them. Since Y is an orbit, every red point has a red immediate predecessor and a red immediate successor; and the same is true with blue replacing red. Now there is a point z between x and y, which must be blue. There is a point u between x and z, which must also be blue. Thus the blue predecessor v of z must satisfy u ≤ v. There is a point between v and z, which cannot be either red or blue without giving a contradiction.

In this case, the elements of X \ Y interchange the two orbits and reverse the order. There are various configurations. It may occur that each orbit is dense in the whole order: for example, take the dense linearly ordered set X = \{q, q + \sqrt{2} : q ∈ ℚ\}. The additive group of ℚ acts with two orbits, each dense in X, and the map x ↦ \sqrt{2} − x interchanges them and reverses the order. However, it is possible to construct examples where one orbit precedes the other, or where the two orbits are made up of interlacing intervals.

For the circular order (the ternary relation which is satisfied by (x, y, z) if one of x < y < z, z < x < y or y < z < x holds), I merely give some examples. As noted, any group with a dense right order has the derived circular order as a Cayley object. All such groups are torsion-free. But there are other groups, in particular torsion groups, for which the circular order is a Cayley object. One example is the group ℚ/ℤ (the multiplicative group of complex roots of unity).

This circular order is also a Cayley object for the infinite cyclic group: for the group generated by a rotation of the unit circle through an irrational multiple of 2π has the property that any orbit is dense.

11 n-tuples of orders

There is a unique countable homogeneous n-tuple of linear orders, which is the Fraïssé limit of the class of all finite sets carrying n independent linear orders. The I-property can be stated as follows: If <_{1}, …, <_{n} denote the orders then, for any k distinct points x_{1}, …, x_{k} and any k-tuple (q_{1}, …, q_{k}) of numbers from the set {0, …, k}, there exists a point z which lies in the q_{i}th interval defined by x_{1}, …, x_{k} with respect to <_{i}, for i = 1, …, n. (Here, for any order <, if a_{1} < … < a_{k}, the k intervals defined by these points are {z : z < a_{1}}, {z : a_{1} < z < a_{2}}, …, {z : a_{k} < z}; we number them from 0 to k.) By Cantor’s Theorem, for n = 1 it suffices to require this condition for k ≤ 2; and it can be shown that, in general, it suffices to require it for k ≤ 2n.

Problem For which pairs (m, n) is the unique countable homogeneous n-tuple of linear orders a Cayley object for ℤ^{m}?

Clearly this never holds for m = 1. The case m = 2 can be completely resolved:

Theorem 11.1 The countable homogeneous universal n-tuple of linear orders is a Cayley object for ℤ^{2} if and only if n = 1.

Proof We saw in the last section that any dense order on ℤ^{2} is determined by two real numbers α, β with irrational ratio, where (x, y) > (0, 0) if and only if αx + βy > 0. So an n-tuple of dense orders is given by a 2 × n matrix A, so that (x, y) >_{i} (0, 0) if and only if the ith entry of (x, y)A is positive.

Suppose that the columns of A are linearly dependent (over ℝ). Then without loss of generality, we have

A_{in} = ∑_{j=0}^{n−1} a_{ij}v_{j}

for some real numbers v_{1}, …, v_{n−1}, not all zero. Let x and y be any two m-tuples of integers such that

x <_{j} y if v_{j} > 0,
y <_{j} x if v_{j} < 0.

(If v_{j} = 0, the order doesn’t matter. Note that the choice is possible if the n-tuple of orders is universal.) Then

(yA)_{n} − (xA)_{n} = ((y − x)A)_{n}

= ∑_{j=0}^{n−1}((y − x)A)_{j}v_{j}
> 0

by choice of x and y. So the order <_{n} is not independent of {<_{j} : j < n}. This shows that n ≤ 2.

Now suppose that n = 2. Without loss, let

A = ( \begin{matrix}1 & 1 \\ α & β \end{matrix} ) ,

where α and β are distinct irrationals. Suppose that α and β are positive (the other cases are similar), and suppose that α < β. Choose a rational number r/s with r, s > 0, α < r/s < β, and s minimal subject to this. Then

−r + αs < 0 < −r + βs.

If the pair of orders is universal, there exist p, q ∈ ℤ with

−r + αs < −p + αq < 0 < −p + βq < −r + βs.

Since αq < βq, we have q > 0. Hence q > s. But then

−(p − r) + β(q − s) < 0 < −(p − r) + α(q − s),

or

β < \frac{p − r}{q − s} < α,

a contradiction.

In Section 6 we mentioned the problem of determining groups X for which the countable universal almost homogeneous permutation graph is a Cayley object. This graph is defined by the countable universal pair of linear orders, in the same sense that betweenness or circular order are defined by a single linear order. So, if this pair of orders is a Cayley object for the group X, so is the universal permutation graph. (The converse is not true, since an automorphism of the permutation graph may interchange the two orders, or may reverse both of them.)

References

[1] S. A. Adeleke and P. M. Neumann, Relations related to betweenness: their structure and automorphisms, Memoirs Amer. Math. Soc. 131, no. 623, American Mathematical Society, Providence, RI, 1998.

[2] K. Borsuk, Foundations of Geometry, North Holland Publ. Co., Amsterdam, 1960.

[3] P. J. Cameron, Transitivity of permutation groups on unordered sets, Math. Z. 48 (1976), 127–139.

[4] P. J. Cameron, A census of infinite distance-transitive graphs, Discrete Math. 192 (1998), 11–26.

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

[6] G. L. Cherlin, The classification of countable homogeneous directed graphs and countable homogeneous n-tournaments, Memoirs Amer. Math. Soc. 131, no. 621, American Mathematical Society, Providence, RI, 1998.

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

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

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

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

[11] A. H. Lachlan and R. E. Woodrow, Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc. 262 (1980), 51–94.

[12] R. B. Mura and A. Rhemtulla, Orderable Groups, Marcel Dekker, New York, 1977.

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