G2(4) graph

There is a rank 3 strongly regular graph Γ with parameters v = 416, k = 100, λ = 36, μ = 20. The spectrum is 100¹ 20⁶⁵ (−4)³⁵⁰. It is the unique graph that is locally the Hall-Janko graph (Pasechnik [2]). Its 2nd subconstituent is the distance-2 graph of the Cohen-Tits near octagon.

Group

The full group of automorphisms is G = G₂(4).2 (of order 2¹³.3³.5².7.13), acting rank 3, with point stabilizer HJ.2.

Construction

Consider the projective plane PG(2,16) provided with a nondegenerate Hermitean form. It has 273 points, 65 isotropic and 208 nonisotropic. There are 416 = 208.12.1/6 orthogonal bases. These are the vertices of Γ. The group U₃(4):4 of semilinear transformations preserving the form acts transitively on the 416 bases, with rank 5. The suborbit sizes are 1, 15, 100, 150, 150. Γ is the graph obtained by taking the suborbit of size 100 for adjacency.

These suborbits can be described geometrically as follows: Given one basis {a,b,c}, the suborbit of size 15 consists of the bases that have an element in common with {a,b,c}. The first suborbit of size 150 consists of the bases that are disjoint from {a,b,c} but contain a point orthogonal to one of a,b,c. Associated with a basis {a,b,c} is the triangle consisting of the 15 isotropic points on the three lines ab, ac, and bc. The suborbits of sizes 1, 15, 100, 150, 150 correspond to the bases with triangles having 15, 5, 3, 2, 5 points in common. Thus, Γ can be described as the graph on the 416 triangles, adjacent when they have 3 points in common ([1]).

Supergraphs

This graph is the first subconstituent of the Suzuki graph on 1782 vertices, a rank 3 strongly regular graph with parameters (v,k,λ,μ) = (1782,416,100,96). It is also the first subconstituent of a triple cover of that graph, an antipodal distance-transitive graph with intersection array {416,315,64,1; 1,32,315,416}, group 3.Suz.2 with point stabilizer G₂(4).2, constructed by Soicher [3]. Pasechnik [2] showed that these two graphs are the only graphs that are locally Γ.

Subgraphs

We give the substructures of Γ associated to the 8 maximal subgroups of G distinct from G₂(4), sorted according to increasing orbit size.

a) A vertex.
There are 416 of these, forming a single orbit. The stabilizer of one is HJ.2 with vertex orbit sizes 1+100+315. The subgraph induced on the first subconstituent is the Hall-Janko graph, which is strongly regular with parameters (v,k,λ,μ) = (100,36,14,12).

b) Three copies of the 2-coclique extension of the Clebsch graph. Or: a 96+320 split.
The 65520 nonedges of Γ form a single orbit. The stabilizer of one has vertex orbit sizes 2+10+20+64+160+160. These 65520 nonedges fall into 1365 sets of 48, where each set induces a subgraph of size 96 that is the disjoint union of three copies of the 2-coclique extension of the Clebsch graph (the halved 5-cube), and the 48 nonedges are the 2-cocliques.

These 1365 subgraphs of size 96 can be seen as μ-graphs in the Suzuki graph: The rank 3 Suzuki graph Σ on 1782 = 1 + 416 + 1365 vertices is strongly regular with parameters v = 1782, k = 416, λ = 100, μ = 96. We can take Γ to be the first subconstituent of Σ. Now the 1365 vertices of the second subconstituent are seen in Γ as 1365 subgraphs of size 96, regular of valency 20. These 1365 subgraphs form a single orbit. The stabilizer of one is 2²⁺⁸:(3 × A₅):2 with vertex orbit sizes 96+320.

The 4095 subgraphs isomorphic to the 2-coclique extension of the halved 5-cube form a single orbit. They can be seen as μ-graphs in Soicher's triple cover of the Suzuki graph. The stabilizer of one is 2²⁺⁸:A₅:2 with vertex orbit sizes 32+64+320.

