A census of infinite distance-transitive graphs

Peter J. Cameron

Abstract This paper describes some classes of infinite distance-transitive graphs. It has no pretensions to give a complete list, but concentrates on graphs which have no finite analogues.

1 Introduction

There are various degrees of symmetry which a graph might display. Most of these are of a ‘local-to-global’ type, asserting that, if two configurations which look the same with respect to some local property, then one can be mapped to the other by an automorphism of the graph. The strongest such property is homogeneity, asserting that any isomorphism between finite induced subgraphs extends to an automorphism of the graph. All finite or countable graphs with this property have been determined [13], [20].

A weaker condition is k-homogeneity, where we only require that isomorphisms between subgraphs on at most k vertices extend to automorphisms. Thus 1-homogeneity is simply vertex-transitivity. A finite graph is 2-homogeneous if and only if its automorphism group is a rank 3 permutation group of even order. (The rank of a transitive permutation group is the number of its orbits on ordered pairs of points. In the case of a 2-homogeneous graph, the orbits consist of pairs which are equal, adjacent, and non-adjacent respectively.)

The determination of the rank 3 permutation groups (and so, implicitly, the finite 2-homogeneous graphs) was completed by Liebeck [21], building on many earlier results, and in particular using the classification of finite simple groups. Without the classification, the best result is that of Cameron [3], who found that all finite 5-homogeneous graphs are homogeneous. Note that, for all k < 5, there are graphs which are k-homogeneous but not (k + 1)-homogeneous.

For countably infinite graphs, much less is known. A referee has pointed out to me that graphs which are k-homogeneous but not (k + 1)-homogeneous exist for all k (see Section 4). The same question has been considered for other classes of structures, such as posets: see [23], [11].

Homogeneity can be weakened in another way. Any connected graph can be regarded as a metric space. We may call a graph metrically homogeneous if any isometry between finite subsets extends to an isomorphism, and metrically k-homogeneous if this holds for all subsets with cardinality at most k. Now metrically 2-homogeneous graphs are precisely distance-transitive graphs: any two pairs of vertices at the same distance are equivalent under an automorphism.

The finite distance-transitive graphs have not yet been determined, but a considerable amount of work has been done, based on a classification due to Smith [25]. A graph is imprimitive if there is an equivalence relation on its vertex set which is preserved by all automorphisms. Smith showed that, in the case of a distance-transitive graph of valency greater than 2, there are only two possibilities for such an invariant equivalence relation: either it is a bipartition, or it is the relation of being equal or at maximal distance (the so-called antipodal relation). If the graph is bipartite, then a connected component of the distance-2 graph (on a bipartite block) is distance-transitive. If it is antipodal, then the quotient by the antipodal relation is distance-transitive. After at most one reduction of each type, a primitive distance-transitive graph is reached. So the program is first to determine the finite primitive distance-transitive graphs (using the classification of finite simple groups), and then to find all ‘bipartite doubles’ and ‘antipodal covers’ of these graphs. The first part is almost complete, the second rather less so.

A very complete reference on finite distance-transitive graphs is the book of Brouwer, Cohen and Neumaier [1].

By contrast, the theory of infinite distance-transitive graphs is open. Not even the countable metrically homogeneous graphs have been determined. The purpose of this article is to describe the known examples of infinite distancetransitive graphs.

There are two other kinds of graph symmetry which we will meet in passing. An s-arc is a sequence v_{0}, v_{1}, …, v_{s} of vertices such that v_{i} and v_{i+1} are

adjacent for 0 ≤ i ≤ s − 1, and v_{i} ≠ v_{i+2} for 0 ≤ i ≤ s − 2. Thus it is a walk, with repeated edges or vertices permitted, but which never immediately retraces an edge. A graph is s-arc transitive if its automorphism group acts transitively on s-arcs. Weiss [29] showed that a finite graph with valency greater than 2 cannot be more than 7-arc transitive. However, a regular tree is s-arc transitive for all s.

The second condition does not initially seem to have anything to do with symmetry. A countable structure M is ℵ_{0}-categorical if any countable structure satisfying the same first-order sentences as M is isomorphic to M. According to the theorem of Engeler, Ryll-Nardzweski and Svenonius (see [5]), M is ℵ_{0}-categorical if and only if its automorphism group is oligomorphic. (A permutation group is oligomorphic if it has only finitely many orbits on n-tuples of points for all natural numbers n.)

Note that, for example, an ℵ_{0}-categorical graph has finite diameter (since pairs of points at different distance cannot be in the same orbit of the automorphism group). By contrast, let M be a homogeneous graph (or, more generally, a homogeneous relational structure over any finite relational language).

Then two finite subsets lie in the same orbit of the automorphism group if and only if they induce isomorphic substructures; the orbits on n-element subsets correspond to the isomorphism types of n-element structures, which are finite in number. So M is ℵ_{0}-categorical.

2 Macpherson’s Theorem

There is one class of infinite distance-transitive graphs which is completely known: the locally finite ones. Let s and t be positive integers. There is a unique biregular tree with valencies s+1 and t+1. (This means that all vertices have valency s + 1 or t + 1, and two adjacent vertices have different valency if s ≠ t. Said otherwise, all vertices in one bipartite block have valency s + 1, and all those in the other have valency t + 1.)

