I’ll bet nobody, except some people I’ve told about it before, could identify what this is.
Give up? OK, it’s a string-art representation of three disjoint Hamiltonian cycles in a degree-3 diameter-3 Kautz graph. A what? Unfortunately, a Kautz graph is not an inherently easy thing to grasp or describe, and the Wikipedia article does a particularly lousy job. (Yeah yeah, I know, I could write my own, but I’ve had enough of Wikipedia politcs already.) We have some decent descriptions that we’ve used for presentations at work (it’s the topology used in our machines), but what’s on the website doesn’t seem that great. So, here are some of the basics.
A degree-N Kautz graph consists of nodes which each have N input and N output links (arcs, edges, whatever terminology you prefer) arranged in a particular order. Specifically, each node has a number expressed in base N+1, such that no two adjacent digits are the same. The node’s output links are defined by shifting its number left and filling on the right with one of the three eligible digits; its input links are defined by shifting right and filling on the left likewise. So, for example, node 132 (in a degree-3 graph) will have output links to 320/321/323 and input links from 013/213/313). Why on Earth is any of this interesting or useful to anyone but a graph theorist? Because it turns out that Kautz graphs have a lot of interesting properties. For example, a degree-3 diameter-6 Kautz graph guarantees that any two nodes out of 972 have three completely separate paths each involving no more than six hops between them. For the same number of nodes, a hypercube would require ten hops and a torus fifteen. That’s why SiCortex uses Kautz graphs to connect nodes, with the SC072/SC648/SC5832 being degree-3 networks of diameter 2/4/6 respectively. The number of nodes in a Kautz graph of degree k and diameter d is (k+1)*kd-1. For k=3 and d=6, that’s 4*35 or 972, times 6 cores per node = 5832, hence the name of the system.
Kautz graphs are interesting to work with. For one thing, it’s almost impossible to conceptualize which nodes are connected to which others, through which paths. Can you tell me how to get from node 3101 to node 0321? Uhhh. Well, there’s always one obvious path formed by simply shifting in the digits of the destination one by one (in this case 3101 to 1010 to 0103 to 1032 to 0321), but there may be shorter paths and by the way good luck finding the other two that are guaranteed to exist. In practical effect, the connections and routes seem just as random as those in some arbitrary collection of nodes on the internet. Then there’s the issue of tiling a Kautz graph, or breaking it down into topologically-equal pieces so (for example) you can make a diameter-4 or diameter-6 system using the same pieces. That’s some of SiCortex’s secret sauce, but I don’t need to worry about giving away our methods because I don’t know them and even if I did I doubt that I’d understand them. Basically we just have a few guys who are really smart and have studied this a lot, and they seem to know how to do it.
Of course, none of this explains why I went to the effort of creating a string-art manifestation of a Kautz graph. Mostly it’s just because I felt like the versions on slides and such were all a bit disappointing. There’s just something about this version’s physical reality that makes it more compelling. As it turns out, actually wrapping the strings around the posts made me more acutely aware of some of the Kautz graph’s strange symmetries than I had been before. There was also a bit of an intellectual challenge involved. Pretty early I hit on the idea of dividing the links into three cycles and using different colors to represent them, and then I had to figure out how to find those cycles. In fact, I spent more time writing the program to do that than I did physically building the thing, and one of our local Kautz gurus was actually a bit surprised to find that there even were three disjoint Hamiltonians in a diameter-3. Lastly, of course, I did it because it’s unique. I’m pretty darn sure nobody else has one, and in today’s mass-produced world the idea that I have something that would not exist if I hadn’t made it myself is pretty satisfying.
UPDATE: one of the aforementioned smart people offered the following corrections and graciously gave permission for me to include them here.
In the second paragraph, you say that any pair of nodes will have three separate paths with no more than 6 hops between them. In fact, the first (shortest) path has no more than 6 hops, the second typically has 7, and the third in a few cases requires 8 hops.
All paths can be thought of as shifting in the destination node number. Short paths arise when the trailing digits of the origin node number correspond to leading digits of the destination node number, so fewer shifts are required than the diameter.
The alternate paths to a destination arise by shifting in a “wrong” digit (one which does not take you on the shortest path to the destination), followed by shifting in the correct digits of the destination address.
In a way, that underscores the point I made about how hard it is to conceptualize Kautz graphs. Consider the “shifting in a wrong digit” part. It’s fairly obvious that doing so will give you a new path, but considerably less obvious that the paths thus derived will be totally separate from one another. Kautz graphs are full of little surprises like this, which is what gives them their charm.