Up

Hall-Janko graph

There is a rank 3 strongly regular graph Γ with parameters v = 100, k = 36, λ = 14, μ = 12. The spectrum is 361 636 (-4)63. The graph was constructed by Hall & Wales. This graph is not determined by its parameters only - indeed, any graph OA(10,4) (that is, two orthogonal Latin squares of order 10) will have the same parameters, but cannot be isomorphic. This graph is the unique connected graph that is locally the U3(3) graph (Pasechnik).

Group

The full group of automorphisms is G = HJ.2, acting rank 3, with point stabilizer U3(3).2.

Construction

1+36+63 first version

There is a strongly regular graph with parameters v = 36, k = 14, λ = 4, μ = 6 and group of automorphisms U3(3).2 with point stabilizer L2(7).2. See the description of the U3(3) graph for a description of this graph as 1+14+21, in terms of the Fano plane.

That graph on 36 vertices has 63 subgraphs on 12 vertices isomorphic to the 2-coclique extension of 2×3, 21 on each vertex.

(The 21 on the base vertex x of the 1+14+21 construction are in 1-1 correspondence with the flags pL in Fano: x, the points p,q,r on L, the lines L,M,N on p, and the five flags pL,qL,rL,pM,pN.)

Construct the Hall-Janko graph by taking a base vertex z, the 36 vertices of the U3(3) graph, all adjacent to z, and these 63 12-point subgraphs of the U3(3) graph, adjacent to their 12 points, where two such subgraphs are adjacent when they have 4 points in common.

1+36+63 second version

In the projective plane PG(2,9) provided with a nondegenerate hermitean form, one has a unital with 28 points, and 63 nonisotropic points. The plane has 63.6.1/6 = 63 orthogonal bases, and the 63 points and 63 bases form a generalized hexagon GH(2,2). Two points have distance 1 when they are orthogonal, distance 2 when not orthogonal while the joining line is not a tangent, and distance 3 when the joining line is a tangent. Two bases have distance 1 when they meet, distance 2 when one contains a point that is orthogonal to some point of the other, and distance three otherwise.

This generalized hexagon is not self-dual: it is disconnected (with two components of size 16) far away from a point, but is connected far away from a line.

Any apartment (hexagon) in this GH(2,2) determines a unique sub-GH(2,1) (with 14 lines and 21 points) and we find 36 sub-GH(2,1)'s in this way. These sub-GH(2,1)'s either coincide (14 lines and 21 points in common), or meet in a line and the lines meeting it (4 lines and 9 points in common), or meet in two intersecting lines (2 lines and 5 points in common), and these intersections occur with frequencies 1, 14, 21.

The set of 63 nonisotropic points of PG(2,9) has precisely 36 partitions into 21 bases, twelve on any given basis. These partitions meet in 3, 9, or 21 bases (with frequencies 14, 21, 1). Each partition is obtained from a sub-GH(2,1) by taking the 21 lines that meet it in a single point.

The graph on these 36 partitions where two are adjacent when they meet in 3 bases, or, equivalently, the graph on the 36 sub-GH(2,1)'s where two are adjacent when they have 4 lines in common, is strongly regular with parameters v = 36, k = 14, λ = 4, μ = 6. Its group of automorphisms is U3(3).2 with point stabilizer L2(7).2.

Our graph on 100 vertices is constructed as 1+36+63, where the 36 is the set of 36 sub-GH(2,1)'s, adjacent when they have 4 lines in common, and the 63 is the set of 63 nonisotropic points, adjacent when they are not orthogonal and the joining line is not a tangent, and a sub-GH(2,1) is adjacent to its points.

10+90

Construct our graph using two ingredients: the Foster graph F on 90 vertices, and the Moebius plane S(3,4,10). The Foster graph is the unique distance-regular graph with intersection array {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}, has group 3.Alt(6).22, distance distribution 1+3+6+12+24+24+12+6+2, and is an antipodal 3-cover of the unique distance-regular graph with intersection array {3,2,2,2;1,1,1,3} on 30 vertices, the incidence graph of GQ(2,2), and also the graph on the 30 circles (blocks) of S(3,4,10), adjacent when disjoint. Let π be the folding map.

The 100 vertices of Γ are the 90 vertices of F and the 10 points of the point set X of S(3,4,10). X is a 10-coclique in Γ, two vertices of F are adjacent in Γ when they have distance 3, 6, 7 or 8 in F, and the point x in X is adjacent to y in F when x is in the block π(y).

image of HJ graph by Claudio Rocchini Claudio Rocchini used the above description to create this image.

Supergraphs

This graph is the first subconstituent of the G2(4).2 graph on 416 vertices, which in its turn is the first subconstituent of the Suz graph on 1782 vertices.

Subgraphs

We give the substructures of Γ associated to the 9 maximal subgroups of G distinct from HJ, sorted according to increasing orbit size.