Define the graph M(s, t) to be the distance-2 graph on the bipartite block with valency t + 1. In other words, its vertices are the vertices of the tree of valency t + 1, and two vertices are adjacent if their distance in the tree is 2. Note that, if s = 1, this graph is the (t + 1)-vslent tree.

Macpherson [22] proved:

Theorem 2.1 A locally finite infinite distance-transitive graph is isomorphic to M(s, t) for some positive integers s and t.

A consequence of this result is the following:

Corollary 2.2 For any given integer k > 2, there are only finitely many finite distance-transitive graphs of valency k.

The proof uses the compactness theorem of first-order logic. There are only finitely many structures for the d-neighbourhood of a vertex v, and the group of permutations induced on it by automorphisms fixing v, for any fixed d. So, if there were infinitely many such graphs, then there would be infinitely many with the same d-neighbourhood structure. So, by compactness, there would be an infinite graph with this structure, necessarily M(s, t) for some s and t. But the resulting restrictions can be eliminated using arguments of finite group theory. The first proof of this [4] used the classification of finite simple groups; this was later avoided by Weiss [30].

The graph M(s, t) can be defined as well when one or both of s and t is infinite, and is distance-transitive.

3 Analogues of finite graphs

The book [1] contains extensive lists of finite distance-transitive graphs. Many of these have infinite analogues. What follows is not a complete survey.

One class consists of the Hamming graphs H(n, q), whose vertices are all the words of length n over an alphabet of q symbols, two vertices adjacent if they differ in exactly one coordinate. Now it is clear that we can allow the size of the alphabet to become infinite and use the same definition to obtain infinite distance-transitive graphs with diameter n. If, however, we allow the word length to be infinite, the graph is no longer connected: two words lie in the same component if and only if they differ in only finitely many coordinates, and there are uncountably many components. Each component is distancetransitive with infinite diameter, and all are isomorphic. It is customary to select a distinguished component as follows: assume that one of the symbols in the alphabet is called ‘zero’; then take all words with only finitely many non-zero components.

Similarly, the Johnson graph J(v, k) (whose vertices are the k-subsets of a v-set, joined if their symmetric difference has size 2), can be infinitised in two ways. If we allow v to be infinite but keep k finite, we obtain a distance-transitive graph with diameter k.

If we allow both v and k to be infinite, things are different. We assume for simplicity that v = k = ℵ_{0}, and take only infinite sets whose complement is infinite. First of all, the smallest size of the symmetric difference is now 1, rather than 2, and we obtain the same graph as the Hamming graph with q = 2 (apart from two special components corresponding to finite and cofinite sets).

Now the subsets (and hence the components) fall into complementary pairs. The set of equivalence classes of such partitions which have both parts infinite carries a distance-transitive graph of diameter 2: we join two classes of partitions if the common refinement of a partition from each class has only three (rather than four) infinite classes. Note that this provides a rank 3 permutation representation of the symmetric group of countable degree modulo the finitary symmetric group. This observation is due to B. H. Neumann. Moreover, there is a unique countable graph with the same first-order theory: it is also distance-transitive with diameter 2.

In the finite case, there are also various graphs defined in terms of finite vector spaces. For example, the q-analogue of a Johnson graph has as vertices the k-dimensional subspaces of a v-dimensional vector space. Both the dimension v and the size of the field can be allowed to become infinite without any problem.

If the automorphism group of a projective plane is transitive on pairs of points, pairs of lines, flags, and antiflags, and the plane is self-dual, then its incidence graph is distance-transitive with diameter 3. In the finite case, 2transitivity on points implies that the plane is Desarguesian, whence all the other conditions follow. In the infinite case, there are highly symmetric non-Desarguesian planes (see Kegel and Schleiermacher [17]). Further examples are obtained from incidence and point graphs of generalised polygons.

4 Graphs of diameter 2

The most useful method for constructing objects with a large amount of symmetry is based on Fraïssé’s Theorem. The age of a graph or other structure is the class of all finite structures embeddable in it. The amalgamation property for a class of finite structures asserts that, if structures B_{1}, B_{2} in the class have substructures both isomorphic to a common structure A, then there is a structure C in the class containing copies of B_{1} and B_{2} with the common substructure identified according to the isomorphism. Now Fraïssé’s Theorem states:

Theorem 4.1 A class C of finite structures is the age of a countable homogeneous structure M if and only if C is closed under isomorphism, closed under taking induced substructures, contains only countably many non-isomorphic structures, and has the amalgamation property. If these conditions hold, then M is unique up to isomorphism.

See [5] for discussion. The structure M is called the Fraïssé limit of the class C. One strengthening we need later is the strong amalgamation property, where it is required that the intersection of B_{1} and B_{2} inside C is precisely A (no larger). This is equivalent to the condition that, in the Fraïssé limit M, for any finite set of points the group of automorphisms fixing those points has no further fixed points.

For example, the class of all graphs satisfies Fraïssé’s conditions; the Fraïssé limit is the random graph, or Rado’s graph. More generally, Henson [15] observed that, for any n ≥ 3, the class of finite graphs containing no K_{n} satisfies Fraïssé’s conditions. (To amalgamate two K_{n}-free graphs with a common subgraph, take the union, with no additional edges.) The Fraïssé limit, denoted H_{n}, is a homogeneous graph containing no K_{n} but embedding all finite K_{n}-free graphs. This gives us an infinite family of distance-transitive graphs of diameter 2.

