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!
That is fascinating! I know next to nothing about networks, but it is very easy to see why they would be such an interesting, rewarding, and significant area of investigation.
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!
That is fascinating! I know next to nothing about networks, but it is very easy to see why they would be such an interesting, rewarding, and significant area of investigation.