Up

# Suzuki graph

There is a rank 3 strongly regular graph Γ with parameters v = 1782, k = 416, λ = 100, μ = 96. The spectrum is 4161 20780 (−16)1001. It is one of the two graphs that are locally the G2(4) graph (Pasechnik, 1993), the other being the triple cover constructed by Soicher (1993), a distance-transitive graph with intersection array {416, 315, 64, 1; 1, 32, 315, 416}.

## Group

The full group of automorphisms is G = Suz.2 (of order 214.37.52.7.11.13), acting rank 3, with point stabilizer G2(4).2.

## Construction

A geometric construction was given in Brouwer et al. (2009).

## Subgraphs

We give the substructures of Γ associated to the 15 maximal subgroups of G distinct from Suz, sorted according to increasing orbit size.

a) A vertex.
There are 1782 of these, forming a single orbit. The stabilizer of one is G2(4).2 with vertex orbit sizes 1+416+1365. The subgraph induced on the first subconstituent is the G2(4) graph, which is strongly regular with parameters (v,k,λ,μ) = (416,100,36,20).

b) A U4(3) graph on 162 vertices.
Each element g of Atlas type 3A of Suz fixes 162 vertices of Γ and Γ induces a U4(3) graph on these 162-sets. These U4(3) graphs are strongly regular with parameters (v,k,λ,μ) = (162,56,10,24). There are 22880 of these (one for each subgroup <g> of G), forming a single orbit. The stabilizer of one is 32.U4(3).22133 with vertex orbit sizes 162+1620.
The graph on these 22880 subgraphs, adjacent when disjoint, that is, when the corresponding elements g commute, is the unique distance-regular graph with intersection array {280,243,144,10; 1,8,90,280}, known as the Patterson graph. (And distance 0, 1, 2, 3, 4 in the Patterson graph corresponds to intersection size 162, 0, 18, 12, 42 for these 162-sets.)
The 2080 U4(3) subgraphs on a vertex p induce the 2080 Gewirtz subgraphs in the G2(4) graph on the neighbours of p.

c) Nice splits 6297.
Γ has a unique orbit (of size 32760) of partitions of the vertex set into 297 maximal 6-cocliques such that the union of any two parts induces a regular subgraph of Γ. (There are many other partitions into 297 maximal 6-cocliques.) The stabilizer of one such partition is U5(2):2. Let (just here) C6@2 denote the 2-coclique extension of the hexagon. Then the union of any two parts of such a partition induces either 6K2 or C6@2. Each partition carries the structure of a rank 3 strongly regular graph with parameters (v,k,λ,μ) = (297,40,7,5), the collinearity graph of the generalized quadrangle GQ(8,4) that is the dual polar graph for U5(2), if we call two maximal 6-cocliques adjacent when their union induces C6@2.
The subgroup U5(2):2 of G (of index 32760) is transitive on the 1782 vertices, but has two orbits on the edges, giving a red subgraph of valency 160 and a green subgraph of valency 256. And three orbits on the nonedges (with valencies 1280, 80, and 5), the last of which gives our partition of the vertex set into 6-cocliques. The local graph of the red graph is the disjoint union of five 2-coclique extensions of the Clebsch graph.

d) A 2-coclique extension of the Schläfli graph.
There are 135135 of these, forming a single orbit. The stabilizer of one is 21+6.U4(2).2 with vertex orbit sizes 54+1728. The graph induced on the orbit of size 54 is the 2-coclique extension of the Schläfli graph. This graph has valency 32. Its local graph is the 2-coclique extension of the Clebsch graph. The mu-graphs of Γ consist of three copies of this graph on 32 vertices.

e) A 3-edge-coloring.
The subgroup 35:(M11×2) of G (of index 232960) is transitive on the 1782 vertices, but has three orbits on the edges, giving a red subgraph of valency 20, the disjoint union of 22 Brouwer-Haemers graphs, and a bipartite green subgraph of valency 36, and a blue subgraph of valency 360.
The 22 Brouwer-Haemers graphs are permuted by M11×2 acting rank 3 with suborbits 1+1+20. The 1+1 induces a U4(3) graph, as under b). Thus, Γ has partitions into 11 U4(3) graphs.

f) An edge.
There are 370656 of these, forming a single orbit. The stabilizer of one is J2:2 × 2 with vertex orbit sizes 2+100+630+1050.

g) A maximal 6-coclique.
There are 405405 of these, forming a single orbit. The stabilizer of one is 24+6:3S6 with vertex orbit sizes 6+240+1536. The vertices in the 240-orbit have 4 neighbours in the 6-coclique, those in the 1536-orbit have 1. Each maximal 6-coclique lies in 24 splits as under c). Each maximal 6-coclique lies in 64 U4(3) subgraphs, and the maximal 6-cocliques of each U4(3) subgraph remain maximal in Γ.
Each vertex lies in 1365 maximal 6-cocliques. Each nonedge lies in 5. Each non-edge xy lies in 1044 3-cocliques, on which the stabilizer has orbits of sizes 20+1024, see below under i). Each triple xyz with z in the orbit of size 20 lies in a unique maximal 6-coclique. No triple xyz with z in the orbit of size 1024 lies in a maximal 6-coclique.
There are no smaller maximal cocliques. The largest cocliques have size 66.