a) A vertex.
There are 100 of these, forming a single orbit. The stabilizer of one is U3(3):2 with vertex orbit sizes 1+36+63. The subgraph induced on the first subconstituent is the U3(3) graph, which is strongly regular with parameters (v,k,λ,μ) = (36,14,4,6).

b) A decad (10-coclique).
There are 280 of these, forming a single orbit. The stabilizer of one is 3.A6.22 with vertex orbit sizes 10+90. For the structure of the 90, see the 10+90 construction above. These 280 objects carry a 3-class association scheme with valencies 36, 108, 135 and the relations of valency 36 and 135 are strongly regular with parameters (280,36,8,4) and (280,135,70,60). Two decads meet in either zero or two points, where the relation of valency 135 is that of meeting in two points. Note that the graph with parameters (280,36,8,4) is not the collinearity graph of GQ(9,3) - in fact it is the collinearity graph of a partial linear space with 12 4-lines on each point.

c) A 2-coclique extension of T(5).
The 3150 nonedges of Γ fall into sets of 10, where each set induces a subgraph that is the 2-coclique extension of the triangular graph T(5). There are 315 of these sets, forming a single orbit. The stabilizer of one is 21+4.Sym(5) with vertex orbit sizes 20+80.

The stabilizer of a non-edge has vertex orbit sizes 2+6+12+32+48, where the 12 form the mu-graph, which is a 2-coclique extension of K2×K3. The orbits 2+6+12 induce a 2-coclique extension of T(5).

These 315 objects carry the unique distance-transitive graph with intersection array {10,8,8,2; 1,1,4,5}, the Cohen-Tits near octagon, see [BCN], Section 13.6. They can be viewed as the involutions in HJ of Atlas type 2A. They form the second subconstituent of the G2(4).2 graph on 416 points that is locally Γ. That latter graph is strongly regular with parameters (416,100,36,20), and the 315 objects are seen inside Γ as the mu-graphs (of size 20).

d) A subgraph K4,4,4 (or also: a subgraph 3K4×2).
The graph Γ contains 525 subgraphs K4,4,4 (12 vertices, valency 8) forming a single orbit. And also 525 subgraphs 3K4×2 (24 vertices, valency 6) forming a single orbit. The stabilizer of one of these is (22+4:3×S3).2 with vertex orbit sizes 12+24+64.

There are 1575 maximal 4-cocliques, forming a single orbit. The stabilizer of one is 22+3:Sym(4) with vertex orbit sizes 4+8+24+64. The 4+8 induce K4,4,4.

Below under e) we see that given a 4-clique L one finds three other 4-cliques Li such that the union of L and Li induces K4×2. But that latter graph has 16 4-cliques, so there are 8400.3/16 = 1575 subgraphs K4×2 in Γ, forming a single orbit. The stabilizer of one has vertex orbits 8+12+16+64, where these orbits consist of the vertices with 6,4,0,3 neighbours inside the given K4×2. The orbits of sizes 8+16 form 3K4×2.

e) A 40-point subgraph P#4.
Let P be the Petersen graph on 10 vertices, and let P#4 denote the graph obtained from P by replacing each vertex x by the four (mutually adjacent) vertices (x,i) (i=1,2,3,4), and each edge x~y by the twelve edges (x,i)~(y,j) for i notequal j. Now P#4 has 40 vertices and is regular of degree 12. It has 4 10-cocliques and 10+210=220 4-cliques. The group of P#4 is Sym(5) × Sym(4).

There are 8400 4-cliques in Γ, forming a single orbit. The stabilizer of a 4-clique in G is Sym(3) × Sym(4) with vertex orbit sizes 4+12+24+24+36, where the orbits of sizes 12, 24, 24, 36 consist of the vertices outside the 4-clique with 3, 0, 1, 2 neighbours inside. Each 4-clique L determines three others Li (i=1,2,3) (forming a single orbit in the stabilizer of L) such that the union of L and Li induces K2#4 = K4×2. The union of the first three orbits, of size 4+12+24 = 40, is P#4.

There are 840 subgraphs P#4, forming a single orbit. The stabilizer of one is (A5 × A4):2 with vertex orbit sizes 40+60.

f) A nice partition into 10 decads.
Γ has 1008+12096 partitions into 10 decads, falling into two orbits. Let us call those in the orbit of size 1008 nice. The stabilizer of one is (A5 × D10).2, transitive on the 100 vertices, with orbit sizes 10+120+150 on the 280 decads.

g) An edge.
There are 1800 of these, forming a single orbit. The stabilizer of one is L3(2):2 × 2 with vertex orbit sizes 2+14+42+42.

h) A split 100=50+50 of the vertex set.
The vertex set of Γ has splits into two halves, where each half is in three different ways the union of five decads. There are 2016 of these splits, forming a single orbit. The stabilizer of one is 52:(4×S3), transitive on the 100 vertices.

