The Graph Extension Theorem

I made some notes on the Graph Extension Theorem for a new research project. They may be of wider interest, so here is a summary.

Shult’s Graph Extension Theorem is a simple device for showing that certain permutation groups have transitive extensions, and for constructing these extensions. It is not completely general – that is, it will not construct transitive extensions of arbitrary groups – but it is very easy to apply. Among the examples it constructs are the Higman–Sims group and Conway’s third group.

Shult published his Graph Extension Theorem in 1972. For a simple graph Γ (with no loops, multiple edges or directed edges), let Γ(v) be the set of vertices w for which {v,w} is an edge, and Γ*(v) the set of vertices x (different from v) for which {v,x} is not an edge.

Theorem Let Γ be a simple graph on the vertex set V, whose automorphism group G acts transitively on V. Let v be a vertex. Suppose that there is a permutation π of V with the properties

• π fixes {v}, Γ(v) and Γ*(v) setwise;
• π induces automorphisms of the induced subgraphs on Γ(v) and Γ*(v) – that is, it maps edges within either of these sets to edges and non-edges to non-edges;
• if x∈Γ(v) and y∈Γ*(v), then {x,y} is an edge if and only if {π(x),π(y)} is a non-edge.

Let ∞ be a point not in V, and let σ be the permutation of V∪{∞} which interchanges ∞ with v and acts on the remaining points as π. Then G and σ generate a transitive extension of G (that is, a 2-transitive group in which and the stabiliser of ∞ is G).

The final section of this note will explain why the theorem is true (but based on ideas of Higman and Seidel rather than Shult’s original proof).

Here is an example. Let Γ be a 5-cycle, with vertex set {0,1,2,3,4}; its automorphism group is the dihedral group of order 10 generated by a=(0,1,2,3,4) and b=(0)(1,4)(2,3) (or, as affine maps of the integers mod 5, a:x→x+1 and b:x→−x). Now let π be the permutation (0)(1)(4)(2,3). It is readily checked that π satisfies the conditions of the Graph Extension Theorem. So, with σ=(∞,0)(1)(4)(2,3), we see that ⟨G,σ⟩ is a transitive extension of G. Indeed, since σ is the linear fractional map x→1/x, we see that ⟨G,σ⟩ is the linear fractional group PSL(2,5).

Remark The conditions on π in the Graph Extension Theorem can be formulated in a different way. Given a graph Γ with a vertex v, let Γ*_v be the graph with the same vertex set as Γ, and the same edges incident with v, or within Γ(v), or within Γ*(v), but with edges between the last two sets replaced by non-edges, and non-edges replaced by edges.

Then a permutation π has the required properties if and only if it is an isomorphism between Γ and Γ*_v fixing v.

In particular, if Γ has vertex-transitive automorphism group, and Γ*_v is isomorphic to Γ, then π exists, and so Aut(Γ) has a transitive extension.

Remark Aside from other applications, the Graph Extension led to a characterisation of symplectic and orthogonal geometries over GF(2) by Shult, which was re-worked by Seidel and led directly to the Buekenhout–Shult axiomatisation of polar spaces. I may return to this at some point.

Some applications

Conway’s group Co₃

I begin with a “metaphysical” construction of the group Co₃.

In the paper in which he announced his sporadic group, McLaughlin constructed it as a transitive extension of PSU(4,3), acting with two orbits having lengths 112 and 162. He constructed a graph with vertex set the union of these two orbits and one extra vertex v. Edges join v to all vertices in the orbit of lengths 112; edges within the two orbits are given by specified orbital graphs. Finally, PSU(4,3) has two orbits on pairs (x,y) with x in one orbit and y in the other; McLaughlin chooses one of these to be edges in his graph, and the other to be non-edges. He remarks that the isomorphism class of the graph does not depend on the orbit chosen. He then shows that the automorphism group of the graph is vertex-transitive; this is McLaughlin’s sporadic group.

Now if one choice of orbit gives a graph Γ, then the other clearly gives Γ*_v. So McLaughlin’s claim implies that these two graphs are isomorphic, and so that the permutation required by the Graph Extension Theorem exists. Thus McLaughlin’s group has a transitive extension, which happens to be Conway’s group Co₃.

The fact that the graph was independent of the choice of orbit was puzzling at the time; in some sense the Graph Extension Theorem “explains” it.

The groups PSL(2,q), for q≡1 (mod 4)

Now a more hands-on example, a generalization of our introductory example.

Let q be a prime power congruent to 1 (mod 4). Then −1 is a square in
the field GF(q). Construct a graph P(q) whose vertex set is GF(q),
in which vertices x and y are joined if and only if y−x is a square
in the field. Since −1 is a square, this graph is undirected; it is the
Paley graph. It is vertex-transitive, admitting the group

G = {x→ax+b : a,b∈GF(q),a a non-zero square}.

Indeed, its full automorphism group is generated by G and field automorphisms.

