SGDs with doubly transitive automorphism group

Peter J. Cameron

Abstract Symmetric graph designs, or SGDs, were defined by Gronau et al. as a common generalisation of symmetric BIBDs and orthogonal double covers. This note gives a classification of SGDs admitting a 2-transitive automorphism group. There are too many for a complete determination, but in some special cases the determination can be completed, such as those which admit a 3-transitive group, and those with λ = 1. The latter case includes the determination of all near 1-factorisations of K_{n} (partitions of the edge set into subsets each of which consists of disjoint edges covering all but one point) which admit 2-transitive groups.

A symmetric graph design, or SGD, with parameters (n, X, λ, F), (where n and λ are positive integers and X and F are graphs on n vertices), is a set {X_{1}, …, X_{n}} of subgraphs of the complete graph on {1, …, n} having the following properties:

(a) X_{i} ≅ X for i = 1, …, n;

(b) X_{i} ∩ X_{j} ≅ F for i, j = 1, …, n, i ≠ j;

(c) any edge of K_{n} lies in exactly λ of the graphs X_{1}, …, X_{n}.

To avoid degenerate cases, we assume that X is neither the complete nor the null graph on n vertices. Symmetric graph designs generalise both symmetric BIBDs (symmetric 2-designs, the case where X = K_{k}, F = K_{λ}), and orthogonal double covers or ODCs (the case where λ = 2 and F is a single edge).

I refer to Gronau et al. [3] or Rosa [4] for elementary properties of SGDs. In particular,

• X has λ(n − 1)/2 edges;

• F has λ(λ − 1)/2 edges.

In this note I give a classification of SGDs admitting a doubly transitive automorphism group. There are too many of these designs for a complete list to be possible, so what follows is a structural description. By the complement of a SGD, I mean the structure obtained by replacing each X_{i} by its complement in K_{n}. I do not know whether this always gives another SGD, but it does so in the 2-transitive case.

The results of this note, except for Corollary 1, use the Classification of Finite Simple Groups.

Theorem 1 Let {X_{1}, …, X_{n}} be a SGD with parameters (n, X, λ, F) which admits a 2-transitive group G. Then, up to complementation, one of the following occurs:

(a) X has an isolated vertex and induces a vertex-transitive graph on the remaining vertices;

(b) X is K_{k} or K_{k,n−k}, with (n, k) = (11, 5) or (176, 50) or of the form ((q^{d} − 1)/(q − 1), (q^{d−1} − 1)/(q − 1)) with q a prime power and d ≥ 3;

(c) n = 2^{2rs} and X admits the group Sp(2r, 2^{s}) (or G_{2}(2^{s}), with r = 3) acting with orbit lengths 2^{2rs−1} ± 2^{rs−1};

(d) n = 176, and X is the Hoffman-Singleton graph or its complement on 50 vertices, or the union of one of these graphs with K_{50,126}.

Conversely, if we choose any graph in cases (b)–(d), or any graph admitting a vertex-transitive group which is the point stabiliser in a 2-transitive group, we obtain a SGD. Several interesting examples arise. For example, there are two 2-transitive SGDs for which X is the Petersen graph. One falls under case (a), with n = 11, since the point stabiliser in the 2-transitive group PSL(2, 11) is A_{5}, which acts on the Petersen graph. The second falls under case (c), with n = 16, since Sp(2, 4) ≅ A_{5}. The values of λ in the two cases are 3 and 2 respectively (so the second is an ODC). The example in (d) with X ≅ HS also has λ = 2 (and is an ODC).

It is not feasible to list all possibilities. However, we can do so for some subclasses, for example, the 3-transitive designs and the designs with λ = 1.

Corollary 1 If a SGD with parameters (n, X, λ, F) admits a 3-transitive automorphism group, then X is K_{n−1} or K_{1,n−1}.

A near 1-factorisation of the complete graph K_{n}, for n odd, is a partition of the edge set into n subsets each consisting of (n − 1)/2 pairwise disjoint edges (covering all the vertices but one). These subsets form a SGD with λ = 1. Each edge set is a near 1-factor. The next result complements the determination of the perfect 1-factorisations admitting 2-transitive groups by Cameron and Korchmáros [2].

