Up

The Octad Graph

There is a unique distance-regular graph Γ with intersection array {30,28,24; 1,3,15}. It has v = 759 vertices, valency k = 30, and diameter d = 3. The spectrum is 301 7252 (−3)483 (−15)23. It is the collinearity graph of a near hexagon. Construction of Γ is folklore. The near hexagon is due Shult & Yanushka (1980). Uniqueness of Γ is Theorem 11.4.1 in [BCN], an immediate corollary of the uniqueness of the near hexagon (Brouwer (1983)).

Construction

Let C be the extended binary Golay code C. If Ω is the 24-set of coordinate positions of C, and X the set of supports of the 759 vectors of weight 8 in C, then (Ω,X) is the unique Steiner system S(5,8,24), one of the Witt designs. The graph Γ is the block graph of (Ω,X): the vertices are the elements of X (called octads since they are certain 8-subsets of Ω), and two vertices are adjacent when they are disjoint.

Group

The automorphism group of Γ is M24 of order 244823040, acting distance-transitively with point stabilizer 24:A8. Thus, M24 is transitive on the points, and has 4 orbits on pairs of points, corresponding to distance 0, 1, 2, 3. See here for the classification of the orbits of M24 on triples of points.

Near hexagon geometry

The graph Γ is the collinearity graph of the point-line geometry of which the points are the 759 octads, and the lines the 3795 partitions of Ω into three pairwise disjoint octads. Each point is on 15 lines, and each line has 3 points.

This point-line geometry is a near polygon: for each point x and each line L there is a unique point on L closest (in graph distance) to x. More precisely, it is a near hexagon, since Γ has diameter 3. Given a set S of points, let C(S) be the geodetic closure of S, that is, the smallest subspace containing S that is closed for geodetics. If x, y are points with d(x,y) = 2, then C({x,y}) is a subgeometry with 15 points and 15 lines called a quad. It is a generalized quadrangle of order 2. The 15 lines and 35 quads on a fixed point x form the points and lines of a geometry PG(3,2). If Q is a quad, and z a point with d(z,Q)=2, then z has distance 2 to five points of Q, and these five points form an ovoid in Q. See also [BCN], §11.4A.

Big ovoids and subgraphs on 506 vertices

There is a unique distance-regular graph Δ with intersection array {15,14,12; 1,1,9}. It has 506 vertices, valency 15 and diameter 3. The spectrum is 151 (−8)22 4230 (−3)253. Uniqueness is due to Brouwer & Lambeck (1987).

Let ω be a fixed element of Ω. There are 253 octads that contain ω, and 506 that do not contain ω. The graph Δ is the induced subgraph in Γ on the set of 506. The set of 253 is a big ovoid O: a set that meets every line of the near polygon in precisely one point. (Above we saw 5-point ovoids in a quad. These are the intersections of a big ovoid and a quad. Also the intersections of four big ovoids.) There are no other big ovoids than the 24 obtained in this way.

The 24 big ovoids are permuted by M24. The stabilizer of one is M23, with vertex stabilizer 24:A7.

The full automorphism group of Δ is M23, with vertex stabilizer A8. The graph Δ is distance-transitive.

The intersection of Δ with a quad is a Petersen graph. For each vertex x of Δ, the 15 edges and 35 Petersen graphs and 15 symbols (in Ω \ (x ∪ {ω})) form the points and lines and planes of a geometry PG(3,2). See also [BCN], §11.4B.

Subgraphs on 330 vertices

There is a unique distance-regular graph E with intersection array {7,6,4,4; 1,1,1,6}. It has 330 vertices, valency 7 and diameter 4. The spectrum is 71 455 1154 (−3)99 (−4)21. Uniqueness is due to Brouwer (1986).

Let σ, τ be two fixed elements of Ω. There are 77 octads that contain both σ and τ, 352 that contain precisely one, and 330 that contain neither. The graph E is the induced subgraph in Γ on the set of 330. The full automorphism group of E is M22.2, with point stabilizer 23:L3(2)×2. The graph E is distance-transitive. See also [BCN], §11.4C.

References

A. E. Brouwer, The uniqueness of the near hexagon on 759 points, pp 47-60 in: Finite Geometries, T. G. Ostrom Conf. Pullman 1981, Lecture Notes in Pure and Applied Math. 82, Marcel Dekker, New York, 1983.

A. E. Brouwer, Uniqueness and nonexistence of some graphs related to M22, Graphs Combin. 2 (1986) 21-29.

A. E. Brouwer, A. M. Cohen & A. Neumaier, Distance-regular graphs, Springer, Heidelberg, 1989.

A. E. Brouwer & E. W. Lambeck, An inequality on the parameters of distance regular graphs and the uniqueness of a graph associated to M23, Ann. Discrete Math. 34 (1987) 100-106.

J. H. Conway, Three lectures on exceptional groups, pp 215-247 in: Finite Simple Groups, Academic Press, 1971.

E. E. Shult & A. Yanushka, Near n-gons and line systems, Geom. Dedicata 9 (1980) 1-72.