Snarks!
Searchers after horror haunt strange, far places. For them are the catacombs of Ptolemais, and the carven mausolea of the nightmare countries. They climb to the moonlit towers of ruined Rhine castles, and falter down black cobwebbed steps beneath the scattered stones of forgotten cities in Asia. The haunted wood and the desolate mountain are their shrines, and they linger around the sinister monoliths on uninhabited islands.
The Picture in the House, H.P. Lovecraft
This Lovecraft quote is a fairly accurate description of my research style. I like to explore strange things and try to understand them. And there are a lot of strange things in the world.
Today I would like to invite you to come falter with me down black cobwebbed steps to meet a thing only whispered about in the carven mausolea of university math departments: snark graphs.
Snarks are undirected graphs where every vertex has exactly three incoming edges (these are called cubic or 3-regular graphs) whose edges can’t be colored with only three colors. The term "snark" in this context was coined by Martin Gardner in 1976 in an article in Scientific American, inspired by Lewis Carroll's poem The Hunting of the Snark.
All snarks are non-planar. This means that you can’t draw them on a 2D surface without crossing edges. This turns out to be quite important for what I’m interested in using them for!
The smallest snark is the Petersen graph, discovered by Julius Petersen in 1898. It has 10 vertices and 15 edges, arranged in a distinctive pattern that makes it one of the most famous graphs in all of mathematics. From this cool blog post:
Here we have the Petersen graph, which, according to Donald Knuth, “serves as a counterexample to many optimistic predictions about what might be true for graphs in general.” It is not that the Petersen graph is stubborn! But it marches to the beat of a different drummer. If you have not met it before, prepare to be delighted.
The smallest snark — the 10 vertex 15 edge Petersen graph. You can try coloring each edge one of three colors (for example, red, green, blue) and what you will find is that you can’t do that without two edges of the same color being connected to a vertex. Also you can’t rearrange the position of the vertices to remove all crossing edges. Interestingly those two things that sound very different are actually two different aspects of the same thing!
Also can’t help but notice the similarity to the sigil of Baphomet …. such occult!
The sigil of Baphomet, which is not exactly the Petersen Graph, but is fairly close.
The next smallest snarks have 18 vertices, including the smallest Flower snark and the Blanusa snarks.
The 18 vertex 27 edge second Blanusa snark. Yes, there is a first Blanusa snark also.
Here’s one that’s a little bit bigger, which is called the first Loupekine snark.
The 22 vertex 33 edge first Loupekine snark. And again yes, there is a second one. Also yes, it does look like a codpiece, and if you want to get me one with this snark on it, I will wear it.
This one is called the Szekeres snark.
The 50 vertex 75 edge Szekeres snark.
Here’s one last one, the Descartes snark, the naming of which has an interesting backstory.
The 210 vertex 315 edge Descartes snark.
Snarks are rare. We know ways to construct infinite families of snarks (like the Flower snarks discovered by Rufus Isaacs), but finding all possible snarks of a given size is challenging.
Ising Models on Snarks
I suspect that Ising models defined on snarks might have peculiar and interesting properties. Here are some reasons for this intuition:
Each vertex is connected to exactly three others. This means that these graphs are locally homogeneous — all vertices kind of see the same type of environment.
They are non-planar, which is a requirement for making the computation of ground states NP-hard (planar graphs have polynomial time algorithms to generate ground states).
The four-coloring thing means that if I were to set all couplings to antiferromagnetic, the ground state would be highly frustrated and be a superposition of a lot of states and potentially have weird properties.
There are small snarks (like the Petersen Graph) where it’s possible to numerically calculate the partition function and the properties of the paramagnet to spin-glass phase transition, so we can get a reliable picture of what’s going on (at least for small snarks).
I couldn’t find any existing research on Ising models on snarks. Ahh the joys of having interests so esoteric that no one else shares them :-)
Here’s an animation of the dynamics of the Ising model with all couplings set to antiferromagnetic on the Petersen graph while varying the temperature. At high temperature, all states become equally likely (paramagnet with signature linear dependence of per spin energy on temperature), and as the temperature is lowered the system undergoes a smooth phase transition to an ordered antiferromagnetic (AFM) state with 15 degenerate ground states each corresponding to a configuration with exactly one unsatisfied edge.
Here’s the same visualization on the second Blanusa snark, again with all AFM couplers. Here we can see the emergence of a spin-glass phase at low temperatures — the system consistently gets stuck in different local energy minima at low T.
Same kind of behavior for the first Loupekine snark.
Tangled on Snark Game Graphs
Alright, so at least for all AFM couplers you get a spin glass phase even for very small snarks. This seems promising for Tangled played on snarks because a player can probably create the conditions for a glassy phase even on a small game graph, which I think is required for making computation of the score a hard problem (if there is no frustration we can easily find the ground states of the Ising model by just ensuring all the edge couplings are satisfied). Anecdotally, I have not been able to win a single game of Tangled on the Blanusa snark against even mid-tier pure Monte Carlo Tree Search agents.