Consider the map π which fixes 0 and acts as x→1/x on the remaining vertices. We claim that π satisfies the conditions of the Graph Extension Theorem. Clearly it maps squares to squares and non-squares to non-squares, so the first condition holds. For the others, observe that

1/y−1/x = −(y−x)/xy,

so the difference 1/y−1/x has the same quadratic character as y−x if x and y are both squares or both non-squares, but opposite character if one is a square and the other a non-square.

So the Graph Extension Theorem applies. Indeed, the map σ of the theorem is x→1/x, and ⟨G,σ⟩=PSL(2,q).

The Higman–Sims group

The Higman–Sims group was constructed by D. G. Higman and Sims as a permutation group on 100 points, as a transitive extension of an intransitive action of the Mathieu group M₂₂ having orbit lengths 22 and 77. The construction is simple – almost certainly the simplest construction of any sporadic simple group. Soon afterwards, G. Higman constructed a sporadic simple group of the same order as a 2-transitive group on 176 points; it was not until later that several people, including Parrott and Wong, Smith, and Sims, showed that the two groups were isomorphic (as had been suspected right from the start).

Graham Higman’s construction can be rephrased as an application of the Graph Extension Theorem, which is what I want to outline here. This is not complete; I do not know yet how to produce the permutation π.

We begin a long way back, with the outer automorphism of the symmetric group S₆. This can be described as follows. The group S₆ has two different actions on sets A and X of cardinality 6, in such a way that a transposition of A acts as a product of three transpositions on X, and vice versa. I will write, for brevity, {a,b}∼{x,y} if (x,y) is a cycle in the permutation of X corresponding to the transposition (a,b) of A. (In Sylvester’s idiosyncratic terminology, in which a duad on A is a pair of points, a syntheme a partition of A into duads, and a synthematic total a partition of the duads into synthemes – and similarly for X – it can be shown that duads on A correspond to synthemes on X and vice versa; our relation asserts that {x,y} is a part of the syntheme on X corresponding to the duad {a,b}.)

Now construct a graph H as follows. Let A and X be above, and take two new symbols α and χ. The vertex set of the graph is {α,χ}∪A∪X∪(A×X). Edges are as follows:

• {α,χ};
• {α,a} for all a∈A;
• {χ,x} for all x∈X;
• {a,(a,x)} and {x,(a,x)} for all a∈A and x∈X;
• {(a,x),(b,y)} for all a,b∈A, x,y∈X such that {a,b}∼{x,y}.

It can be shown that the automorphism group of this graph is the group PΣU(3,5), and is vertex-transitive and edge-transitive. The stabiliser of an ordered edge is the group S₆ visible in the above construction; the stabiliser of an unordered edge is Aut(S₆); and the stabiliser of a vertex is S₇.

The graph H is the Hoffman–Singleton graph. It has a special place in graph theory. A Moore graph of diameter 2 is a regular graph with diameter 2 and girth (length of shortest cycle) 5. It is regular; if its valency is k, then the total number of vertices is k²+1. There are unique examples for k=2 (the 5-cycle) and k=3 (the Petersen graph). Hoffman and Singleton, using linear algebra methods, showed that a Moore graph could exist only for k=2, 3, 7 and (possibly) 57; they constructed the Moore graph of valency 7 and proved its uniqueness. The possible graph of valency 57 is still unknown, though it is known that there can be no vertex-transitive graph of this form.

Now construct a graph Γ as follows. The vertex set of Γ is the set of (undirected) edges of H. We see from the above construction that there are three possible relationships between two distinct edges e₁ and e₂:

• they intersect;
• they are disjoint, but there is an edge e₃ joining a vertex of e₁ to a vertex of e₂ (the girth-5 property shows there cannot be more than one such edge);
• they are disjoint, and there is no edge as in the previous point.

Counting shows that, given e₁, the number of edges e₂ in each possible relation to it are 12, 72 and 90 respectively. We join two vertices of Γ by an edge if (as edges of H) they are in the second relation above.

This graph admits PΣU(3,5) as a transitive rank-4 group of automorphisms. I claim that the Graph Extension Theorem applies, giving a transitive extension of this group; this transitive extension is the Higman–Sims group. But I don’t yet have a nice construction for the permutation π.

Two-graphs and graph switching

In this section I will explain why the Graph Extension Theorem is true. The ideas here were introduced by Graham Higman for a (different) construction of the group Co₃; Higman did not apply them to his own construction of HS. At about the same time, Jaap Seidel was producing a different version of this material, coming from equidistant point sets in elliptic geometry (aka equiangular lines in Euclidean space): he subsequently wrote several surveys.

A two-graph is a pair (X,Δ), where X is a set and Δ a collection of 3-element subsets of X with the property that any 4-element subset contains an even number of members of Δ. The reason for calling it a “two-graph” will be described below; in hypergraph theory this would be a special kind of 3-graph.

