Clebsch graph

Alfred Clebsch (1833-1872) was a pioneer in algebraic geometry.

The Clebsch graph named after him is the unique strongly regular graph Γ with parameters v = 16, k = 10, λ = 6, μ = 6. It is the halved 5-cube, and hence it and its complement are cubelike. It is the local graph of the Schläfli graph.

The complement of the Clebsch graph is the unique strongly regular graph Δ with parameters v = 16, k = 5, λ = 0, μ = 2. It is the folded 5-cube. The subgraph on the non-neighbours of a point is the Petersen graph.

The group of automorphisms G is 2⁴.Sym(5) of order 1920, with point stabilizer Sym(5). It is transitive on vertices, edges, non-edges and triangles.

The Clebsch graph has spectrum 10¹ 2⁵ (−2)¹⁰. Its complement has spectrum 5¹ 1¹⁰ (−3)⁵. The Clebsch graph has Seidel spectrum (−5)⁶ 3¹⁰. Its complement has Seidel spectrum 5⁶ (−3)¹⁰.

Name

This graph was given this name by Seidel (1968) in his paper classifying the strongly regular graphs with smallest eigenvalue −2 (for which the Seidel matrix S = J−I−2A has eigenvalue 3):

In terms of polytopes, the 16 vertices and 80 adjacencies of the graph {V,A} can be identified with the 16 vertices and 80 edges of the polytope hγ₅, also denoted by 1₂₁ (Coxeter, Regular polytopes, 2nd ed., pp. 158, 201). This remark is due to H. S. M. Coxeter, who also points out the relation of this polytope to the 16 lines (and 80 pairs of skew lines) on Clebsch's quartic surface (cf. Clebsch (1868)). Therefore, {V,A} will be called the Clebsch graph.

Later some confusion has arisen, and some authors use the name "Clebsch graph" for the complement of Γ.

Constructions

The Clebsch graph is the halved 5-cube, that is, the vertices are the binary vectors of length 5 and even weight, joined when the Hamming distance is 2.

The Clebsch graph is the graph obtained from K₁+T(6) by switching w.r.t. the set of 10 pairs not containing a fixed symbol (see also 2-graphs).

The Clebsch graph is also the graph obtained from the Hamming graph H(2,4), that is, the 4 × 4 grid, by switching w.r.t. a partition into two 2 × 4 grids.

The complement of the Clebsch graph is the folded 5-cube. That is, its vertices are the 16 cosets of {00000,11111}, adjacent when the Hamming distance is 1. It is the graph obtained by identifying antipodes in the 5-cube.

Equivalently, the complement of the Clebsch graph is the graph obtained from the 4-cube by joining antipodes by an edge.

The complement of the Clebsch graph is the graph on GF(16) where two points are adjacent when their difference is a cube. It follows that K₁₆ is the edge-disjoint union of three copies of the complement of the Clebsch graph.

Symmetric designs

The adjacency matrix A of Γ is the point-block incidence matrix of a square 2-(16,10,6) design. The matrix J−A is the point-block incidence matrix of a square 2-(16,6,2) design. There are three such designs, see the folded 6-cube.

Supergraphs

The Clebsch graph is the local graph of the Schläfli graph.

Subgraphs

We give the substructures of Γ associated to the 4 conjugacy classes of maximal subgroups of G distinct from 2⁴:A₅, sorted according to decreasing order.

a) A parallel class of nonedges. There are 5 of these, forming a single orbit. The stabilizer is 2⁴:Sym(4) of order 384. It is transitive on the set of vertices, and has orbits of sizes 32+48 on the edges, and 8+32 on the nonedges (that is, 4+6 on the edge directions, 1+4 on the nonedge directions).

b) A nice pairing of the quadrangles in Δ. There are 60 pairings of the 40 quadrangles in Δ such that the union of two paired quadrangles induces a cube, and each of the 20 cubes contains one pair. Such a pairing is called nice when for any two cubes that share a face that is not in their chosen pair, the quadrangles in their chosen pairs meet pairwise in a single point. There are 6 such nice pairings, forming a single orbit. The stabilizer is 2⁴:5:4 of order 320. It is transitive on vertices, edges and nonedges.

c) A parallel class of edges. There are 10 of these, forming a single orbit. The stabilizer is D₈ × Sym(4) of order 192. It is transitive on the set of vertices, and has orbits of sizes 8+24+48 on the edges, and 16+24 on the nonedges (that is, 1+3+6 on the edge directions, and 2+3 on the nonedge directions). Since Δ has μ=2, an edge in the Clebsch graph Γ determines a quadrangle in Δ, that is, a pair of directions in the folded 5-cube; if we remove the edges in these two directions from Δ, what is left is the union of two 3-cubes. Such a split of Δ into two 3-cubes corresponds to a split of Γ into two subgraphs 2 × 4.

d) A vertex.
There are 16 of these, forming a single orbit. The stabilizer is Sym(5) of order 120, with vertex orbit sizes 1+5+10.

Independence and chromatic number

The Clebsch graph has independence number 2 and chromatic number 8. The complement of the Clebsch graph has independence number 5 and chromatic number 4.

References

A. Clebsch, Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen, J. für Math. 69 (1868) 142-184.

H.S.M. Coxeter, Self-dual configurations and regular graphs, Bull. Amer. Math. Soc. 56 (1950) 413-455.

W.H. Clatworthy, Partially balanced incomplete block designs with two associate classes and two treatments per block, J. Res. Nat. Bur. Standards 54 (1955) 177-190.

J.J. Seidel, Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3, Lin. Alg. Appl. 1 (1968) 281-298.