This is essentially the complete list of countable homogeneous graphs. Lachlan and Woodrow [20] showed:

Theorem 4.2 A countable homogeneous graph is one of the following: the disjoint union of m complete graphs of size n, with at least one of m and n infinite; the complement of one of these; one of Henson’s graphs H_{n} or their complements; or the random graph.

Further graphs can be obtained by modifying the procedure, taking the finite graphs to have extra structure. For example, the class of bipartite graphs fails to be homogeneous, since given two non-adjacent vertices, we do not know whether they are in the same bipartite block or not. So, for example, it is impossible to amalgamate a path of length 2 and one of length 3 with common endpoints in this class. However, the class of graphs with a prescribed bipartition does satisfy Fraïssé’s conditions. (There are two structures in this class which as graphs consist of two nonadjacent vertices.) The Fraïssé limit is a universal bipartite graph which is distance-transitive of diameter 3.

A referee has pointed out the following examples. For k ≥ 1, let C be the class of finite graphs with a (k + 1)-ary relation R such that, if R(x_{0}, …, x_{k}) holds, then {x_{0}, …, x_{k}} is a maximal (k + 1)-clique. The Fraïssé limit is a khomogeneous but not (k + 1)-homogeneous graph, which is distance-transitive of diameter 2 if k ≥ 2.

For another example, take the Fraïssé limit of the class consisting of finite sets carrying two independent total orders, and then form a graph by joining two points whenever the two orders agree on those points. This is the comparability graph of the universal 2-dimensional partial order, or the universal permutation graph: see [14].

A more complicated variation is due to Covington [9], who showed how to give extra structure to the class of finite N-free graphs (graphs with no induced path of length 3) so that Fraïssé’s conditions hold. The Fraïssé limit is distancetransitive with diameter 2. Unlike most Fraïssé limits, Covington’s graph has an explicit description. Partition the rational numbers into two dense subsets A and B. Now the vertices of the graph are the finite subsets of ℚ, two vertices adjacent if and only if the least element of their symmetric difference is in A.

Henson’s triangle-free graph H has diameter 2 and girth 4, and contains induced cycles of length 5. It is easy to see that, in consequence, the Cartesian product H × K_{2} is a distance-transitive graph of diameter 5. (The Cartesian product H ×K of two graphs H and K has an edge {(u_{1}, v_{1}), (u_{2}, v_{2})} whenever {u_{1}, u_{2}} is an edge of H and {v_{1}, v_{2}} is an edge of K.) This procedure applied to other homogeneous graphs does not yield distance-transitive graphs (apart from, trivially, the complete graph G = K_{ℵ_{0}}, for which G × K_{2} is the complete bipartite graph with a matching removed).

5 Homogeneous metric spaces

In this section we construct distance-regular graphs of arbitrary diameter (possibly infinite). They are not homogeneous as graphs, so we construct them as metric spaces. We need to be able to recognise metric spaces which come from distance-transitive graphs.

We consider integral metric spaces, that is, metric spaces where all distances are non-negative integers. In such a metric space (M, d), we form a graph (the distance-1 graph of M) by joining two points whose distance is 1.

The metric space (M, d) is 2-homogeneous, or distance-transitive, if whenever d(x, y) = d(u, v), there is an isometry of M mapping (x, y) to (u, v).

We say that the integral metric space M is graphic if the distance in M is equal to the distance in its distance-1 graph X.

The following result is straightforward.

Proposition 5.1 Let M be an integral metric space which is distance-transitive and whose distance-1 graph is connected. Then M is graphic (and its distance-1 graph is distance-transitive).

Proof. Let G be the distance-1 graph, and d_{M}, d_{G} the metrics in M and G respectively. By the Triangle Inequality, d_{M} ≤ d_{G}. If d = d_{M}(x, y) < d_{G}(x, y) for some x, y, and d is minimal subject to this, then there two points at distance d in M which are joined by a path of length d in G, and another two points at distance d which are not, contradicting the distance-transitivity of M.

Theorem 5.2 The class of finite integral metric spaces has the amalgamation property; so there exists a unique countable homogeneous graphic metric space M.

Proof. Let A, B_{1}, B_{2} be finite integral metric spaces with A a subspace of both B_{1} and B_{2}. It suffices to consider the case where B_{1} = A ∪ {x}, B_{2} = A ∪ {y}: the general case can be done by a number of steps of this kind. We have to define an integral distance d(x, y) so that the triangle inequality is satisfied. This means that, for any a ∈ A, we must have

|d(a, x) − d(a, y)| ≤ d(x, y) ≤ d(a, x) + d(a, y).

This could only fail if there exist a, b ∈ A such that

|d(a, x) − d(a, y)| > d(b, x) + d(b, y).

Assume that this holds and, without loss, that d(a, x) > d(a, y). Then

d(a, x) − d(b, x) > d(a, y) + d(b, y),

contradicting the fact that

d(a, x) − d(b, x) ≤ d(a, b) ≤ d(a, y) + d(b, y).

So the choice of d(x, y) is always possible.