Theorem 2 A near 1-factorisation which admits a 2-transitive group is one of the following:

(a) The point set is an elementary abelian group V of odd order, and the 1factors are of the form

f_{a} = {{x, y} : x + y = 2a, x ≠ y}.

(b) The points are those of the projective space PG(d, 2), and the 1-factors have

the form

f_{a} = {{y, z} : y, z, a are collinear}.

With this, we can complete the determination of 2-transitive SGDs with λ = 1.

Theorem 3 A SGD with λ = 1 admitting a 2-transitive automorphism group is either a near-factorisation or a projective plane.

For the case λ = 2 (orthogonal double covers), we have the following.

Theorem 4 Suppose that an orthogonal double cover of K_{n} with copies of X (a SGD with λ = 2) admits a 2-transitive group. Then one of the following holds:

(a) X is a star X_{1,n−2};

(b) X has an isolated vertex and is a union of cycles of fixed length on the remainder;

(c) (n, X) = (7, K_{4}), (11, K_{5}), (16, K_{6}), (16, P) or (176, HS), where P and HS denote the Petersen and Hoffman–Singleton graphs.

Case (a) occurs for all n. Case (b) is more restricted, but occurs, for example, for all prime powers q; the cycle length can be any divisor of q−1 which is greater than 2. Also, there are examples with cycles of length 3 arising from linear spaces with line size 4 with 2-transitive groups: these are the projective spaces PG(d−1, 3), with n = (3^{d} −1)/2, admitting PSL(d, 3), and two different unitals with n = 28, admitting the unitary and Ree groups. (The examples from affine spaces over GF(4) are already included in the preceding construction.) These account for all possible parameters; it would be possible to work out all the ODCs with a bit more effort.

We now give the proofs of these theorems. We begin with two preliminary results.

Lemma 1 There is no SGD for which X is a regular graph on n vertices.

Proof. The number of edges of X is (n − 1)λ/2 (see [4]). If X is regular with valency μ, then it has nμ/2 edges. So n − 1 divides μ, whence μ = 0 or n − 1 and X is null or complete. But these two degenerate cases were excluded.

Lemma 2 Let G be a 2-transitive permutation group of degree n, and let H be a subgroup of G of index at most n. Then H has at most two orbits. If it has two orbits, then

• the index of H is n;

• either H is a point stabiliser in G, or the translates of an H-orbit are the blocks of a symmetric BIBD;

• G permutes the right cosets of H 2-transitively by right multiplication.

This is a familiar result from permutation group theory. It can also be proved using Fisher’s Inequality and Block’s Lemma, since if H is intransitive, then the translates of an H-orbit are clearly the blocks of a BIBD.

Now let G be a 2-transitive automorphism group of a SGD, and let H be the subgroup fixing the graph X_{1}. Clearly H has index at most n. If H is transitive, then X_{1} is regular, contrary to Lemma 1. So, by Lemma 2, either H is a point stabiliser, or H is the stabiliser of a block in a symmetric BIBD.

Conversely, let G be 2-transitive, and let H be either the stabiliser of a point, or the stabiliser of a block of a symmetric BIBD admitting G. Let X_{1} be any H-invariant graph other than the complete or null graph, and let X_{1}, …, X_{n} be the images of X_{1} under G. Then {X_{1}, …, X_{n}} is a SGD: the fact that G acts 2-transitively both on vertices and on the set {X_{1}, …, X_{n}} guarantees this. In particular, the fact that the complement of a 2-transitive SGD is an SGD now follows.

Consider the case where H fixes the point 1 and acts transitively on the remainder. Then 1 is joined to none or all of the other points. By complementation, we may assume that the first alternative holds. This gives case (a) of Theorem 1.

In the other case, we use the classification of 2-transitive symmetric designs, which follows from the Classification of Finite Simple Groups (see [1]). The following cases occur, up to complementation.

(i) Projective spaces: n = (q^{d} − 1)/(q − 1), k = (q^{d−1} − 1)/(q − 1), where q is a prime power and d ≥ 3; and G contains PSL(d, q) (or d = 4, q = 2, and G = A_{7}).

