Claudio
Rocchini used the above description to create this image.
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.
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.
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).
Claudio
Rocchini used the above description to create this image.
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
2−1+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).)
size # A B 4 1575 0 4 6 100800 18 2 7 25200 32 3 7 3600 28 7 10 280 120 0The 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.
..... 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).
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.