The construction can be varied in a number of ways.

First variation. Consider the class of finite integral metric spaces with diameter at most n, for any fixed n. For, in the above argument, the only possible failure of amalgamation would occur if |d(a, x) − d(a, y)| > n, which is impossible if d(a, x) and d(a, y) are both at most n.

If we choose n = 2, the distance-1 graph is the random graph.

Second variation. Consider the class of finite integral metric spaces in which each triangle has even perimeter. In this case,

d(a, x) − d(b, x) ≡ d(a, b) ≡ d(a, y) + d(b, y) (mod 2),

and so the upper and lower bounds for d(x, y) have the same parity, and we can choose d(x, y) to have the same parity as these bounds.

Note that the distance-1 graph of this metric space is bipartite. Hence the distance-2 graph on a bipartite block is also distance-transitive, and in fact is isomorphic to the distance-1 graph of the universal homogeneous metric space.

We can combine this variation with the previous one to produce a homogeneous metric space of diameter n in which all triangles have even perimeter. For n = 3, the distance-1 graph is the universal almost-homogeneous bipartite graph (see Section 4).

Remark. This construction is similar, but not identical, to one due to Komjath et al. [18], who constructed a countable universal graph omitting odd cycles up to some fixed length. No doubt, further such variations are possible.

Third variation. The upper bound for d(x, y) is always at least 2, so we are never forced to prescribe d(x, y) = 1. Hence, for fixed m, the class of integral metric spaces containing no m points mutually at distance 1 has the amalgamation property, and we obtain a distance-transitive K_{m}-free graph. We can combine this with a diameter bound of n as in the first variation. For n = 2, we obtain Henson’s homogeneous K_{m}-free graph.

6 Homogeneous coboundaries

In this section, we construct some further distance-transitive graphs as covers of complete or complete bipartite graphs. These covers are defined by universal homogeneous coboundaries, which we now define.

Let Λ be an abelian group, fixed throughout most of the discussion. For any graph Γ = (V, E), an oriented cycle in Γ is an n-tuple (x_{0}, …, x_{n−1}) (up to cyclic permutation) for which {x_{i}, x_{i+1}} is an edge for i = 0, …, n − 1 (the subscripts taken mod n). Its reflection is obtained by reversing the order. It is induced if it contains no other edges.

For k = 0, 1, 2, we define a k-cochain on Γ to be a function from vertices, directed edges, or oriented induced cycles respectively to Λ, where if k = 1 we require that reversing the direction of the edge changes the sign of the function, and if k = 2 we require that reflecting the cycle changes the sign. We denote by C^{k} the set of k-cochains; it is an abelian group under pointwise operations.

A k-cochain f on Γ defines a relational structure on V, with a relation R_{α} for each α ∈ Λ. For k = 1, the relations are given by

(x, y) ∈ R_{α}  ⇔  f(x, y) = α,

with a similar definition for k = 0. For k = 2, we need a family of relations for each α, one for each possible length of an induced cycle in Γ. It is clear what automorphisms, amalgamation, and homogeneity should mean.

There are homomorpisms called coboundary maps δ^{k} : C^{k} → C^{k+1} for k = 0, 1, given by

δ^{0}f(x, y) = f(y) − f(x) for f ∈ C^{0},
δ^{1}f(x_{0}, …, x_{n−1}) = f(x_{0}, x_{1}) + … + f(x_{n−1}, x_{0}) for f ∈ C^{1}.

We denote the kernel and image of δ^{k} by Z^{k} and B^{k+1} respectively, and call their elements k-cocycles and (k + 1)-coboundaries respectively.

A simple calculation shows that δ^{1}δ^{0} = 0, so that B^{1} ⊆ Z^{1}. In fact, equality holds. For suppose that f ∈ Z^{1}. Then the sum of the values of f on the edges of any oriented induced cycle is zero. The same holds for any cycle, since it can be decomposed into induced cycles, and the contributions of the additional edges cancel. So, if we choose a fixed basepoint x_{0} in each connected component, and define e(x) to be the sum of the values of f on the edges of a path joining the relevant basepoint x_{0} to x, then e(x) is well-defined, independent of path. It is clear that f = δ^{0}e ∈ B^{1}.

Similarly, any 1-cocycle which vanishes on the edges of a spanning forest F is zero, since any additional edge lies in a fundamental cycle with respect to F. Hence, two 1-cochains which have the same coboundary and agree on F are equal.

Consider, for example, the case where Λ is the cyclic group of order 2, say Λ = {0, 1}, and Γ is the complete graph. Then a 0-cochain is the characteristic function of a set of vertices, and a 1-cochain of a set of edges (which we can take to be the edge set of a graph on Γ). If e is a 0-cochain, then δ^{0}e is the edge set of a complete bipartite graph. Adding δ^{0}e to f is the same as switching the graph corresponding to f with respect to the set of vertices corresponding to e. Thus, switching classes are cosets of Z^{1} in C^{1}, and are mapped bijectively by δ^{1} to 2-coboundaries, that is, to two-graphs (see Section 7).

Let f be a 1-cochain on Γ. We define a graph Γ_{f} as follows: the vertex set is V × Λ; the vertices (x, α) and (y, β) are adjacent in Γ_{f} if and only if f(x, y) = β − α. Then Γ_{f} is a cover of Γ, with covering projection p given by p(x, α) = x.

