Up

The O6(3) graph

There is a unique strongly regular graph Γ with parameters v = 112, k = 30, λ = 2, μ = 10. The spectrum is 301 290 (–10)21. This graph is the collinearity graph of the unique generalized quadrangle GQ(3,9). (Any strongly regular graph with the parameters of the collinearity graph of a GQ(q,q2) necessarily is one, by Cameron-Goethals-Seidel (1978). And GQ(3,9) is unique by Dixmier-Zara (1976).)

Group

The full group of automorphisms of Γ is G = U4(3).D8 (of order 210.36.5.7) acting rank 3, with point stabilizer 34:((2×A6).22). This group is PGO*6(3) where the * denotes that the form may be multiplied by a constant. [Is there no standard name for this group?]

Construction

Γ is the graph on the 112 isotropic points of the O6(3) geometry, adjacent when orthogonal, i.e., joined by a totally isotropic line.

Γ can also be described as the graph on the 112 totally isotropic lines of the GQ(9,3) on 280 points defined by U4(3), adjacent when they meet.

Or again: In the Steiner system S(5,8,24), take all 112 blocks starting 110... or 101...; join two blocks of the same kind when they have only two symbols in common, and join two blocks starting differently when they have four symbols in common. This yields Γ (and shows that it has a split into two Gewirtz graphs).

Supergraphs

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

Subgraphs

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

a) Vertices. There are 112 of these, forming a single orbit. The stabilizer of one (in the full automorphism group) is 34:((2 × A6).22) with vertex orbit sizes 1+30+81. The second subconstituent VO4(3) (on 81 vertices) is again strongly regular, with parameters (81,20,1,6). It is the graph on the vectors of a 4-dimensional vector space over GF(3), where two vectors are adjacent when the quadratic form vanishes on their difference.

b) Subquadrangles. There are 252 subquadrangles GQ(3,3) (namely, the subgraphs induced on the perp of a nonisotropic point), forming a single orbit. The stabilizer of one is U4(2):2×2 = PGO5(3)×2. The vertex orbit sizes are 40+72.

c) Lines. There are 280 4-cliques (namely, the totally isotropic lines), forming a single orbit. The stabilizer of one is 3+1+4.21+4.D12. The vertex orbit sizes are 4+108.

d) Splits into two Gewirtz graphs. Γ has 324 splits into two Gewirtz graphs, forming a single orbit. The stabilizer of one split is L3(4).22, and the stabilizer of one Gewirtz graph is L3(4).2, of index 2 in the full automorphism group of the Gewirtz graph. (Indeed, in the McLaughlin graph Λ we find Γ as the set of neighbours of a vertex x, and the Gewirtz graph as the set of common neighbours of two nonadjacent vertices x, y. The stabilizer in McL:2 of {x,y} is the full group of the Gewirtz graph, and the subgroup obtained by fixing both x and y has index 2 in it.)

There are 648 Gewirtz subgraphs, 324 on each point, 108 on each edge, 180 on each nonedge, 36 on each path of length 2, 12 on each K1,3, 4 on each quadrangle. The intersection sizes are 0 or 56 (1x), 16 or 40 (42x), 20 or 36 (56x), 24 or 32 (105x), 28 (240x). When two Gewirtz subgraphs C, D have nonempty intersection K, then C and D are the only Gewirtz subgraphs on K in Γ. If the intersection K has size u, then the graph induced on K is regular of valency (u–16)/4. Fixing C and varying D we find all the 16-cocliques, half of the 10 K2, all the 6 C4, and half of the Coxeter graphs in C.

Equivalent to a split of the isotropic points of O6(3) into two Gewirtz graphs is a collection of 315 elliptic lines, precisely one in each tangent plane with a single isotropic point. Thus, there are 324 such collections.

In the U4(3) generalized quadrangle, this object is equivalent to a collection of 315 K4,4's (induced on the union of two orthogonal hyperbolic lines), precisely one on each edge. Such objects are visible inside the Patterson graph.

e) Regular spreads. A nonisotropic point in the U4(3) geometry determines a unital on its perp: 28 isotropic points, pairwise not joined by a totally isotropic line. In the orthogonal geometry this corresponds to a regular spread: a partition of the 112 isotropic points into 28 totally isotropic lines, such that any two of these lines determine a regulus: 4 lines in an O+4(3). There are 540 nonisotropic points in the unitary geometry, forming a single orbit. The stabilizer of one is (U3(3) × 4):2.

There are lots of other spreads: each time we see a regulus, we can replace its four lines by the other four in their union and obtain a new spread. Or, in unitary terms, we can replace a hyperbolic line by its perp and obtain a new ovoid. However, there are also spreads without any regulus.

#reguli  #spreads  comment
63       540       regular, 1 orbit
31       34020     obtained from regular by a single switch, 1 orbit
15       680400    510300 obtained by double switch
9        30240
7        952560
6        1088640
4        1088640
3        2721600
2        3265920
1        1905120
0        5961600
total    17729280

