{"id":2195,"date":"2016-02-01T01:00:07","date_gmt":"2016-02-01T01:00:07","guid":{"rendered":"http:\/\/blogs.ams.org\/visualinsight\/?p=2195"},"modified":"2018-01-19T17:50:27","modified_gmt":"2018-01-19T17:50:27","slug":"hoffman-singleton-graph","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/visualinsight\/2016\/02\/01\/hoffman-singleton-graph\/","title":{"rendered":"Hoffman–Singleton Graph"},"content":{"rendered":"
\n
\"Hoffman--Singleton<\/a>

Hoffman–Singleton Graph – Félix de la Fuente<\/p><\/div>\n<\/div>\n

This is the Hoffman–Singleton graph<\/a>, a remarkably symmetrical graph with 50 vertices and 175 edges. There is a beautiful way to construct the Hoffman–Singleton graph by connecting 5 pentagons to 5 pentagrams.<\/p>\n

In what follows, all indices lie in \\(\\mathbb{Z}\/5\\): that is, the integers mod 5.<\/p>\n

Take five pentagons \\(P_h\\): graphs with 5 vertices such that vertex \\(j\\) is adjacent to vertices \\(j-1\\) and \\(j+1\\). Take 5 pentagrams \\(Q_i\\): graphs with 5 vertices such that vertex \\(j\\) is adjacent to vertices \\(j-2\\) and \\(j+2\\). Now join each vertex \\(j\\) of pentagon \\(P_h\\) to the vertex \\(hi+j\\) of pentagram \\(Q_i\\). The result is the Hoffman–Singleton graph<\/b>.<\/p>\n

Félix de la Fuente<\/a> constructed the above picture of the Hoffman–Singleton graph using this method. He explains the details here:<\/p>\n

\"Hoffman--Singleton<\/a>

Hoffman–Singleton Graph: Construction and Petersen Subgraphs – Félix de la Fuente<\/p><\/div>\n

In this diagram \\(P_{h,j}\\) is the \\(j\\)th vertex of the pentagon \\(P_h\\), while \\(Q_{i,k}\\) is the \\(k\\)th vertex of the pentagram \\(Q_i\\). Each vertex \\(P_{h,j}\\) is connected to 5 vertices \\(Q_{hi+j}\\). Félix de la Fuente shows how this connects each pentagon to all 5 pentagrams, forming 5 copies of the ‘Petersen graph’. For more on the Petersen graph, see this earlier post:<\/p>\n

• Petersen graph<\/a>.<\/p>\n

Here is another image of the same construction:<\/p>\n

\n
\"Hoffman--Singleton<\/a>

Hoffman–Singleton graph – Claudio Rocchini<\/p><\/div>\n<\/div>\n

The Hoffman–Singleton graph has 252,000 symmetries. Not surprisingly, they’re deeply connected to the math you can do with the numbers 5 and 25. They form a group isomorphic to the group called \\(\\mathrm{P}\\Sigma \\mathrm{U}(3,\\mathbb{F}_{25})\\). <\/p>\n

To understand this group, note that \\(\\mathbb{F}_{25}\\), the field with 25 elements, can be obtained from \\(\\mathbb{F}_5\\), the field with 5 elements, by adjoining a square root \\(i\\) of some element that does not have a square root in \\(\\mathbb{F}_5\\). This element will then have 2 distinct roots in \\(\\mathbb{F}_{25}\\), namely \\(i\\) and \\(-i\\), and there is an automorphism of \\(\\mathbb{F}_{25}\\) that exchanges them, called the Frobenius automorphism<\/b><\/a>. This automorphism also sends each element of \\(\\mathbb{F}_{25}\\) to its 5th power.<\/p>\n

Since it switches \\(i\\) and \\(-i\\), the Frobenius automorphism of \\(\\mathbb{F}_{25}\\) is similar to complex conjugation. We can use it to define unitary matrices over \\(\\mathbb{F}_{25}\\), and thus the unitary group<\/a><\/b> \\(\\mathrm{U}(3,\\mathbb{F}_{25})\\) consisting of \\(3 \\times 3\\) unitary matrices, and its subgroup \\(\\mathrm{SU}(3,\\mathbb{F}_{25})\\), the special unitary group<\/b><\/a>, consisting of those with determinant 1.<\/p>\n

If we take \\(\\mathrm{SU}(3,\\mathbb{F}_{25})\\) and mod out by its center, consisting of matrices that are multiples of the identity, we obtain the projective special unitary group<\/b><\/a> \\(\\mathrm{PSU}(3,\\mathbb{F}_{25})\\). The 2-element group generated by the Frobenius automorphism acts on \\(\\mathrm{PSU}(3,\\mathbb{F}_{25})\\). Thus, we can form the semidirect product of \\(\\mathbb{Z}\/2\\) and \\(\\mathrm{PSU}(3,\\mathbb{F}_{25})\\), obtaining a group called \\(\\mathrm{P}\\Sigma \\mathrm{U}(3,\\mathbb{F}_{25})\\).<\/p>\n

Puzzle 1:<\/b> Show that \\(\\mathrm{P}\\Sigma \\mathrm{U}(3,\\mathbb{F}_{25})\\) has 252,000 elements.<\/p>\n

Puzzle 2:<\/b> Can you use the description of the Hoffman–Singleton graph in terms of pentagons and pentagrams to prove that its symmetry group contains \\(\\mathrm{P}\\Sigma \\mathrm{U}(3,\\mathbb{F}_{25})\\)?<\/p>\n

The symmetry group of the Hoffman–Singleton graph acts transitively on the ‘flags’, where a flag<\/a><\/b> is a pair consisting of a vertex and an edge incident to that vertex. The Hoffman–Singleton graph is thus called a symmetric graph<\/b><\/a>. <\/p>\n

The stabilizer of a vertex of the Hoffman–Singleton graph is isomorphic to the symmetric group on 7 letters, \\(\\mathrm{S}_7\\). The stabilizer of an edge is isomorphic to \\(\\mathrm{Aut}(\\mathrm{A}_6)\\), where \\(\\mathrm{A}_6\\) is the alternating group on 6 letters. (The group \\(\\mathrm{Aut}(\\mathrm{A}_6)\\) has four times as many elements<\/a> as \\(\\mathrm{A}_6\\).) Both these stabilizers are maximal subgroups of the symmetry group of the Hoffman–Singleton graph.<\/p>\n

There is also a more subtle way to construct the Hoffman–Singleton graph starting from the Fano plane<\/b><\/a>: the projective plane over the field with 2 elements.<\/p>\n

The Fano plane has 7 points and 7 lines, with 3 points on each line and 3 lines through each point:<\/p>\n

\n
\"Fano<\/a>

Fano Plane – Gunther<\/p><\/div>\n<\/div>\n

The symmetry group of the Fano plane has 168 elements. So, the number of different Fano plane structures on a 7-element set is <\/p>\n

$$ 7! \/ 168 = 30 $$<\/p>\n

Call each of these a Fano<\/b>. <\/p>\n

Fix a 7-element set \\(S\\). This set has <\/p>\n

$$ {7 \\choose 3} = 35 $$<\/p>\n

3-element subsets, which we will call triads<\/b>. Choose a triad \\(L \\subset S\\). Since there are \\(30\\) Fanos, each with 7 lines, and just 35 triads, there are <\/p>\n

$$ \\frac{30 \\cdot 7}{35} = 6 $$<\/p>\n

Fanos for which \\(L\\) is a line. <\/p>\n

Puzzle 3.<\/b> Show that for any Fano \\(F\\), there are 14 other Fanos \\(F’ \\ne F\\) that have a line in common with \\(F\\). (That is, some triad is a line in both \\(F\\) and \\(F’\\).)<\/p>\n

Now, fix a Fano and consider all 15 Fanos that have a line in common with \\(F\\). <\/p>\n

To build the Hoffman–Singleton graph, take these 15 Fanos and all 35-element subsets of \\(S\\) as vertices. Draw an edge between any triad and any Fano that has it as a line. Draw an edge between any two 3-element subsets that are disjoint. Never draw an edge between two Fanos.<\/p>\n

The resulting graph is the Hoffman–Singleton graph! It has the 50 vertices corresponding to the 35 triads and 15 Fanos. Each vertex has degree 7. A vertex corresponding to a Fano is connected to 7 triads, since the Fano plane has 7 lines. Each triad is connected to the 3 Fanos that include it and the 4 triads it is disjoint from.<\/p>\n

Puzzle 3.<\/b> Why can the Hoffman–Singleton graph be built this way? Being built from 5 pentagons and 5 pentagrams, it’s not surprising that its symmetry group is connected to the number 5 and the field \\(\\mathbb{F}_{25}\\). But the Fano plane seems unrelated to this. <\/p>\n

My best guess about Puzzle 3 is that it’s connected to the stabilizer of any vertex of the Hoffman–Singleton graph being \\(\\mathrm{S}_7\\). This group can act on a 7-point set, and thus on the set of Fanos.<\/p>\n

The Hoffman–Singleton graph is a (7,5)-cage<\/a><\/b>, meaning a graph where each vertex has exactly 7 neighbors, the shortest cycles have length 5, and it has as few vertices as possible while possessing both these properties. This follows from the fact that the Hoffman–Singleton graph is a Moore graph<\/a>. In fact, it is the largest known Moore graph, apart from complete graphs, and it arose in Hoffman and Singleton’s attempt to classify Moore graphs:<\/p>\n

• Alan J. Hoffman and Robert R. Singleton, Moore graphs with diameter 2 and 3, IBM Journal of Research and Development<\/i> 5<\/b> (1960), 497–504.<\/p>\n

The Hoffman\u2013Singleton theorem<\/a> states that in a Moore graph with girth 5, every vertex must have 2, 3, 7, or 57 neighbors. The existence of one where every vertex has 57 neighbors is unknown.<\/p>\n

For more, see:<\/p>\n

• Hoffman–Singleton graph<\/a>, Wikipedia<\/i>.<\/p>\n

• Andries E. Brouwer, Hoffman–Singleton graph<\/a>.<\/p>\n

• Asif Zaman, Moore graphs with diameter 2 and 3<\/a>. <\/p>\n

The ‘pentagons and pentagrams construction’ of the Hoffman–Singleton graph was first given by Robertson, but it was used to study the graph’s symmetries here:<\/p>\n

• P. R. Hafner, The Hoffman–Singleton graph and its automorphisms<\/a>, Journal of Algebraic Combinatorics<\/i> 18<\/b> (2003), 7–12.<\/p>\n

If you get stuck on Puzzle 2, this paper holds useful clues. They also show that the Hoffman–Singleton graph contains exactly 1260 cycles of length 5. I do not know the answer to this question:<\/p>\n

Puzzle 4:<\/b> Does the symmetry group of the Hoffman–Singleton graph act transitively on the set of cycles of length 5?<\/p>\n

An affirmative answer would explain why the order of the symmetry group is divisible by the number of 5-cycles:<\/p>\n

\\[ \\frac{252,000}{1260} = 200 . \\]<\/p>\n

Spoiler <\/h3>\n

Here is an answer to Puzzle 3, provided by Greg Egan. However, there may be more intuitive ways to count the Fanos that share a line with a given Fano.<\/p>\n

\nFor the Fano:<\/p>\n

{{1,2,4},{1,3,7},{1,5,6},{2,3,5},{2,6,7},{3,4,6},{4,5,7}}<\/p>\n

the 14 other Fanos that share exactly one line with it come in pairs where the common line is each of the 7 lines in the original Fano:<\/p>\n

{{1,2,4},{1,3,5},{1,6,7},{2,3,6},{2,5,7},{3,4,7},{4,5,6}}
\n{{1,2,4},{1,3,6},{1,5,7},{2,3,7},{2,5,6},{3,4,5},{4,6,7}}<\/p>\n

{{1,2,5},{1,3,7},{1,4,6},{2,3,6},{2,4,7},{3,4,5},{5,6,7}}
\n{{1,2,6},{1,3,7},{1,4,5},{2,3,4},{2,5,7},{3,5,6},{4,6,7}}<\/p>\n

{{1,2,3},{1,4,7},{1,5,6},{2,4,6},{2,5,7},{3,4,5},{3,6,7}}
\n{{1,2,7},{1,3,4},{1,5,6},{2,3,6},{2,4,5},{3,5,7},{4,6,7}}<\/p>\n

{{1,2,6},{1,3,4},{1,5,7},{2,3,5},{2,4,7},{3,6,7},{4,5,6}}
\n{{1,2,7},{1,3,6},{1,4,5},{2,3,5},{2,4,6},{3,4,7},{5,6,7}}<\/p>\n

{{1,2,3},{1,4,6},{1,5,7},{2,4,5},{2,6,7},{3,4,7},{3,5,6}}
\n{{1,2,5},{1,3,6},{1,4,7},{2,3,4},{2,6,7},{3,5,7},{4,5,6}}<\/p>\n

{{1,2,3},{1,4,5},{1,6,7},{2,4,7},{2,5,6},{3,4,6},{3,5,7}}
\n{{1,2,6},{1,3,5},{1,4,7},{2,3,7},{2,4,5},{3,4,6},{5,6,7}}<\/p>\n

{{1,2,5},{1,3,4},{1,6,7},{2,3,7},{2,4,6},{3,5,6},{4,5,7}}
\n{{1,2,7},{1,3,5},{1,4,6},{2,3,4},{2,5,6},{3,6,7},{4,5,7}}<\/p>\n<\/blockquote>\n

The picture of the pentagons and pentagrams construction was created by Claudio Rocchini and placed on Wikicommons<\/a> under a GNU Free Documentation license<\/a>. <\/p>\n

\n

Visual Insight<\/i> is a place to share striking images that help explain advanced topics in mathematics. I\u2019m always looking for truly beautiful images, so if you know about one, please drop a comment here<\/a> and let me know!<\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

This is the Hoffman–Singleton graph<\/a>, a remarkably symmetrical graph with 50 vertices and 175 edges. There is a beautiful way to construct the Hoffman–Singleton graph by connecting 5 pentagons to 5 pentagrams.<\/p>\n

<\/div>\n","protected":false},"author":66,"featured_media":2268,"comment_status":"open","ping_status":"closed","sticky":true,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[22,23,2],"tags":[],"class_list":["post-2195","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-graphs","category-groups","category-images-library"],"jetpack_featured_media_url":"https:\/\/blogs.ams.org\/visualinsight\/files\/2016\/02\/hoffman-singleton_graph.png","jetpack_shortlink":"https:\/\/wp.me\/p42Vmc-zp","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/2195","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/users\/66"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/comments?post=2195"}],"version-history":[{"count":57,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/2195\/revisions"}],"predecessor-version":[{"id":3064,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/2195\/revisions\/3064"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/media\/2268"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/media?parent=2195"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/categories?post=2195"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/tags?post=2195"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}