Graph

There is a unique strongly regular graph Γ with parameters v = 275, k = 112, λ = 30, μ = 56. The spectrum is 112¹ 2²⁵² (–28)²². The complementary graph has parameters v = 275, k = 162, λ = 105, μ = 81 and spectrum 162¹ 27²² (–3)²⁵². Uniqueness is due to Goethals & Seidel (1975). For a detailed discussion see Brouwer & van Lint (1984).

Group

The full group of automorphisms of Γ is G = McL.2 (of order 2⁸.3⁶.5³.7.11) acting rank 3, with point stabilizer U₄(3):2.

Construction

A 22+77+176 construction is found by taking the Steiner system S(4,7,23) with 1+22 points and 253 = 77+176 blocks, where the first 77 are those containing the first point. Use p,B,C to denote one of the 22, 77, 176 objects, and let ~ denote adjacency. Make the 22 remaining points a coclique, let p ~ B when p is not in B, let B ~ B' when B,B' meet in 1 point, let p ~ C when p is in C, let B ~ C when B,C meet in 3 points, let C ~ C' when C,C' meet in 1 point. This yields Γ. The resulting partition is equitable with parameters (0,56,56), (16,16,80), (7,35,70).

The same construction in other words: Take the 23 points and 253 blocks of S(4,7,23), with points forming a coclique, p ~ B when p is not in B, and B ~ B' when B,B' meet in 1 point. This yields a graph on 276 vertices that is member of the switching class of a regular two-graph. Now switch one point isolated (and delete it) to get Γ. See also h) below.

Subgraphs

We give the substructures of Γ associated to the 11 maximal subgroups of G not containing McL, sorted according to increasing orbit size.

a) Vertices. There are 275 of these, forming a single orbit. The stabilizer of one (in the full automorphism group) is U₄(3):2 with vertex orbit sizes 1+112+162. The graphs induced on the first and second subconstituent are described separately.

b) 22-cocliques. There are 4050 of these, forming a single orbit. The stabilizer of one is M₂₂ with vertex orbit sizes 22+77+176. The graph induced on the 77 is the M₂₂-graph.

c) Pairs of Hoffman-Singleton graphs. Γ has an orbit of splits 50+50+175 where the 50's induce the Hoffman-Singleton graph and the 175 induces the graph on the edges of the Hoffman-Singleton graph, adjacent when they are disjoint and lie in the same pentagon. This latter graph is strongly regular with parameters (v,k,λ,μ) = (175,72,20,36). If one takes the union of the two 50's and switches on this split one obtains the Higman-Sims graph. The stabilizer of a split 50+50+175 is U₃(5):2, where the outer 2 interchanges the two 50's. There are 7128 such splits. *** Other HoSi's in Γ? ***

d) 5-cliques. There are 15400 of these, forming a single orbit. The stabilizer of one is 3₊¹⁺⁴:4S₅ with vertex orbit sizes 5+270.

e) Edges. There are 15400 of these, forming a single orbit. The stabilizer of one is 3⁴:(M₁₀ × 2) with vertex orbit sizes 2+30+81+162. The graph induced on the 81 is the VO^–₄(3) graph.

f) Non-edges. There are 22275 of these, forming a single orbit. The stabilizer of one is L₃(4):2² with vertex orbit sizes 2+56+105+112. The graph induced on the 56 (the common neighbours) is the Gewirtz graph.

g) Odd graphs. Γ contains an orbit of 22275 Odd graphs O₄. The stabilizer of one is 2.S₈ with vertex orbit sizes 35+240. There are other subgraphs O₄ in Γ since the local graph also contains such graphs. *** Any further Odd subgraphs? ***

h) Maximal 7-cocliques. There are 44550 of these, forming a single orbit. The stabilizer of one is 2⁴:A₇ with vertex orbit sizes 7+16+112+140. The 16 here is a maximal 16-coclique. (This is what one gets from the regular two-graph construction after switching a block isolated and deleting it.)

i) Maximal 11-cocliques of the first kind. There are 113400 of these, forming a single orbit. Γ has three orbits of maximal 11-cocliques. The first has stabilizer 2 × M₁₁, with vertex orbit sizes 11+22+110+132. The 11 is a maximal 11-coclique, the 22 a (nice) 11K₂. (There is a unique nice 11K₂ on each 2K₂, but there are many others as well.) The other two orbits of maximal 11-cocliques have stabilizers of order 12 and 36, not transtive on the coclique.

j) Splits 125+150. Γ has an orbit of splits 125+150 with stabilizer 5₊¹⁺²:3:8:2 with vertex orbit sizes 125+150. The 125 induces a rank 5 strongly regular graph with parameters (v,k,λ,μ) = (125,52,15,26).

k) 3-Cocliques. There are 779625 of these, forming a single orbit. The stabilizer of one is 2²⁺⁴:(S₃×S₃) with vertex orbit sizes 3+8+32+64+72+96. The orbit of size 8 induces a K_4,4.

Cliques

The largest cliques have size 5. At first sight it looks like Γ might be the collinearity graph of a partial geometry with 28 lines of size 5 on each point. However, this possibility has been ruled out by Östergård & Soicher (2016).

Cocliques

The largest cocliques have size 22. Numbers of maximal cocliques of given size (with orbit sizes):

7: 44550
10: 13721400 = 1247400 + 12474000
11: 199697400 = 113400 + 49896000 + 149688000
13: 43659000 = 6237000 + 37422000
16: 757350 = 44550 + 712800
22: 4050

The largest cocliques in the line graph have size 11 (and there are 254016000 of these, 181440 on each edge, 2240 on each pair of disjoint edges).

Chromatic number

The complement of Γ has chromatic number 55. That is, Γ has a partition into 55 5-cliques. (Haemers & Tonchev)

References

A. E. Brouwer & J. H. van Lint,
Strongly regular graphs and partial geometries,
pp 85-122 in: Enumeration and Design - Proc. Silver Jubilee Conf. on Combinatorics, Waterloo, 1982, D.M. Jackson & S.A. Vanstone (eds.), Academic Press, Toronto, 1984.

J.-M. Goethals & J. J. Seidel,
The regular two-graph on 276 vertices,
Discr. Math. 12 (1975) 143-158.

W. H. Haemers & V. D. Tonchev,
Spreads in strongly regular graphs,
Designs, Codes and Cryptography 8 (1996) 145-157.

Patric R. J. Östergård & Leonard H. Soicher,
There is No McLaughlin Geometry, arXiv:1607.03372, Jul 2016.