f) Bases. If we choose the quadratic form Σ Xi2, then we see a subgroup 25:S6. There are 567+567 = 1134 bases, of mutually orthogonal nonisotropic points all of the same kind, forming a single orbit under PGO*6(3); for PGO6(3) they split into two orbits (all points with Q(x)=1 and all points with Q(x)=2). The point stabilizer is 25:S6. In terms of the isotropic points these bases determine subgraphs (of vectors of "weight" 6) of size 32. (They are the distance-3 graphs of folded 6-cubes, distance-regular with intersection array {10,9,4;1,6,10}.) All subgraphs with array {10,9,4;1,6,10} arise in this way. These subgraphs are bipartite, and their halves form the 2268 maximal 16-cocliques.

g) Elliptic lines. The orthogonal geometry has 2835 elliptic lines, forming a single orbit. The stabilizer of one is 4(S4×S4).22. In terms of the isotropic points the elliptic lines are the O+4(3) subgeometries.

h) Hyperbolic lines or nonedges. The orthogonal geometry has 4536 hyperbolic lines, forming a single orbit. In terms of the graph on the isotropic points the hyperbolic lines are the nonedges (and give a vertex partition 2+10+40+60). A hyperbolic line has two isotropic points, one point with Q(x)=1 and one point with Q(x)=2. Therefore, fixing a hyperbolic line in PGO6(3) implies fixing a nonisotropic point, and the group is not maximal. But in PGO*6(3) the stabilizer (A6.22 × 2).2 is maximal.

i) Odd graphs or maximal 7-cocliques. Our graph contains an orbit of 5184 Odd graphs O4. This is most easily seen by viewing the orthogonal geometry as elliptic hyperplane in the O7(3) geometry. That latter geometry can be described using the form Σ Xi2, and the point (1,1,1,1,1,1,1) is elliptic. In its perp we see 112 = 7 + 35 + 70 points (7: 1111110; 35: 1110000; 70: 1112220), where the 7-set is a maximal coclique and the 35-set induces the Odd graph O4, the unique distance-regular graph with intersection array {4,3,3;1,1,2}. The stabilizer of a 7-coclique (or of an O4) is S7. There are no other maximal 7-cocliques. *** Are there any other Odd subgraphs? ***

j) Triples of mutually orthogonal elliptic lines. There are 8505 triples of mutually orthogonal elliptic lines, forming a single orbit. An elliptic line has two points with Q(x)=1 and two with Q(x)=2, and hence a triple of mutually orthogonal elliptic lines determines a unique basis consisting of points with Q(x)=1, and a unique basis consisting of points with Q(x)=2. It follows that the stabilizer of a triple of mutually orthogonal elliptic lines is nonmaximal in PGO6(3). However, it is maximal in PGO*6(3), with stabilizer 43(2×S4) = 25.23.S3.2.

k) Unitary elliptic quadrics and even cocliques The graph on the 280 totally isotropic lines, adjacent when they meet, has 9072 10-cocliques with the property that each point outside is adjacent to 0 or 2 points inside. These form a single orbit (but split into two orbits of size 4536 with stabilizer M10 for U4(3)). These 10-cocliques can be seen as elliptic quadrics:

The U4(3) geometry is defined by a nondegenerate Hermitean form over GF(9). When restricted to vectors with coordinates in GF(3), the form becomes a quadratic form. This means that this geometry contains O+4(3) and O4(3) substructures. The former becomes a pair of orthogonal nondegenerate planes, but each such plane has three elliptic points, and a pair of orthogonal nondegenerate planes is equivalent to a split of a basis into 3+3. Thus, the corresponding subgroup is not maximal. The latter becomes a set of ten pairwise disjoint lines such that each t.i. line hits 0 or 2 of them.

Cocliques

From the information on the maximal cocliques in the second subconstituent we immediately derive the numbers of maximal cocliques of a given size here. There are 5184 maximal 7-cocliques (see also under i)), 766584 maximal 10-cocliques, 3447360 maximal 11-cocliques, 816480 maximal 12-cocliques, 181440 maximal 13-cocliques, and 2268 maximal 16-cocliques (see also under f)).

Chromatic number

This graph has chromatic number 8. Indeed, 8 suffices since there is a split into two Gewirtz graphs and Gewirtz has chromatic number 4. And 7 does not suffice: there is no partition of the point set into seven 16-cocliques.

References

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

S. Dixmier & F. Zara, Etude d'un quadrangle généralisé autour de deux de ses points non liés, preprint, 1976.

S. Dixmier & F. Zara, Essai d'une méthode d'étude de certains graphes liés aux groupes classiques, C. R. Acad. Sci. Paris (A) 282 (1976) 259-262.