The graph induced on the 320 vertices outside a fixed subgraph of size 96 can be extended by a 16-coclique to construct a srg(336,80,28,16) (Jenrich, 2014).

c) Unions of 16 16-cocliques.
Γ contains a unique orbit of 21840 16-cocliques (there are four more orbits of 16-cocliques, see below in the Cocliques section) each stabilized by a group (A₄ × (2⁴ : A₅)) : 2 of order 23040 with vertex orbit sizes 16+240+160. The union of the orbits of sizes 16+240 gives a 256-point subgraph of valency 60 stabilized by a subgroup H of shape 2⁴⁺⁶:(A₅ × 3):2 of order 368640 with vertex orbit sizes 256+160. There are 1365 such 256-point subgraphs. Such a 256-point subgraph Δ contains many 16-cocliques, but there is only one orbit of size 16 of H on 16-cocliques in Δ (giving a partition of the vertex set of Δ). The graph Δ is the strongly regular graph with parameters (v,k,λ,μ) = (256,60,20,12) described in Jenrich (2014).

The 1365 subgraphs of size 96 found under b) and the 1365 subgraphs of size 256 found here form the points and lines of a generalized hexagon GH(4,4) (with 5 points/line and 5 lines/point) if we let disjoint subgraphs of different types be incident.

d) Sets of 208 6-cocliques.
The maximal subgroup U₃(4):4 was used above to construct the graph Γ. It is transitive on the 416 vertices. Each of the 208 hyperbolic lines in PG(2,16) gives 6 bases forming a 6-coclique in Γ. This yields a family of 208 6-cocliques (3 on each vertex) invariant for U₃(4):4. This subgroup has index 2016, and the action of G on the 2016 families has permutation rank 3 with suborbit sizes 1+975+1040, giving rise to a strongly regular graph with parameters (2016,975,462,480). The full group of the latter graph is O₇(4).2.

e) A Gewirtz subgraph.
Each element of Atlas type 3A of G₂(4) fixes 56 vertices of Γ, and Γ induces a Gewirtz graph on these 56-sets. There are 2080 of these, forming a single orbit. The stabilizer of one is 3.L₃(4).2² with vertex orbit sizes 56+360. The action of G on these 2080 has permutation rank 4 with suborbit sizes 1+126+945+1008. A vertex outside a Gewirtz subgraph has 14 neighbours inside, inducing a co-Heawood subgraph. The 280 Gewirtz subgraphs on a vertex p induce the 280 10-cocliques in the Hall-Janko subgraph on the neighbours of p. If C is one of these 10-cocliques, then each vertex nonadjacent to p has two neighbours in C.

f) An edge.
There are 20800 of these, forming a single orbit. The stabilizer of one is U₃(3):2 × 2 with vertex orbit sizes 2+36+126+252.

g) A 6-coclique or a 50-point subgraph P#5.
Γ has 698880 5-cliques, forming a single orbit. The stabilizer of one is Sym(5) × Sym(3) with vertex orbit sizes 5+6+15+30+60+60+120+120. The orbit of size 6 here is the 6-coclique meant - it is not a maximal coclique, but its stabilizer is (A₅ × A₅):2 with vertex orbit sizes 6+50+60+300.

Let P be the Petersen graph on 10 vertices, and let P#5 denote the graph obtained from P by replacing each vertex x by the five (mutually adjacent) vertices (x,i) (i=1,2,3,4,5), and each edge x~y by the twenty edges (x,i)~(y,j) for i notequal j. Now P#5 has 50 vertices and is regular of degree 16. It has 5 10-cocliques and 10+450=460 5-cliques. The group of P#5 is Sym(5) × Sym(5).

Each 5-clique L determines 3 others L_i (i=1,2,3) (forming a single orbit in the stabilizer of L) such that the union of L and L_i induces K₂#4. The union of the orbits with sizes 5+15+30 of the stabilizer of L has shape P#5. There are 69888 subgraphs P#5 forming a single orbit. The stabilizer of one is (A₅ × A₅):2 with vertex orbit sizes 6+50+60+300.

