Up

Graph

There is a unique strongly regular graph Γ with parameters v = 162, k = 56, λ = 10, μ = 24. The spectrum is 561 2140 (–16)21. The complementary graph has parameters v = 162, k = 105, λ = 72, μ = 60 and spectrum 1051 1521 (–3)140. Uniqueness is due to Cameron, Goethals & Seidel (1978).

Group

The full group of automorphisms of Γ is G = U4(3).22133 (of order 29.36.5.7) acting rank 3, with point stabilizer L3(4):22.

Construction

Γ can be constructed as 1+56+105 by taking a point ∞, one of the three orbits of hyperovals (of size 56) in PG(2,4), and the 105 flags (p,L) of PG(2,4). Here ∞ is adjacent to the 56 hyperovals; two hyperovals are adjacent when disjoint; a hyperoval O is adjacent to a flag (p,L) when p is outside O and L meets O; two flags (p,L) and (q,M) are adjacent when p and q are distinct, and L and M are distinct, and p is on M or q on L. (For example: from the Golay code one gets S(5,8,24). From S(5,8,24) one gets S(3,6,22). The derived design is that of the 21 lines of PG(2,4), the residual that of the 56 hyperovals.)

Γ is the second subconstituent of the McL graph Λ on 275 vertices.

Γ can also be found inside the O–6(3) graph on 112 vertices. That graph contains 648 Gewirtz subgraphs forming a single orbit. The intersection sizes are 0 or 56 (1x), 16 or 40 (42x), 20 or 36 (56x), 24 or 32 (105x), 28 (240x), and meeting in 0, 20, 24, 32, 36 or 56 vertices is an equivalence relation with two equivalence classes of size 324. Pick one equivalence class. It consists of 162 complementary pairs (`splits'). These are the vertices of Γ. Call two splits adjacent when their parts meet in 20 or 36 vertices, and nonadjacent when they meet in 24 or 32. This yields the graph Γ. (In fact one sees inside the McL graph Λ that it is possible to find 162 representatives of the 162 splits such that any two representatives meet in either 20 or 32 vertices.)

Cover

Γ has an antipodal 3-cover constructed by Soicher. It is the unique distance-regular graph with intersection array {56,45,16,1; 1,8,45,56}, and is distance-transitive with group 3.U4(3).22 with point stabilizer L3(4).22. The suborbit sizes are 1+56+315+112+2. The second subconstituent of that graph is itself distance-regular (but not distance-transitive) on 315 vertices, with intersection array {32,27,8,1; 1,4,27,32}.

Supergraphs

Γ is the second subconstituent of the McL graph on 275 vertices.

Γ is a subgraph of the Suzuki graph on 1782 vertices.

Subgraphs

We give the substructures of Γ associated to the 13 maximal subgroups of G not containing U4(3), sorted according to increasing orbit size.

a) Splits 81+81. Γ has 112 splits into two VO–4(3) subgraphs, forming a single orbit. The stabilizer of one is 34:(2 × M10). (How does one find all VO–4(3) subgraphs? By searching the 21-dimensional eigenspace for eigenvectors that are 1 on the subgraph and –1 on the complement. The result is that these 112 are the only splits of Γ into two subgraphs of valency 20.)

b) Vertices. There are 162 of these, forming a single orbit. The stabilizer of one is L3(4):22 with vertex orbit sizes 1+56+105. The 56 induce a Gewirtz graph. The 105 are the flags of PG(2,4). where two flags (p,L) and (q,M) are adjacent when p,q are distinct and L,M are distinct, and p is on M or q on L. The induced subgraph is strongly regular with parameters (105,32,4,12) and group L3(4).D12 acting rank 4.

c) Pairs of 21-cocliques. There are 162 of these pairs of 21-cocliques, forming a single orbit. The stabilizer of one is L3(4):22 with vertex orbit sizes 42+120. Γ has 324 21-cocliques forming a single orbit. The stabilizer of one is L3(4):2 with vertex orbit sizes 21+120+21, where both 21-sets are 21-cocliques, forming a pair. Their union of is distance-regular with parameters {16,15,5;1,12,16}, the nonincidence graph of points and lines of PG(2,4). The 120 can be identified as one orbit of Fano subplanes of this PG(2,4), adjacent when they meet in 1 point (and 1 line).

d) Splits 627. Γ has one orbit (of size 252) of partitions of the vertex set into 27 maximal 6-cocliques. The stabilizer of one is U4(2):2, transitive on the 162 vertices. The union of two maximal 6-cocliques in one such partition induces either 6K2 or the 2-coclique extension of a hexagon. If we call them adjacent in the first case, then we find the Schläfli graph on the 27 maximal 6-cocliques in one partition. There are many other partitions of the vertex set into 27 maximal 6-cocliques, but if we call two maximal 6-cocliques compatible when their union induces a regular graph, then these are the only partitions into 27 mutually compatible maximal 6-cocliques.

e) Splits 54+54+54. Γ has 280 splits into three copies of the same graph on 54 vertices, forming a single orbit. The stabilizer of one is 3+1+4.2–1+4.S3, transitive on the 162 vertices. (There are 15120 triangles, forming a single orbit. Each triangle determines a unique subgraph 9K3, and there are 1680 such subgraphs, forming a single orbit. Each subgraph 9K3 has a unique partner, disjoint from the first, such that each of its vertices has two neighbours in each of the nine K3's of the first, and we find 840 54-point subgraphs of valency 20. Each of these 54-point subgraphs is disjoint from precisely two others and there is an element of order 3 that permutes the three.)

f) U3(3) graphs. Γ has 540 subgraphs isomorphic to the U3(3) graph on 36 points, forming a single orbit. The stabilizer of one is (U3(3):2) × 2. *** check: no further such subgraphs? ***

g) Maximal 6-cocliques. There are 1134 of these, forming a single orbit. The stabilizer of one is (24:A6).2 = 24.S6. with vertex orbit sizes 6+60+96.

h) 2-coclique extension of K3×K3. There are 2835 subgraphs isomorphic to the 2-coclique extension of K3×K3, forming a single orbit. The stabilizer of one is 2.((S4 × S4):2 × 2) with vertex orbit sizes 18+144.

i) Edges. There are 4536 of these, forming a single orbit. The stabilizer of one is A6.22 × 2 with vertex orbit sizes 2+10+60+90. The orbit of size 10 is the first of the orbits of 10-cocliques.

j) K6,6's of the second kind. Γ has two orbits of K6,6 subgraphs: one of size 18144 with stabilizer A6.2 and vertex orbit sizes 12+30+120, and one of size 4536 with stabilizer A6.22 × 2 and vertex orbit sizes 12+60+90. (The former is found inside 42+120 (see c): the K6,6 is the subgraph of the nonincidence graph of PG(2,4) formed by a hyperoval O and the dual hyperoval of lines disjoint from O.)
The two groups found under i) and j) are conjugate in U4(3).D8 and intersect U4(3) in a maximal subgroup.

k) Splits 72+90. There are 4536 splits of Γ into two subgraphs of sizes 72 and 90, with valencies 26 and 32. *** check: not more such splits? *** They form a single orbit. The stabilizer of one is A6.22 × 2 with vertex orbit sizes 72+90. For A6, the orbit of size 72 splits into 36+36, where each 36 carries a Sylvester graph. For A6, the orbit of size 90 splits into 45+45, where each 45 carries the distance-2 graph of the incidence graph of GQ(2,2).

l) Maximal 15-cocliques of the first kind. Γ has two orbits of maximal 15-cocliques. The first orbit has size 5184 and stabilizer A7 with vertex orbit sizes 15+42+105. (The second orbit has size 38880 and stabilizer 2 × L(3,2) with vertex orbit sizes 1+14 on the 15-coclique, and 1+7+7+14+14+21+42+56 on all 162 points.)

m) Nonedges. There are 8505 of these, forming a single orbit. The stabilizer of one is (42 × 2)(2 × S4) with vertex orbit sizes 2+8+24+64+64. The orbit of size 8 induces a K4,4.

Cocliques

The largest cliques have size 3. The largest cocliques have size 21. Numbers of maximal cocliques of given size (with orbit sizes): 
6: 1134
9: 498960 = 90720 + 408240
10: 7987896 = 4536 + 362880 + 1088640 + 3265920 + 3265920
12: 2063880 = 22680 + 408240 + 544320 + 1088640
15: 44064 = 5184 + 38880
21: 324

Chromatic number

This graph has chromatic number 10 (Soicher (2018)).

References

P. J. Cameron, J.-M. Goethals & J. J. Seidel, Strongly regular graphs having strongly regular subconstituents, J. Algebra 55 (1978) 257-280.

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

L. H. Soicher, Cliques and colourings in GRAPE, talk in Novosibirsk, Aug. 2018.