Let Γ be a graph with vertex set X. Then we obtain a two-graph (X,Δ), where Δ is the set of 3-sets containing an odd number of edges of the graph (that is, inducing a subgraph consisting of either a triangle, or an edge and an isolated vertex). Call this two-graph T(Γ).

Given a graph Γ with vertex set X, the operation of switching Γ with respect to a set Y of vertices consists of replacing all edges betwen Y and X\Y by non-edges and all non-edges by edges, leaving edges and non-edges within Y and within X\Y untouched. Switching is an equivalence relation on the set of all graphs on the vertex set X: for if σ_Y denotes the switching operation just described, then σ_Yσ_Z = σ_Y⊕Z, where ⊕ denotes symmetric difference. The equivalence classes are called switching classes.

Theorem

• Every two-graph has the form T(Γ) for some graph Γ.
• Let Γ₁ and Γ₂ be graphs on the vertex set X. Then T(Γ₁)=T(Γ₂) if and only if Γ₁ and Γ₂ are equivalent under switching.

It follows that a permutation π of X is an automorphism of the two-graph (X,Δ) if and only if it maps a graph in the corresponding switching class to a graph in the same switching class. In particular, Aut(Γ) is a subgroup of Aut(T(Γ)).

The proof of the theorem is not difficult, but it has a simple interpretation in terms of algebraic topology. Let |X|=n. Then a two-graph (or, strictly, its characteristic function t) is a 2-cochain on the (n−1)-simplex with values in Z₂; the defining condition shows that it is actually a 2-cocycle (that is, its coboundary is zero). Since the cohomology of the simplex vanishes, t is the coboundary of a 1-chain, that is, the characteristic function of the set of edges of a graph; this is part (a) of the theorem. Now two graphs are cohomologous (that is, have the same coboundary) if and only if they differ by a 1-cocycle; again, the vanishing of cohomology shows that a 1-cocyle is the coboundary of a 0-cochain, that is, a subset Y of X. So a 1-cocycle is the edge set of the complete bipartite graph between Y and its complement; and adding a 1-cocyle to a graph (mod 2) translates as switching, in the sense just described.

Now suppose that Γ is a graph which satisfies the hypotheses of the Graph Extension Theorem. Let ∞ be a new point, and regard Γ as a graph on V∪{∞} having ∞ as an isolated vertex. Let Γ’=σ_Γ(v)Γ, the graph obtained by switching Γ with respect to the set Γ(v). Switching removes edges from v to Γ(v), and puts in all possible edges from ∞ to Γ(v); it also maps edges between Γ(v) and Γ*(v) to non-edges and non-edges to edges. In other words, the permutation σ=(∞,v)π is an isomorphism from Γ to the switching-equivalent graph Γ’, and so belongs to the automorphism group of the corresponding two-graph. So ⟨G,σ⟩ is a subgroup of Aut(T(Γ)).

On the other hand, it is easily seen that there is a unique graph in the switching class having ∞ as an isolated vertex, namely Γ; so any automorphism of T(Γ) fixing ∞ is an automorphism of Γ.

We conclude that ⟨G,σ⟩ is a transitive extension of G, as claimed.

Remark A two-graph arising as in the Graph Extension Theorem has a 2-transitive automorphism group, and hence has the property that any two points lie in a constant number λ of 3-sets in Δ. Following Higman, we call a two-graph with this numerical property regular.

Regularity has a couple of consequences. Assume that Δ is not complete or null.

• Any 3-set in Δ lies in a constant number μ of 4-sets all of whose 3-sets are in Δ, with |X| = 3λ−2μ. For take {a,b,c}∈Δ, and let μ denote the number of 4-sets {a,b,c,x} all of whose 3-subsets are in Δ. For any point x∉{a,b,c}, there are two possibilities:
  • All three of {a,b,x}, {b,c,x}, {a,c,x} belong to Δ: there are μ such points.
  • exactly one of these three sets belongs to Δ. For each of the three choices, there are λ−μ−1 choices.

  So μ+3(λ−μ−1) = n−3, giving n = 3λ−2μ as required. In particular, μ is independent of the chosen set {a,b,c}.

• n is even. For consider the complementary set Δ’ of 3-subsets. It is also a regular two-graph, so has associated parameters λ’ and μ’, with n = 3λ’−2μ’. Now
  2n = 3(λ+λ’)−2(μ+μ’) = 3(n−2)−2(μ+μ’),
  so n = 2(μ+μ’+3) is even, as claimed.

Remark There are other interpretations of two-graphs, for example, as sets of equiangular lines in Euclidean space. Note that our introductory example corresponds to the six diagonals of the icosahedron in R³; triples of lines are of two types, according as whether or not vectors can be chosen along the lines so that their pairwise angles are all acute. The triples of either type form the two-graph. The procedure is quite general; the two-graph admitting Co₃ is represented by a set of 276 equiangular lines in R²³ which can be found in the Leech lattice.