Suppose that f and f′ are 1-cochains with the same coboundary. Then they differ by a 1-cocycle. Since B^{1} = Z^{1}, this means that f′(x, y) = f(x, y) + e(y) − e(x) for some e ∈ C^{0}. Then the map

ϕ : (x, α) ↦ (x, α + e(x))

is easily checked to be an isomorphism from Γ_{f} to Γ_{f′}. So the cover is determined by a 2-coboundary, in other words, by a coset of Z^{1} in C^{1}.

The automorphisms are related as follows.

Proposition 6.1 (a) Let g be an automorphism of the 2-coboundary δ^{1}f. Then there is a 0-cochain e such that, for all x ∼ y, we have

f(xg, yg) = f(x, y) + e(y) − e(x).

(b) If e, f, g are as in (a), and α, β ∈ Λ, then there is an automorphism \overline{g} of Γ_{f} mapping (x, α) to (xg, β), given by

(y, γ)\overline{g} = (yg, e(y) − e(x) + γ + β − α).

Proof. Calculation.

Theorem 6.2 Let C denote the age of a countable homogeneous graph Γ, and assume that C has the strong amalgamation property. Then the set of 2-coboundaries on graphs in C has the strong amalgamation property. Hence, if Λ is finite or countable, then there is a unique countable homogeneous 2-coboundary on Γ.

Proof. First we show the following. If h is a 2-coboundary on B, A ⊆ B, and h|_{A} = δf, then there is an extension of f to a 1-cochain f′ on B with h = δf′. For let h = δf′′. Since f′′|_{A} and f have the same coboundary, f′′|_{A} = f + δe for some 0-cochain e. Extend e to a cochain e′ on B in any manner, and set f′ = f′′ − δe′. Then f′|_{A} = f and δf′ = δf′′ = h.

So suppose that we have 2-coboundaries h_{1}, h_{2} on B_{1} and B_{2}, and A ⊆ B_{1}, B_{2} such that h_{1} and h_{2} have the same restriction to A. As above, we can assume that h_{i} = δf_{i} for i = 1, 2, where f_{1} and f_{2} agree on A. Now amalgamate B_{1} and B_{2} over A with no additional intersection, and define f on C = B_{1} ∪ B_{2} by the rule that f|_{B_{i}} = f_{i} for i = 1, 2; then δf is the required strong amalgam.

If Λ is at most countable, then Fraïssé’s third condition holds. The other conditions are obvious.

It follows from the Theorem of Lachlan and Woodrow [20] that the ages of all countable homogeneous graphs do have the strong amalgamation property, except for unions of countably many finite complete graphs and their complements. However, only in two cases do we get distance-transitive graphs:

Theorem 6.3 Let n be a positive integer or ℵ_{0}. Let Λ be either C_{p}^{n} or ℚ^{n}. Let Γ be the countable complete graph, or the countable complete bipartite graph (with both parts infinite). Let h be the universal homogeneous 2-coboundary on Γ, with h = δ^{1}f. Then Γ_{f} is distance-transitive of diameter d and is (d − 2)-arc transitive, where d is the girth of Γ.

Proof. I give the argument for the complete graph; the complete bipartite graph is similar.

Since a 2-coboundary on an edge is trivial, the group preserving h is transitive on ordered edges. Now it is readily checked that (x, α) and (y, β) lie at distance 2 if and only if x ≠ y and f(x, y) ≠ β − α; and at distance 3 if and only if x = y and β ≠ α. (So the graph is antipodal of diameter 3). Now the stabiliser of (x, 0) in the automorphism group of h fixes all (x, α). So we have to find extra automorphisms.

These are provided by the group H = Aut(Λ), acting on the second coordinates of the vertices of Γ_{f}, by the rule

(y, β)^{σ} = (y, β^{σ} + f(x, y) − f(x, y)^{σ})

for σ ∈ Aut(Λ). The groups Λ of the theorem are precisely the finite or countable abelian groups for which Aut(Λ) acts transitively on the non-zero elements of Λ. So, immediately, we see that the vertices at distance 3 from (x, 0) form an orbit. Also, the stabiliser of (x, 0) acts transitively on the fibres {(y, β) : β ∈ Λ} for y ≠ x. Given a fibre, the group Aut(Λ) fixes (y, f(x, y)) (the unique vertex in the fibre adjacent to (x, 0)) and acts transitively on the other vertices. So Γ_{f} is indeed distance-transitive.

Remark. In the case where Γ is complete, the graph Γ_{f} has the property that the induced subgraph on the neighbourhood of any point is the random graph.

Remark. It is easy to see that no other homogeneous graph has a universal coboundary giving rise to a distance-transitive cover. For if the girth of Γ is d, then the antipodal cover has diameter d, and so any geodesic in Γ must be contained in a d-cycle, whence Γ has diameter at most d/2.

Suppose we want to find a distance-transitive cover of Henson’s universal homogeneous triangle-free graph H by this method. The induced cycles in Henson’s graph have length 4 or 5, and the above argument shows that the coboundary must vanish on all 4-cycles. This easily implies that it takes a constant value α on 5-cycles, and that α is an involution (so we may suppose that Λ is the cyclic group of order 2). The resulting cover is the Cartesian product H × K_{2}, which we noted in Section 4.

