A Survey of Distance-Transitive Graphs

by Arjeh M. Cohen

last update Aug 2001

Preface

This is a survey of the state of the art of the classification of primitive distance transitive graphs. It might help to carry out the remainder of the work, as sketched at the DTG workshop in Eindhoven, December 1998. The open cases are listed in three tables, to be found from within the text below.

Introduction

Starting point is the following

Theorem ([PSY]). Let X = (V,E) be a primitive distance-regular graph with a distance-transitive group G of automorphisms. Assume k, d >2. Then one of the following holds.

  1. X is a Hamming graph and G is a wreath product;
  2. G is almost simple (nonabelian);
  3. G has an elementary abelian normal subgroup which is regular on V.

(See [VBt] for another proof.) The theorem shows how to use the classification of finite simple groups for the determination of all primitive distance-transitive graphs. In view of the determination of all rank 3 groups (see e.g. [L3] ), we may assume diam X > 2. We discuss the three cases individually.

Case i.

Here the graph X is well known, although the possibilities for the group G are not completely determined.

Case ii. G almost simple

The classification of finite simple groups can be invoked to make a further subdivision according to the possibilities for soc(G). Knowledge of the maximal subgroups of soc(G) should then help to finish. If G is distance transitive with stabilizer subgroup H, then its permutation character 1HG is multiplicity free. This gives a method of ruling out several cases. The study of such permutation representations was initiated by Jan Saxl [SI]. The case soc G = Altn (n > 4) is dealt with in [I1] and in [LPS]; PSL(n,q) is handled in [vBCl]. It uses [ILS] to rule out certain representations which are not multiplicity free. For soc(G) sporadic, the possible graphs X are determined in [ILLSS]. Remain the Chevalley groups:
  1. Case ii.classical For soc(G) of classical Lie type, work was started by John van Bon, Nick Inglis and Jan Saxl in 1990, [vBIS1]. The idea was to use Aschbacher's list of subgroups of classical groups in [A] in combination with the results in the Kleidman-Liebeck book [KL]. Two papers are in preparation: [BISmf], handling the question which permutation representations are multiplicity free, and [vBIS2], handling all cases of (natural linear representations of) dimension n > 8. Thus, the smaller dimensions remain. Several series are dealt with in the two papers mentioned. But the following cases are open (so far)

    Look here for a table summarizing the classical work in progress

  2. Case ii.exceptional For soc(G) of exceptional Lie type, work in preparation by Cohen, Liebeck, and Saxl [CLS] (since 1985) should do the work. The idea of proof is to use results of Liebeck and Saxl determining the maximal groups of relatively small index; a case by case study for each of these groups will then be conducted. There exists a short list of hard cases not yet dealt with. For example, A7(2) in E7(2). Ross Lawther has dealt with some cases.

    Look here for a table summarizing the exceptional work in progress

Case iii. G affine

Here V can be identified with an Fs vector space V for some prime power s = rb, maximal with respect to H = G0 in GamL(V), where G0 is the stabilizer in G of 0 in V. The assumption that X is primitive amounts to the action of H on V being irreducible. By Van Bon's thesis we can roughly reduce to the case where H = G0 is almost simple. More precisely,

Theorem ([vBt, vBp]) Let G be an affine group acting primitively and distance-transitively on a connected noncomplete graph X of valency and diameter at least three. Then, with Fs, V, and H as above, we have one of the following.

  1. X is a Hamming graph;
  2. X is a Bilinear Forms graph;
  3. V is 1-dimensional and H is a subgroup of GamL(1,s);
  4. The generalized Fitting subgroup F*(H/Z(H GL(V))) of H/Z(H GL(V)) is simple, its projective representation on V is absolutely irreducible and can be realized over no proper subfield of Fs.

In the first two cases, the graphs are fully determined. Case three is dealt with in [CI].

Remains Case iii.4.

Again, we invoke the classification of finite simple groups. The general technique here is to use
  1. The bound |V| < 5 |H| +1 (by John van Bon).
  2. If dim(FrV) = c, then H has at most c orbits in V.
  3. A result (by John van Bon) taking care of the case where Fq* is contained in Aut(X) and H' leaves invariant a unitary or orthogonal form on V, see [vBMP].

For soc H = Altn (n > 4), the analysis of affine dtg is completed in [LP]. In case G0 is a group of Lie type of characteristic distinct from the scalar field of V, the classification has been dealt with in [CMS]. In case the group G0 is sporadic, the classification can be found in [vBIS]. Remains the case where G0 is a group of Lie type defined over the same characteristic as the vector space V:

  1. Case G0 is exceptional and of same characteristic as field of scalars. Theorem 12.4 of [vBt] gives a very restricted number of cases. John van Bon and Cohen have finished this case; there is a preprint [vBCe] (postscript version available).
  2. Case G0 is classical and of same characteristic as field of scalars. This runs in the same way as the previous case, see Theorem 12.7 of [vBt]. It is harder because more twisted cases (groups as well as modules) come in. Done by John van Bon, Arjeh Cohen and Hans Cuypers. Preprint available soon.