Discussion about this post

User's avatar
Beren Gunsolus's avatar

Thanks, this is cool! Also, please forgive the math below :)

I've been thinking about networks a bunch recently: there's a famous problem (the "degree-diameter problem") that asks "what's the largest network where any node in it has at most k neighbors, and any two nodes are at most d connections away?".

It's easy to find upper bounds: for example, if k=7 and d=2, a given node has at most 7 neighbors, and each such neighbor has at most 6 other neighbors, for a total of at most 1 + 7 + 7*6 = 50 nodes.

The above type of bound (the "Moore bound") is generally too optimistic: besides uninteresting examples (where k<3 or d<2), there are only two other known examples that attain the bound: a ten node network (where k=3 and d=2: it's called the "Petersen graph", very famous. There's a whole book on this little network!), and a 50 node network (where k=7 and d=2, called the "Hoffman-Singleton graph"). It's unknown if there are any other examples... but it is known that if there is another, it must have exactly 3250 nodes, each with 57 neighbors: figuring out if such a network exists or not is a somewhat famous open problem!

The 50 node network above is very symmetrical, with 252,000 symmetries (I helped my company design a t-shirt with this network on it, though it only displays 10 of those symmetries), and it can be used to construct a 100 node network with symmetries one of the 26 "sporadic groups". I recently came up with a model for the 50 node network, based on a dodecahedron ((basically) with the 30 edges, 12 faces, 5 inscribed cubes, and three added points, representing the 50 nodes, and some rules describing the connections). Networks are cool!

Expand full comment
1 more comment...

No posts