7 Further two-graphs

The covers described in Section 6 are very special, except in the case |Λ| = 2: any double cover of a graph is of this form. This is because there are only two ways to join two fibres of size 2 by disjoint edges, and these correspond to the two possible values of f(x, y).

In particular, double covers of complete graphs correspond to two-graphs [24]. A two-graph on Ω is a 2-coboundary on the complete graph on Ω with values in ℤ/2. In other words, it is a set T of 3-subsets of Ω, with the property that any 4-set contains an even number of members of T.

The double cover is distance-transitive if and only if the two-graph admits a 2-transitive automorphism group. All finite 2-transitive two-graphs have been determined by Taylor [26]. Apart from sporadic examples, these are associated with vector spaces, either of fixed dimension over arbitrary finite fields (those admitting PSL(2, q), PSU(3, q), or ^{2}G_{2}(q)), or of arbitrary even dimension over a fixed field (those admitting Sp(2n, 2) or 2^{2n} : Sp(2n, 2)). These have infinite analogues, constructed in the same way. In fact, the methods of [6] for constructing more general covers of complete graphs admitting classical groups of Lie rank 1 also work more generally.

Examples with no finite analogues are less common. There is a countable universal homogeneous two-graph, otherwise the universal homogeneous 2-coboundary over ℤ/2 on the complete graph. The vertex neigbourhood is the random graph R. It can also be constructed as the coboundary of R, where a graph is regarded as a 1-cochain on the complete graph, edges and non-edges corresponding to values 1 and 0 respectively. Thus, it is a reduct of the random graph, one of the five reducts appearing in Thomas’ classification [27].

Two further examples are constructed from trees. They depend on the following two constructions of two-graphs from trees [7]:

• Take Ω to be the edge set of a tree. A triple of edges is in T if and only if the smallest subtree containing these edges contains a trivalent vertex.

• Colour the internal vertices black and white. Now take Ω to be the set of leaves of the tree; a triple of leaves is in T if and only if the trivalent vertex of the smallest tree containing the three leaves is black.

The two classes of two-graphs are the ages of two countable, almost-homogeneous (and in particular, 2-transitive) two-graphs, and hence give rise to two distancetransitive double covers of complete graphs. They can be characterised by forbidden substructures: the pentagon and hexagon in the first case, the pentagon in the second. (These are the two-graphs which are the coboundaries of the 5-cycle and 6-cycle graphs.)

8 Circular structures

The next class of examples is based on the unit circle. In order to obtain countable graphs, we will use the countable analogue of the unit circle, the set Ω of all complex roots of unity. The group of permutations preserving the cyclic order on this set is transitive on k-sets for all k (Cameron [2]).

Let n be an integer greater than 1. We partition Ω into parts of size n, two points z and w belonging to the same part if and only if the argument of wz^{−1} is a multiple of 2π/n. (For n = 2, the equivalence classes are antipodal pairs.) A set Δ of representatives of the equivalence classes is good if it is dense in Ω. Good sets exist uniquely:

Proposition 8.1 (a) If we choose representatives of the equivalence classes randomly, the resulting set is good with probability 1.

(b) Any two good sets are equivalent under a permutation of Ω preserving the cyclic order.

Now take Δ to be a good set. Then Δ carries the cyclic order induced from Ω. In addition, we define n binary relations R_{0}, R_{1}, …, R_{n−1} on Δ by the rule that (z, w) ∈ R_{j} if and only if

2πj/n < arg(wz^{−1}) < 2π(j + 1)/n.

By our choice of Δ, each pair of distinct points satisfies R_{j} for a unique value of j. The converse of R_{j} is R_{n−1−j}. The structure Δ, equipped with the relations R_{0}, …, R_{n−1} and the circular order, is homogeneous.

Not also that the set Δ is equivalent to its reflection; so there is a permutation of Δ which interchanges each relation with its converse (and reverses the circular order).

For n = 2, the relations R_{0} and R_{1} form a converse pair of tournaments, isomorphic to each other. Lachlan [19] showed that there are exactly three finite homogeneous tournaments: this one, the transitive tournament ℚ, and the Fraïssé limit of the class of all finite tournaments.

For n = 3, the isomorphic converse digraphs R_{0} and R_{2} arise as a sporadic example in Cherlin’s classification of homogeneous digraphs [8]. The relation R_{1} is self-converse, and hence is a graph. It is not homogeneous, but Droste et al. [10] showed that it has the weaker property of being set homogeneous: this means that, if two finite induced subgraphs A and B are isomorphic, then some automorphism of the graph carries A to B. These authors showed, moreover, that if a countable graph is 8-set homogeneous (this means that the above condition holds for subgraphs A and B with at most 8 vertices) but not 3homogeneous, then it is isomorphic to the graph R_{1} or its complement R_{0} ∪ R_{2}.

