The McLaughlin Graph

A partition $(S,\comp{S})$ of $V(G)$ determines a bipartite subgraph of $G$; if we replace this subgraph by its bipartite complement, we say that the resulting graph is got by switching on $S$ (or on $\comp{S}$). If $S$ is the neighborhood of a vertex $u$ in $G$, then after switching on $S$ the vertex $u$ is isolated.

def switch(G,sub):
H = G.copy()
rest = Set(H.vertices()).difference(Set(sub))
for u in sub:
for v in rest:
if H.has_edge(u,v): H.delete_edge(u,v)
return H


We construct a graph on the blocks of the $4$-$(23,7,1)$ design formed by the words of weight seven in the binary Golay code of length 23. (This graph is strongly regular.) We then add 23 vertices $\{0,\ldots,23\}$ corresponding to the 23 coordinate positions of a code word, and join the $i$-th new vertex to the blocks that do not contain it. The resulting graph is not regular but if we switch on one of the new vertices and then delete it we get the McLaughlin graph on 275 vertices, which is strongly regular.

C = ExtendedBinaryGolayCode()
D = C.punctured([0])
words = [ tuple(it.support()) for it in D if hamming_weight(it)==7]
MG = Graph( [words, lambda a,b: len(Set(a).intersection(Set(b)))==1])
MM = MG.copy()
edges = [ (i,a) for i in [0..22] for a in words if i not in a]
McL = switch( MM, MM[0])
McL.delete_vertex(0)


It's strongly regular, with a big automorphism group:

grp_order = McL.automorphism_group(return_group=0,order=1)
McL.is_connected(), McL.is_regular(), McL.am().fcp(), grp_order

(True, True, (x - 112) * (x + 28)^22 * (x - 2)^252, 1796256000)


The McLaughlin graph gives rise to a regular two-graph. For details on regular two-graphs, see any recent book on algebraic graph theory.

G = McL.copy()
G.relabel()
A = G.am()
n = G.num_verts()
J = Matrix(n,n,n^2*[1])
B = J -1 -A
C = block_matrix( 2, 2, [A,B,B,A])
SMcL = Graph( C)
grp = SMcL.automorphism_group()
grp.order(), SMcL.am().fcp()

(991533312000, (x - 275) * (x + 55)^23 * (x - 5)^253 * (x + 1)^275)


and now

grp.composition_series()[1].is_simple()

True


The group is one of Conway's simple groups. [* Too big by a factor of two! Does the graph need adjustment or does the simple group just come as an index 2 subgroup of the automorphism group? *]