A Survey of Distance-Transitive Graphs
by Arjeh M. Cohen
last update Aug 2001
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.
Starting point is the following
Let X = (V,E)
be a primitive distance-regular graph with a
group G of automorphisms. Assume k, d >2.
Then one of the following holds.
X is a Hamming graph and G is a wreath product;
G is almost simple (nonabelian);
G has an elementary abelian normal subgroup which is regular
(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.
Here the graph X is well known, although the
the group G are not completely determined.
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:
- 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:
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
For soc(G) of
exceptional Lie type, work in preparation by Cohen, Liebeck, and Saxl
(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
There exists a short list of hard cases not yet dealt with.
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,
([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.
- X is a Hamming graph;
- X is a Bilinear Forms graph;
- V is 1-dimensional and H is a subgroup of GamL(1,s);
- The generalized Fitting subgroup F*(H/Z(H GL(V))) of
H/Z(H GL(V)) is simple, its projective representation on V is
irreducible and can be realized over no proper subfield of
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
- The bound |V| < 5 |H| +1 (by
John van Bon).
- If dim(FrV) = c,
then H has at most c orbits in V.
- 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
Remains the case where G0 is a group of Lie type
defined over the same characteristic as the vector space V:
- 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).
- 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.