These examples generalise. For any n, consider the graph R_{0} ∪ R_{n−1}. The ends of a path of length d have angular separation less than 2πd/n, and so are in the relation R_{j} or R_{n−1−j} for j < d. It follows that the graph has diameter ⌈n/2⌉ and is distance-transitive. Also, if n is odd, say n = 2m + 1, consider the graph R_{m} (whose edges join points at greatest angular distance). Then a path of length 2k joins points in the relation R_{j} or R_{2m−j} for j ≤ k, while a path of length 2k + 1 joints points in the relation R_{m+j} or R_{m−j} for j ≤ k. So again the graph has diameter m + 1 and is distance-transitive.

The relation of these two distance-transitive graphs on the same set of vertices (for n odd) resembles that of the Johnson graph J(m, 2m+1) and the ‘odd graph’ O_{m+1} in the finite case.

I do not know whether there are higher-dimensional analogues of these graphs, with a sphere replacing the circle.

9 Hrushovski’s graphs

Some of the most remarkable distance-transitive graphs to have been found are described by the following theorem.

Theorem 9.1 For every natural number d, there are 2^{ℵ_{0}} non-isomorphic countable graphs which have diameter d and girth 2d, and are distance-transitive, d-arc transitive, and ℵ_{0}-categorical.

I will not give a complete proof of this theorem, but will follow the original construction of Hrushovski [16]. To get the theorem as stated, a bit more work is needed; this is due to David Evans (personal communication).

The graphs I consider are Hrushovski’s graphs H^{α} for suitable α. Hrushovski discovered a very powerful strengthening of Fraïssé’s method for constructing countable structures by amalgamation. In his variant, not all amalgamations are required, but only those where the bottom structure has a certain closure property. Hrushovski never published the precise result described here, though he did use similar methods for other purposes in model theory [16]. A survey, including these graphs in a more general context, can be found in the article by Wagner [28]. Hrushovski’s graphs have diameter d and have just two orbits on pairs of vertices at distance d; they are (d − 1)-arc transitive.

I will give a brief account. This is a description, rather than a construction, of the graphs, since no account of the proof of Hrushovski’s theorem is attempted. Let V X and EX denote the vertex and edge sets of the graph X. For an irrational number α in (1/2, 1), we define δ(X) = |V X| − α|EX|. We define a function f by

• k(n) is the greatest rational approximation to 1/α from below with denominator not exceeding n;

• c(n) = ∑_{i=1}^{n−1} k(i);

• f(n) = n − αc(n).

We choose an irrational α such that f is unbounded. (The set of such α is residual, so we can find one arbitrarily close to any prescribed value.)

Hrushovski’s graph H^{α} has the property that its age C^{α} consists of all graphs X such that, for all induced subgraphs X′ of X, we have δ(X′) ≥ f(|V X′|) (equivalently, |E(X′)| ≤ c(|V X′|)).

A finite graph X ∈ C^{α} is closed if X ⊂ Y ∈ C^{α} implies δ(X) ≤ δ(Y). (We can take strict inequality here: the irrationality of α means that if graphs have different numbers of vertices, the values of δ are different.) Now, if X is closed, then any embedding X ⊂ Y in the age can be realised inside H^{α}; and any isomorphism between closed subgraphs can be extended to an automorphism. The first property means that the closure of X depends only on its isomorphism type: it is closed if any Y in the age properly containing it has δ(Y) > δ(X). We can this think of “closed” as meaning “closed in H^{α}”.

Since f(n + 1) − f(n) = 1 − αk(n), with k(n) < 1/α, we see that f is strictly increasing. So any graph X on the boundary of the age, that is, with δ(X) = f(|V X|), is closed. For example, if α > (d − 1)/d, then k(n) = 1 for n ≤ d, whence c(n) = n − 1. Thus every tree on at most d vertices is closed. In particular, H_{α} is (d − 1)-arc transitive.

It is trivial that δ(X ∪ Y) + δ(X ∩ Y) ≤ δ(X) + δ(Y), with equality if and only if there are no edges from X \ Y to Y \ X. Using this, one shows that, if A and B are closed, so is A ∩ B. So the closure of X, written cl(X), is the unique smallest closed subgraph containing X. Moreover, we have

f(| cl(A)|) ≤ δ(cl(A)) ≤ δ(A);

since f is unbounded, it follows that the size of the closure of a set is bounded.

We take α to lie in the interval

(d − 1)/d < α < (2d − 1)/(2d + 1).

We first examine how the functions k, c and n behave. First, since 1 + 2/(2d − 1) < 1/α < 1 + 1/(d − 1), we have:

\begin{matrix}Range & k(n) \\ n ≤ d − 1 & 1 \\ d ≤ n ≤ 2d − 2 & 1 + 1/d \\ 2d − 1 ≤ n ≤ 2d & 1 + 2/(2d − 1) \end{matrix}

From this, we deduce:

\begin{matrix}Range & c(n) & f(n) \\ n ≤ d & n − 1 & n − (n − 1)α \\ d + 1 ≤ n ≤ 2d − 1 & n − 1 + (n − d)/d & n − (n − 1 + (n − d)/d)α \\ n = 2d & 2d + 1/d(2d − 1) & 2d(1 − α) − α/d(2d − 1) \\ n = 2d + 1 & (2d + 1)(1 + \frac{1}{d(2d−1)}) & (2d + 1)(1 − (1 + \frac{1}{d(2d−1)})α) \end{matrix}

