The McLaughlin Graph

This page outlines the construction of the McLaughlin Graph, which proceeds in a number of steps.

Step One - The Witt design

The Witt design is a 4-(23,7,1) design that can be constructed as follows: take all the powers of the polynomial g(x) = x11 + x9 + x7 + x6 + x5 + x + 1 modulo h(x) = x23-1 where all polynomial arithmetic is over GF(2).

View each polynomial as a subset of {0, 1, ..., 22} depending on whether the coefficient of x⁰, x¹, ..., x²² is 1 or not. Of the 2048 possibly polynomials, exactly 253 of them yield subsets of size 7, and these 253 subsets form the blocks of the Witt design.

• Maple code to construct the blocks
• The blocks themselves

Step Two - The regular two-graph on 276 vertices

We will use the Witt design to create a 276 vertex graph --- although this graph is not regular, its switching class is a regular two-graph. Recall that we have a rather confusing mix of terminology at this point --- a two-graph is not a graph, but is equivalent to a switching class of graphs. Any one graph in the switching class determines the entire switching class.

The graph X has two types of vertex; the points of the Witt design, and the blocks of the Witt design. Two vertices x,y of X are adjacent if and only if one of the following conditions holds:

1. x is a point and y is a block not containing x
2. x and y are blocks that intersect in one point

This yields a 276-vertex graph where each "point" vertex has degree 176 and each "block" vertex has degree 128.

1. The graph in g6 format
2. The graph as a list of edges

Step Three - The strongly regular McLaughlin graph

A regular two-graph has the property that if we take a graph in the switching class, then we can "switch off" any vertex

Consider the vertex v corresponding to the point 0; then we can divide the remaining vertices into three sets

• A is the 176 blocks that do not contain 0.
• B is the 22 other points {1,2,...,22}.
• C is the 77 blocks that do contain 0.

The partition {v | A | B | C} is an equitable partition of the vertices of X. More precisely, straightforward(ish) counting tells us that

• Vertex v is adjacent to 176 vertices in A, 0 in B and 0 in C.
• Any vertex in A is adjacent to vertex v, to 70 (other) vertices in A, 15 vertices in B and 42 vertices in C.
• Any vertex in B is adjacent to 120 vertices in A, 0 vertices in B and 56 vertices in C.
• Any vertex in C is adjacent to 96 vertices in A, 16 in B and 16 in C.

If we now switch on the neighbourhood of v (which is the set A) then every edge between a neighbour of v and a non-neighbour of v becomes a non-edge, and vice-versa. The effect of this is that all the edges from A to v, A to B, A to C become non-edges and all non-edges from A to v, A to B, A to C become edges. In particular

• v becomes an isolated vertex (all edges between v and A are turned from edges to non-edges)
• every vertex in A remains adjacent to 70 vertices in A, but now becomes adjacent to 22 - 15 = 7 vertices in B and 77 - 42 = 35 vertices in C.
• every vertex in B becomes adjacent to 176 - 120 = 56 vertices in A, remains adjacent to 0 in B and remains adjacent to 56 in C.
• every vertex in C becomes adjacent to 176 - 96 = 80 vertices in A and remains adjacent to 16 vertices in B and 16 vertices in C.

A quick calculation shows that the degree of each vertex in A is 70+7+35 = 112, the degree of each vertex in B is 56+56 = 112 and the degree of each vertex in C is 80+16+16 = 112. Thus if we throw away the vertex v, then what remains is the 112-regular McLaughlin graph on 276 vertices.

1. McLaughlin graph in g6 format
2. McLaughlin graph as edge-list

Author Details

This page written by Gordon Royle in September 2006.