(ii) Symplectic designs: n = 2^{2d}, k = 2^{2d−1} − 2^{d−1}, and either G contains 2^{2d}. Sp(2r, 2^{s}) with rs = d, or G contains 2^{2d}.G_{2}(2^{s}), with 3s = d.

(iii) A Paley design: n = 11, k = 5, G = PSL(2, 11).

(iv) Higman’s design: n = 176, k = 50, G is the Higman–Sims group.

(There is a small inaccuracy in case (ii), since Sp(4, 2) and G_{2}(2) are not simple but have simple subgroups of index 2 isomorphic to A_{6} and U_{3}(3) respectively; but any graph invariant under the subgroup is invariant under the whole group.)

In cases (i) and (iii), the block stabiliser has just three orbits on point pairs, namely the sets of pairs containing 2, 1 or 0 points of the block respectively; so, up to complementation, only the graphs listed in case (b) of the theorem arise. This is also true for (ii) if we use the full automorphism group 2^{2d}. Sp(2d, 2); but for proper subgroups, other graphs occur, as we have seen. Finally, in case (iv), the block stabiliser leaves invariant a Hoffman–Singleton graph on the block and has four orbits on pairs: edges and non-edges of this graph, and pairs with 1 or 0 points in the block. So Theorem 1 is proved.

Proof of Corollary 1. No symmetric BIBD can admit a 3-transitive group, and no graph except the complete and null graphs can admit a 2-transitive group.

Proof of Theorem 2. We use the division of 2-transitive groups according to the minimal normal subgroup, which is either elementary abelian and regular, or non-abelian simple. In the first case, an elementary argument suffices. The stabiliser of a point fixes the unique near 1-factor which omits that point, so the stabiliser of two points fixes an odd number of points altogether. Let the minimal normal subgroup be V, identified with a vector space over a prime field. Since the fixed point set S of the stabiliser of two points (one of which is 0) is a subspace, the characteristic is odd. Now the normaliser of the stabiliser of S is sharply 2-transitive on S. Let {x, y} be an edge of the 1-factor omitting 0. There is an element of G which fixes 0 and maps x to y It must map y to x and induce an involution on S. But in a sharply 2-transitive group of odd degree, the unique involution fixing 0 is given by v ↦ −v. So y = −x Since x was arbitrary, the near 1-factor omitting 0 has the form specified in Case (a) of the Theorem. The other near 1-factors are now obtained by translation.

In the second case, we examine the list of 2-transitive groups with nonabelian minimal normal subgroups. The only ones in which the 2-point stabiliser fixes an odd number of points are the groups PSL(d, 2) (and A_{7} of degree 15, a subgroup of PSL(4, 2)). So the conclusion of Case (b) holds.

Proof of Theorem 3. The graph X has (n−1)/2 edges. In Case (a) of Theorem 1, X is a near 1-factor, and Theorem 2 applies. Otherwise, n is odd, so Cases (c) and (d) are impossible; and in Case (b), it is clear that projective planes are the only examples.

Proof of Theorem 4. The argument is similar. In Case (a), if the distinguished vertex is joined to all others, then X is a star (since it has n−1 edges); otherwise, the valency of X is 2. The remaining cases require only a small amount of checking, except possibly for case (b). In this case, we can assume that X has 2^{2d−1} ± 2^{d−1} vertices and 2^{2d} − 1 edges; so 2^{2d−1} ± 2^{d−1} divides 2(2^{2d} − 1), whence d − 1 = 1.

References

[1] P. J. Cameron, Permutation groups, pp. 611–645 in Handbook of Combinatorics (ed. R. L. Graham, M. Grötschel and L. Lovász), Elsevier, Amsterdam, 1995.

[2] P. J. Cameron and G. Korchmáros, One-factorizations of complete graphs with a doubly transitive automorphism group, Bull. London Math. Soc. 25 (1993), 1–6.

[3] H.-D. O. F. Gronau, R. C. Mullin, A. Rosa and P. J. Schellenberg, Symmetric graph designs, submitted to J. Graph Theory.

[4] A. Rosa, Symmetric graph designs, talk at 23ACCMCC, Brisbane, 1998.