h) A nonincidence graph of PG(2,4).
There are 926640 of these, forming a single orbit. The stabilizer of one is (A4 × L3(4):23):2 with vertex orbit sizes 42+480+1260. The graph induced on the orbit of size 42 is the bipartite point-line nonincidence graph of PG(2,4).

i) A non-edge.
There are 1216215 of these, forming a single orbit. The stabilizer of one is 22+8:(S5 × S3) with vertex orbit sizes 2+20+96+640+1024. The orbit of size 20 is a K5×4 subgraph. The orbit of size 96 is the mu-graph of Γ.

j) A 792+990 split.
The subgroup M12.2 × 2 of G (of index 2358720) has vertex orbit sizes 792+990.

k) A 324+1458 split.
The subgroup 32+4:2(S4 × D8) of G (of index 3203200) has vertex orbit sizes 324+1458.

l) A K6,6.
There are 10378368 of these, forming a single orbit. The stabilizer of one is (A6:22×A5).2 with vertex orbit sizes 12+150+720+900.

m) A 72+270+1440 split.
The stabilizer of one is ((32:8) × A6).2 (of index 17297280) with vertex orbit sizes 72+270+1440 and valencies 26, 56 and 338, respectively. Each 72 has a partition into 12 6-cliques. For details, see Cliques, below.

n) A 26K2.
The subgroup L2(25).22 of G (of index 57480192) has vertex orbit sizes 52+130+300+650+650. The graph induced on the orbit of size 52 is 26K2.

o) A sub-Hoffman-Singleton graph.
The subgroup Sym(7) of G (of index 177914880) has vertex orbit sizes 42+120+210+210+360+420+420. The graph induced on the orbit of size 42 is the 2nd subconstituent of the Hoffman-Singleton graph, distance-regular with intersection array {6,5,1; 1,1,6}.

## Cliques

There is a single orbit of maximal cliques. They have size 6. The stabilizer is a non-maximal S6 × S3 of order 4320. Each K6 determines a unique 3K6. Each 3K6 determines a unique graph on 36 vertices of valency 20, union of two copies of 3K6, with a partition in six 6-cocliques. Each such graph determines a unique graph on 72 vertices of valency 26, union of two of the preceding, with group ((32:8) × A6).2, see m) above.

## Maximal cocliques

The smallest maximal cocliques have size 6 and form a single orbit, see above under g).

The largest cocliques have size 66 and form a single orbit (Kuzuta, cf. Brouwer et al., 2009). The stabilizer of one is U3(4):4 with vertex orbit sizes 1+65+416+1300. The 1716 points outside a 66-coclique all have 16 neighbours inside, and we find a 3-(66,16,21) design.

## Small cocliques

Γ has two orbits of 3-cocliques: the stabilizer of a nonedge xy has orbits 20+1024 on the vertices adjacent to neither x nor y. Call the 3-cocliques in the small orbit special. There are 8108100 special 3-cocliques, and the stabilizer of one is 24+6.31+2.22 with vertex orbit sizes 3+3+48+48+144+768+768 (the first the 3-coclique xyz itself, the others with 0, 3, 1, 2, 0, 1 neighbours in xyz, respectively).

If xyz is a special 3-coclique, then 48 vertices are adjacent to all three and the subgraph induced on this orbit of size 48 is 3K4×4.

There are 3+768 vertices (other than xyz) adjacent to none of xyz. If uvw is this orbit of size 3, then uvwxyz is a maximal 6-coclique, see above under g). All triples in uvwxyz are special. The common neighbours of xyzw together with xyzw themselves form a K5×4, see above under i).

If xyz is a nonspecial 3-coclique, then 21 vertices are adjacent to all three and the subgraph induced is 6K1+3K5. The 6K1 part of this has 6 common neighbours, and we find a K6,6, see above under l).

## Acknowledgement

Some remarks were contributed by Chen Wang.

## References

BCN, Section 13.7.

A. E. Brouwer, A. Jurišić & J. H. Koolen, Characterization of the Patterson graph, J. Algebra 320 (2008) 1878-1886.

A. E. Brouwer, N. Horiguchi, M. Kitazume & H. Nakasora, A construction of the sporadic Suzuki graph from U3(4), J. Comb. Th. (A) 116 (2009) 1056-1062.

D. Pasechnik, Geometric characterization of graphs from the Suzuki chain, Europ. J. Combin. 14 (1993) 491-499.

L. H. Soicher, Three new distance-regular graphs, Europ. J. Combin. 14 (1993) 501-505.

M. Suzuki, A simple group of order 448,345,497,600, pp. 113-119 in: Theory of finite groups, R. Bauer & C.-S. Sah (eds.), Benjamin, New York, 1969.