From the values of c(n), we see that ⌊c(n)⌋ = n − 1 for n ≤ 2d − 1. So the graphs on at most 2d − 1 vertices in the age are forests, and conversely. However, ⌊c(2d)⌋ = 2d, so the age contains a 2d-cycle. We conclude that the girth of the graph is 2d.

To determine the orbits of the automorphism group on pairs of vertices, we have to compute the closure of a pair of vertices. If X is an edge, then X is closed, as noted above; so the automorphism group is transitive on (ordered) edges.

Now let X be a non-edge. Then δ(X) = 2, so the closure A of X satisfies δ(A) < 2. We have f(2d + 1) = (2d + 1)(1 − (1 + 1/d(2d − 1))α > 2 (by our choice of α < d(2d − 1)^{2}/(d − 1)(2d + 1)^{2} — note that (2d − 1)/(2d + 1) < d(2d − 1)^{2}/(d − 1)(2d + 1)^{2}). So the closure of X has at most 2d vertices. Moreover, if Y is a tree on d + 2 vertices, then δ(Y) = 2 + 1/(2d + 1) > 2, so if A is a tree then it has at most d + 1 vertices. If a path on d + 1 vertices is not closed, then its closure is a 2d-cycle. So the closure of a non-edge is either a path of length at most d or a 2d-cycle. All cases occur. (We have seen that a path of length at most d − 1 is closed. A cycle C on 2d vertices is closed since, as we have seen, δ(C) < 2 but f(n) > 2 for n > 2d.)

It follows that Γ^{α} has diameter d and girth 2d and is (d − 1)-arc transitive, as asserted.

The graphs H^{α} for different values of α have different ages, and so are nonisomorphic.

As noted earlier, Evans has modified this construction to produce such a graph which is distance-transitive. In Evans’ graph, it is possible for a nonadjacent pair of vertices to be closed: this happens if and only if the vertices lie at distance d. Note that, since such a graph E are distance-transitive with diameter d and girth 2d, and contain an induced (2d + 1)-cycle, it follows as for Henson’s triangle-free graph that E × K_{2} is a distance-transitive double cover of E with diameter 2d + 1.

References

[1] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer, Berlin, 1989.

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

[3] P. J. Cameron, 6-transitive graphs, J. Combinatorial Theory (B) 28 (1980), 168–179.

[4] P. J. Cameron, There are only finitely many distance-transitive graphs of given valency greater than 2, Combinatorica 2 (1982), 9–13.

[5] P. J. Cameron, Oligomorphic Permutation Groups, London Math. Soc. Lecture Notes 152, Cambridge University Press, Cambridge, 1990.

[6] P. J. Cameron, Covers of graphs and EGQs, Discrete Math. 97 (1991), 83–92.

[7] P. J. Cameron, Two-graphs and trees, Discrete Math. 127 (1994), 63–74.

[8] G. L. Cherlin, Homogeneous directed graphs, pp. 81–95 in Finite and Infinite Combinatorics in Sets and Logic (ed. N. W. Sauer, R. E. Woodrow and B. Sands), Kluwer, Dordrecht, 1993.

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

[10] M. Droste, M. Giraudet, H. D. Macpherson and N. Sauer, Set-homogeneous graphs, J. Combinatorial Theory (B) 62 (1994), 63–95

[11] M. Droste and H. D. Macpherson, On k-homogeneous posets and graphs, J. Combinatorial Theory (A) 56 (1991), 1–15.

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

[13] A. D. Gardiner, Homogeneous graphs, J. Combinatorial Theory (B) 20 (1976), 94–102.

[14] P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and interval graphs, Canad. J. Math. 16 (1964), 539–548.

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

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

[17] O. H. Kegel and A. Schleiermacher, Amalgams and embeddings of projective planes, Geometriae Dedicata 2 (1973), 379–395.

[18] P. Komjath, A. H. Mekler and J. Pach, Some universal graphs, Israel J. Math. 64 (1988), 158–168.

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

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

[21] M. W. Liebeck, The affine permutation groups of rank 3, Proc. London Math. Soc. (3) 54 (1987), 477–516.

[22] H. D. Macpherson, Infinite distance-transitive graphs of finite valency, Combinatorica 2 (1982), 63–69.

[23] A. H. Mekler, Homogeneous partially ordered sets, pp. 279–288 in Finite and Infinite Combinatorics in Sets and Logic (ed. N. W. Sauer, R. E. Woodrow and B. Sands), Kluwer, Dordrecht, 1993.

[24] J. J. Seidel, A survey of two-graphs, pp. 481–511 in Proc. Internat. Coll. Teorie Combinatorie (Roma 1973), Accad. Naz. Lincei, Roma, 1977.

[25] D. H. Smith, Primitive and imprimitive graphs, Quart. J. Math. Oxford (2) 22 (1971), 551–557.

[26] D. E. Taylor, 2-graphs and doubly transitive groups, J. Combinatorial Theory (A) 61 (1992), 113–122.

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

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

[29] R. M. Weiss, The non-existence of 8-transitive graphs, Combinatorica 1 (1981), 309–311.

[30] R. M. Weiss, On distance-transitive graphs, Bull. London Math. Soc. 17 (1985), 253–256.

Peter J. Cameron

School of Mathematical Sciences Queen Mary and Westfield College

Mile End Road London E1 4NS

U.K.