NAP — a game about symmetry
How To Play
Previous Puzzles
Practice/Sandbox
What is NAP?
NAP stands for No Automorphisms, Please!
The goal is to add edges and nodes to the
graph
to break all symmetries. The fewer added edges and nodes, the better! There's a new puzzle every day.
What counts as a symmetry?
In this case, a symmetry is any 'relabeling' of the nodes that maintains the structure of the graph. If we take some node, we can call the set of all nodes connected to it via some edge its neighbors. Then a symmetry of a graph shuffles some nodes around, but makes sure each node has the same neighbors. Such a symmetry is called an
automorphism
.
For example, we can label the following graph and its one symmetry.
Sometimes, the automorphisms look like the standard symmetry we're used to—reflections and rotations—like how the one above looks like a reflection. But often it can be more subtle and not look like any geometric symmetry. For example, the following is an automorphism that doesn't conform to our standard notion of reflection or rotation:
Note that the actual physical movement of the graph doesn't affect its symmetries, so the following two graphs are the same:
so they have the same symmetries.
This is an example of a graph with no automorphisms (a winning graph!):
Manipulating the graph
Click the
Edit
button, then click
Add Node
and click anywhere near the graph to add a node. To add an edge, click
Add Edge
, then drag click your cursor from one node to another. When you think you have a graph with no symmetries, click
Check Symmetries
! You get 1 point for each edge added and 2 points for each node added. Your goal is to minimize your score.
If a node leaves the screen by accident, you can zoom out (or in) with the navigation buttons.
More about graph symmetries
I break down some math behind graph asymmetries and analyze best possible scores
here
! Please check it out if you're interested in this game!
Why?
Why this game? Firstly, automorphisms are important in so many branches of math, like graph theory, group theory, linear algebra, etc. Developing the intuition for how objects can act on their own and be mapped to themselves is crucial in understanding underlying ideas in these branches of math. The thing I found with automorphisms, though, is that they're not entirely intuitive. I struggled for a long time understanding automorphisms and their importance, so I created this game to try to bridge the understanding-gap of automorphisms in math, through the lens of graph theory. Secondly, I found it really fun and a good geometric exercise. And that on its own makes a game worth making! But with the added pedagogical aspect, this game strives to build an instinct for automorphisms in all branches of math.
The computation is powered by
SageCell
and the graph interface is powered by
vis.js
. Code can be found on my
Github
. Pull requests welcome! :)
Feedback is also welcome: feedback [ at ] beanway [ dot ] me
NAP 1.3.0
Got It!
×