Hall–Janko graph

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. 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. 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. 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. 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). 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. 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. 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. 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. (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). 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