Up

Brouwer-Haemers graph

There is a unique strongly regular graph Γ with parameters v = 81, k = 20, λ = 1, μ = 6, namely the affine orthogonal graph VO–(4,3). Construction is folklore. An early reference is Mesner (1964). Uniqueness was proved by Brouwer & Haemers (1992). The spectrum is 201 260 (–7)20.

Group

The full group of automorphisms is 34:((2×S6).2) acting rank 3, with point stabilizer (2×S6).2.

Construction

(i) This is the graph on the vectors of a 4-dimensional vector space over GF(3) provided with a quadratic form of Witt index 1, where two vectors are adjacent when the quadratic form vanishes on their difference. (We have O–4(3) = A6, which has index 2 in PGO–4(3) = S6, which has index 2 in GO–4(3) = 2×S6, which again has index 2 in the group preserving the form up to a constant.)

A symmetric representation is found by taking 1perp/1 in a 6-dimensional vector space over GF(3) provided with "sum of squares", i.e. the weight, where two vertices are adjacent when their difference has weight 3.

And instead of taking sum 0 (that is, 1perp), we can also take sum 1 (or sum 2).

(ii) Equivalently, take the points of AG(4,3), adjacent when the joining line hits a fixed elliptic quadric in the hyperplane at infinity.

(iii) This graph also is the Hermitean forms graph on GF(9)2.

(iv) This graph also is the coset graph of the truncated ternary Golay code.

(v) This graph also is the graph on GF(81) where two points are adjacent when their difference is a fourth power.

Supergraphs

This graph is the second subconstituent of the GQ(3,9) collinearity graph. Consequently, it is also found inside the McL graph.

Cocliques

This graph has 324 maximal 6-cocliques, 68445 maximal 9-cocliques, 338580 maximal 10-cocliques, 87480 maximal 11-cocliques, 21060 maximal 12-cocliques, and 324 maximal 15-cocliques. No other maximal cocliques occur.

The 324 15-cocliques form a single orbit, with stabilizer Sym(6). The stabilizer has three orbits, of sizes 15+60+6, where such orbits of size 6 are the maximal 6-cocliques. Such cocliques are most easily seen in the representation of ternary vectors of length 6 with sum 1, modulo the all-1 vector. Each vertex has a unique representative of weight 1, 2, or 3, and there are 6+15+60 such vectors.

Chromatic number

This graph has chromatic number 7 [E. van Dam].

Second subconstituent

The second subconstituent Δ of Γ has spectrum 141 240 (–4)10 (–6)9. The automorphism group of Δ is (22×S6).2, twice as large as the point stabilizer of the automorphism group of Γ.

Blokhuis, Brouwer & Haemers show that Δ is uniquely determined by its spectrum. Sketch of the proof: If the adjacency matrix is A, then (A–2I)(A+4I)(A+6I) = 72J and it follows that each vertex is in 4 triangles. The local graph is 6K1+4K2 (for otherwise some point neighbourhood would contain seven isolated points and the 4×4 matrix of average row sums for the partition with sizes 1+7+7+45 would have 2nd largest eigenvalue larger than 2, contradiction). The matrix B = 4J–(A+2I)2+16I is psd so that two nonadjacent vertices have at least 2 and at most 6 common neighbours. We find a representation of Δ in real 10-space, with vectors of squared norm 2, and inner products –λ for adjacent vertices, and 4–μ for nonadjacent vertices. B satisfies JB=0 and AB=–4B and B2=12B so that the rows of B are integral vectors with sum 0 and squared norm 24. If rows x and y of B are identical, then μ(x,y) = 2 and we see two 2's and at least 14 –1's in each row, and the row sum is nonzero, contradiction. It follows that the representation is injective: we have 60 distinct roots. Now examination of the root system shows that it must be A5+A5, and uniqueness follows.

References

A.E. Brouwer & W.H. Haemers, Structure and uniqueness of the (81,20,1,6) strongly regular graph, Discrete Math. 106/107 (1992) 77-82.

D.M. Mesner, Negative Latin square designs, Institute of Statistics, UNC, NC Mimeo series 410, November 1964.

A. Blokhuis, A. E. Brouwer & W. H. Haemers, The graph with spectrum 141 240 (−4)10 (−6)9, Designs, Codes & Cryptography 65 (2012) 71-75.