Cameron graph

There is a rank 4 strongly regular graph Γ with parameters v = 231, k = 30, λ = 9, μ = 3. The spectrum is 30¹ 9⁵⁵ (–3)¹⁷⁵. It is the unique strongly regular graph with these parameters that is a gamma-space with lines of size 3.

Construction

The vertices are the (22 choose 2) = 231 pairs from a fixed 22-set S provided with a fixed Steiner system S(3,6,22). Two pairs are adjacent when they are disjoint and their 4-point union is contained in a block.

Group

The automorphism group is M₂₂.2 of order 887040, acting rank 4 with point stabilizer 2⁵:Sym(5).

Gamma space

This graph is the collinearity graph of a partial linear space with lines of size 3, namely the triples of pairs that partition a block of the Steiner system. This geometry is a gamma space: given a line L, each point outside L is collinear to 0, 1, or 3 points of L. It has Fano subplanes, 10 on each point and 2 on each line. The 15 lines and 10 planes on a fixed point form the edges and vertices of the Petersen graph. We see a GQ(2,2) subgeometry on each block.

Triple cover

This graph has a triple cover on 693 vertices with full group 3.M₂₂.2.

Subgraphs

a) A symbol. Γ has 2765664 21-cocliques falling in 29 orbits of sizes 22, 352, 2310, 4620, 5280, 12320, 18480, 21120, 24640, 27720, 36960 (5x), 49280 (2x), 73920, 110880 (2x), 147840 (5x), 221760 (2x), 443520 (2x). Since 21 is the Hoffman bound on the size of a coclique, these cocliques are maximal, and each vertex outside one has 3 neighbours inside. For two of these 29 orbits the stabilizer of a coclique is transitive on its 21 vertices. These are precisely the two orbits of cocliques with a stabilizer that is maximal in Aut(Γ). These orbits have lengths 22 and 352. A coclique in the former is called a symbol, one in the latter a heptad (see c below). There are 22 symbols, forming a single orbit. The stabilizer of one is L₃(4).2 with vertex orbit sizes 21+210.

b) A quad. Γ has 77 quads, subgeometries GQ(2,2), forming a single orbit. The stabilizer of one is 2⁴:S₆ with vertex orbit sizes 15+120+96.

c) A heptad. There are 352 of these (21-cocliques, see above), forming a single orbit. The stabilizer of one is A₇ with vertex orbit sizes 21+105+105 (the pairs in the heptad, meeting the heptad in 1 symbol, and those outside the heptad).

d) A vertex. There are 231 of these, forming a single orbit. The stabilizer of one is 2⁵:S₅ with vertex orbit sizes 1+30+160+40. The relation defined by the orbit of size 40 is the triangular graph T(22).

The local graphs are 2-clique extensions of the line graph of the Petersen graph.

e) A Fano plane. There are 330 of these, maximal 7-cliques on which the lines induce a Fano plane, forming a single orbit. The stabilizer of one is 2³.L₃(2) x 2 with vertex orbit sizes 7+28+84+112. These are the only maximal cliques.

f) A decad / Sylvester subgraph / GO(2,1). Let our S(3,6,22) be obtained by deriving S(5,8,24) twice, so that there are two outside symbols a and b. There are 1288 splits of the set of 24 symbols into two dodecads. Of these splits, 616 have a and b on the same side, and 672 have them on different sides. Let a decad be a set of ten symbols that together with a and b form a dodecad. There are 616 decads, forming a single orbit. The stabilizer of one is A₆.2² (of order 1440) with vertex orbit sizes 30+36+45+120. On the orbit of size 36 Γ induces a Sylvester graph. On the orbit of size 45 Γ induces a GO(2,1) (generalized octagon of order (2,1), the flag graph of GQ(2,2), on 45 = 1+4+8+16+16 vertices).

g) An undecad / L2(11) subgraph. Let an undecad be a set of eleven symbols that together with a or b form a dodecad. There are 672 of these forming a single orbit. The stabilizer of one is L₂(11):2 with vertex orbit sizes 55+66+110. The graph induced on the orbit of size 55 has valency 6 and point stabilizer S₄, see L₂(11) on 55.

References

A. E. Brouwer, Uniqueness and nonexistence of some graphs related to M₂₂, Graphs Combin. 2 (1986) 21-29.

J. I. Hall & S. V. Shpectorov, P-geometries of rank 3, Geom. Dedic. 82 (2000) 139-169.