Above under f) we saw that there are two kinds of partition of Γ into 10 decads. There are 12096 ugly ones, forming a single orbit. The stabilizer of one is 52:4, transitive on the 100 vertices, with orbit sizes 10+10+10+50+50+50+100 on the 280 decads. The union 10+10+10 of three ugly partitions has stabilizer 52:(4×S3), transitive on the 100 vertices, with orbit sizes 30+100+150 on the 280 decads. There are 2016 of these sets of 30 decads, forming a single orbit.

Each set of 30 decads consists of six groups of five, where three groups of five have the same 50-point union, and the other three groups have the complementary union, so that the set contains 9 partitions into 10 decads, and is the union of three pairwise disjoint such partitions in 2 ways.

i) A 2-clique extension of the Petersen graph.
There are 10080 of these, forming a single orbit. The stabilizer of one is Sym(5) with vertex orbit sizes 20+20+60. (The two orbits of size 20 induce nonisomorphic subgraphs, regular of size 7. One orbit of size 20 induces a 2-clique extension of the Petersen graph. The other induces the graph on the ordered pairs from a 5-set, with (i,j) adjacent to (j,i) and (k,i) and (j,k).)

Independence and chromatic number

The Hall-Janko graph has independence number 10 and chromatic number 10. The complement of the Hall-Janko graph has independence number 4 and chromatic number 25.

Cocliques

Maximal cocliques have sizes 4, 6, 7, 10 and fall into five orbits (there are two orbits of maximal 7-cocliques). G is transitive on 2-cocliques (nonedges) but has two orbits on 3-cocliques. Below we give for each coclique C how many triples from C belong to these two orbits.
size  #       A    B
4     1575    0    4
6     100800  18   2
7     25200   32   3
7     3600    28   7
10    280     120  0
The maximal cocliques of size 4 are the 100.63/4 = 1575 sets consisting of a vertex and a line in the GH(2,2) far from that vertex. The maximal cocliques of size 7 in the 2nd orbit are the 2.100.36/2 halves of the Heawood graph on the common neighbours of two adjacent vertices.

Cayley graph

We saw that HJ.2 has a (nonabelian) subgroup 52:4 of order 100 that acts regularly on the vertices of Γ. Thus, Γ is a Cayley graph. Here a picture.
.....  X....  ...X.  ...X.  
..XX.  XX...  X..X.  XXX.X  
.X*X.  XXX.X  ..X..  ..X..  
.XX..  X...X  XXX..  X.X..  
.....  ...X.  ..XXX  ..X.X  

.X...  ..X.X  ...X.  .X.XX  
X...X  .....  XXX.X  X...X  
X.XXX  X.*.X  ..X..  X.XX.  
...XX  .....  X.X..  ...X.  
....X  X.X..  ..X.X  X....  

XXX..  X.X..  .....  .X...  
..XXX  ..X.X  ..XX.  X...X  
..X..  ..X..  .X*X.  X.XXX  
.X..X  X.XXX  .XX..  ...XX  
.X...  .X...  .....  ....X  

X.X..  ....X  X....  ..X.X  
..X.X  .X...  XX...  .....  
..X..  .XX.X  XXX.X  X.*.X  
X.XXX  X...X  X...X  .....  
.X...  XX.X.  ...X.  X.X..  
(the four 5x5 squares in a row represent the four orbits of 52; indicated are the neighbours of the starred vertex; each row of four equals the previous row, shifted by one square, with squares reflected in the main diagonal and multiplied by -2).

Related graphs on 100 vertices

Given a partition of the vertex set of Γ into ten 10-cocliques, we may add edges and turn these into ten 10-cliques. The resulting graph is strongly regular with parameters (100,45,20,20) (and hence also gives rise to a symmetric 2-(100,45,20) design). This conclusion depends only on the parameters, and the two distinct partitions into decads yield two nonisomorphic srgs. If this partition fits to a 50-50 split, then Seidel switching on that split yields a strongly regular graph with parameters (100,55,30,30). [Bagchi, Jørgensen & Klin]

References

Marshall Hall, Jr. & David Wales, The Simple Group of Order 604,800, J. Algebra 9 (1968) 417-450.

S. Yoshiara, On the geometry of the Hall-Janko group on 315 points, Geom. Dedic. 32 (1989) 173-201.

Bhaskar Bagchi, A regular two-graph admitting the Hall-Janko-Wales group, Combinatorial mathematics and applications (Calcutta, 1988), Sankhyā Ser. A 54 (1992), Special Issue, 35-45.

A. E. Brouwer, A construction of the HJ graph, preprint, 1989. [contains the above construction from S(3,4,10) and the Foster graph]

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

Hans Cuypers, Extended generalized hexagons and the Suzuki chain, J. London Math. Soc. (2) 54 (1996) 1-15.

L. K. Jørgensen & M. Klin, Switching of edges in strongly regular graphs. I. A family of partial difference sets on 100 vertices, Electr. J. Comb. 10 (2003) R17.

D. Leemans, On a rank four geometry for the Hall-Janko sporadic group, JCT (A) 101 (2003) 160-167.