The Hoffman-Singleton Graph is an amazing structure, which can be created many different ways. It is best known as a Moore graph: regular of degree $7$ with odd girth $5$, on $50$ vertices, which is the minimum conceivable number.

We first need some of the objects we computed in Chapter 5, so evaluate the next cell to get started.

xxxxxxxxxx

K6 = graphs.CompleteGraph(6)

vertices = K6.vertices()

edges = [Set(e) for e in K6.edges(labels=False)]

factors = SetPartitions(vertices,[2,2,2]).list()

factors = [Set(list(A)) for A in factors]

factor_graph = Graph([(f1, f2) for f1, f2 in Subsets(factors, 2) if f1.intersection(f2).cardinality() == 0])

factorizations = factor_graph.cliques_maximum()

factorizations = [Set(f) for f in factorizations]

Our construction begins with two new vertices, which Cameron and van Lint call “zero” and “infinity” — we will shorten the label on the latter to simply “inf.” Zero and infinity will be adjacent to each other, zero will be adjacent to each vertex of $K_6$ and infinity will be adjacent to each factorization of $K_6$.

xxxxxxxxxx

G = Graph()

G.add_edge('inf', 'zero')

G.add_edges([(v, 'zero')for v in vertices])

G.add_edges([(fz, 'inf') for fz in factorizations])

We have $14$ vertices in our graph so far, we get another $36$ from the Cartesian product of the set of $6$ $K_6$ vertices with the set of $6$ factorizations. Each pair is joined to the $K_6$ vertex of the pair and the factorization in the pair. At this point the vertices from the Cartesian product have just degree $2$, the other vertices have reached degree $7$.

xxxxxxxxxx

G.add_edges([(v,  (v,fz)) for v in vertices for fz in factorizations])

G.add_edges([(fz, (v,fz)) for v in vertices for fz in factorizations])

Among vertices of the Cartesian product a pair $(a, x)$ is adjacent to the pair $(b, y)$ if $x$ and $y$ are different factorizations and the edge $\{a, b\}$ is contained in the factor common to $x$ and $y$. (Recall that every pair of factorizations have a single factor in common.)

xxxxxxxxxx

for v1, v2 in Subsets(vertices, 2):

    for fz1, fz2 in Subsets(factorizations, 2):

        common_factor = fz1.intersection(fz2)[0]

        if Set([v1, v2]) in common_factor:

            G.add_edge((v1, fz1), (v2, fz2))

            G.add_edge((v2, fz1), (v1, fz2))

Construction complete, we can check that the graph has the requisite properties to be the Moore graph of degree $7$ and girth $5$.

xxxxxxxxxx

G.num_verts(), G.is_regular(), G.average_degree(), G.girth()

Since these properties are enough to characterize the graph, we know we have it. However, we will let Sage do a brutish check. Our graph will not plot very nicely, while the implementation of the graph in Sage has a very novel feature. Each time you create the Hoffman-Singleton graph, you get a different layout, always displaying some of the inherent symmetry. So you can run the construct-and-plot command below repeatedly to experience different layouts.

xxxxxxxxxx

HS = graphs.HoffmanSingletonGraph()

G.is_isomorphic(HS)

xxxxxxxxxx

graphs.HoffmanSingletonGraph().plot()

Notice that this section is made possible by the arithmetic: $50 = 2 + 6 + 6 + 6\cdot 6$.