The 6-coclique consists of the 6 vertices without neighbours in the P#5 (so that it is contained in 16-cocliques).

h) 78+91+91+156.
L(2,13) is a maximal subgroup of G with vertex orbit sizes 78+91+91+156, where the two representations on 91 points are nonisomorphic. The point stabilizers are D₁₄, A₄, D₁₂, C₇. The four subgraphs have valencies 28, 24, 24, 36.

Cocliques

Numbers of maximal cocliques of given size:

7: 499200
9: 628992000
10: 111370604800
11: 408839558400
12: 67554614400
13: 3133132800
16: 3808896

These cocliques fall into 1397 orbits, namely 1, 2, 291, 867, 199, 32, 5 orbits of maximal cocliques of size 7, 9, 10, 11, 12, 13, 16, respectively.

The unique orbit of maximal 7-cocliques is that of the parts of the bipartition of the coHeawood graphs found as common neighbours of three mutually adjacent points (so that there are 416*100*36*2/6 = 499200 of them).

The Hoffman bound for cocliques is 16, so that for each 16-coclique each point outside has 4 neighbours inside.

The 16-cocliques in the 5 orbits have stabilizers of order 384, 384, 600, 1536, 23040, respectively. Let C be a 16-coclique of the last type, and S its stabilizer. Then S has vertex orbit sizes 16+240+160. The 16+240 induces a strongly regular subgraph of size 256 that is the union of 16 16-cocliques, and its stabilizer has order 368640. This is the subgraph studied above under c).

Cliques

Maximal cliques have size 5 (since they have size 4 in the local graph). The smallest clique cover has size 84.

Borsuk

Borsuk asked whether any bounded subset in ℝⁿ can be partitioned into n+1 parts, each of smaller diameter. Kahn & Kalai showed that this is false for n = 1325 and n > 2014. Various other people brought the smallest counterexample dimension down. Bondarenko (2013) observed that the Euclidean representation of the graph Γ in its θ-eigenspace for θ=20 yields 416 unit vectors in ℝ⁶⁵ with mutual inner products 1/5 (for adjacent vertices) and −1/15 (for nonadjacent vertices). The diameter of this set is the distance between the images of two nonadjacent vertices, so that a partition into parts of smaller diameter must be a partition into cliques. But Γ has clique number 5, so one needs at least (in fact: precisely) 84 parts. The argument is general: Given a strongly regular graph Γ with v vertices, where the 2nd largest eigenvalue has multiplicity f, one finds v unit vectors in ℝ^f such that this set of vectors cannot be partitioned into fewer parts of smaller diameter than the clique covering number of Γ, that is, the chromatic number of its complement.

Today the counterexample with smallest dimension is the one found by Jenrich (2013): Start with Bondarenko's example. If B_i, i=1,2,3 are the three connected components of a subgraph as under b), then the vector that is 1 on B₁, −1 on B₂, and 0 elsewhere, lies in the ℝ⁶⁵ and is orthogonal to the vectors representing vertices outside B₁ ∪ B₂. This yields 352 unit vectors in ℝ⁶⁴, and a partition into parts of smaller diameter needs at least 71 parts.
In the representation of Γ with orthogonal bases, the 96 vertices of B₁ ∪ B₂ ∪ B₃ can be taken as the bases {a,b,c} that contain an element orthogonal to a fixed isotropic point p.

References

[1] D. Crnković & V. Mikulić, Block designs and strongly regular graphs constructed from the group U(3,4), Glasnik Matematički 41 (2006) 189-194.

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

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

[4] A. V. Bondarenko, On Borsuk's conjecture for two-distance sets, arXiv 1305.2584, May 2013.

[5] T. Jenrich, A 64-dimensional counterexample to Borsuk's conjecture, arXiv 1308.0206, Aug 2013.

[6] T. Jenrich, New strongly regular graphs derived from the G₂(4) graph, arXiv 1409.3520, Sept 2014.