Things About NAP Scores

I've been thinking a lot about asymmetric graphs this summer. After making my game NAP, I've been thinking about the best way to make asymmetric graphs. The game works like this: You're given some symmetric graph and you need to add vertices and edges economically in order to make the graph asymmetric (i.e. make the graph have no nontrivial automorphisms). I say economically because the goal is to minimize your score, where a new edge gives you 1 point and a new vertex gives you 2 points. It's a fun daily puzzle and good exercise for those geometric brain cells. But naturally, I can get a bit competitive with it. It's already tricky sometimes to get a reasonably low score for many of the puzzles, but I want the best score.

Since each starting graph is different, there's no way to easily define the best score arbitrarily. Instead, we might ask a better question:

Before we start, it'll be helpful to find the smallest asymmetric graph. To do so, we'll start with the following theorem.

Now we can start looking at graphs with a small number of vertices n. When n = 1 or n = 2, it's easy to see there are no asymmetric graphs (ignoring, for convenience, that the graph of 1 vertex is technically asymmetric; we'll see why it's nice to call this symmetric later). When n = 3, there are only four graphs we need to check:

Similarly for graphs of five vertices, we can look at those graphs which are connected and have $\frac{1}{2}\cdot \left(\begin{array}{c}5\\ 2\end{array}\right)=5$ edges or less. This ends giving us eight different graphs, which are all also symmetric.

Finally, for graphs of six vertices, we can use the same techniques to find four graphs that are connected and have $\lfloor \frac{1}{2}\cdot \left(\begin{array}{c}6\\ 2\end{array}\right)\rfloor =7$ edges that have no automorphisms. So, with their compliments, we reach the eight asymmetric graphs with six vertices:

We can see that the graph in blue is the cheapest asymmetric graph, as in it has the fewest nodes and edges. So, when we are solving for W(n) for n < 6, we might consider working towards this cheapest asymmetric graph. Because of this, we will call this graph the cheap ass. graph (for cheap asymmetric graph), or C for short.

To start, when n = 1, we only have one choice for the graph. We need five vertices and 6 edges to get to C, so both the best and worst score for starting with a graph of one vertex is W(1) = 5*2 + 6 = 16. For n = 2, we would be lucky to start with two vertices connected by an edge, but we must consider the worse case of two vertices not connected by an edge; in this case, we would need four vertices and six edges, for a total of W(2) = 4*2 + 6 = 14. Similarly, for three nodes we would start with three unconnected vertices, so we'd need three vertices and six edges to get to C, meaning W(3) = 3*2 + 6 = 12.

To recap, we have

With n = 4, things get more interesting. We can notice that if we start with four unconnected vertices, we'll need only two vertices and six edges to get to C, giving us W(4) = 10. But, since our goal is to find the worst possible starting graph with four vertices, we can perhaps look for a graph that isn't a subgraph of the eight six-vertex asymmetric graphs above. The only such graph with four vertices is the complete graph K₄. Here's where things get tricky: starting with K₄, what's the best possible score?

Because K₄ is not a subgraph of any of the asymmetric graphs above, we know we must have at least seven vertices, so let's go ahead and add the three more we need. Now our goal is to connect these three vertices to the K₄ with the fewest amount of edges. Well, we clearly can't use fewer than three edges, since if we could, we might as well not use one of the added vertices. We'll first notice something critical:

Here, we can see we at least need to add a fourth edge. Doing so allows us to make this configuration:

Before we go to five vertices, we naturally notice a pattern. Starting with zero vertices and going up, we have scores of 18, 16, 14, 12, and 10 for n from 0 to 4. It becomes really tempting to say W(n) = 18 - 2n. Let's see how long we can maintain this model...

For a starting graph of five vertices, we first have to ask what the worst possible starting graph is. Starting with 5 unconnected vertices is actually kind of nice, since we're only one vertex and six edges from C, so a score of 8. So we'll consider the other extreme: the complete graph K₅. Should we consider K₅ minus any edges, since this might be as hard as solving K₅ but in the end will need one extra edge? Well, at least in this case, it seems like no; removing an edge would make it closer to solving the K₄. So, let's find the best score for K₅.

It's actually pretty hard to find the best score, so let's first find a way to anisocrate it with a decent score. One way to do this is with what I call the Tall Hat Method. I picture in my head a party of wizards standing around a magical pentagramal carving in the floor, preparing some kind of ritualistic spell or something. These wizards are pretty petty, though, and like to outclass each other by wearing a taller hat than their neighbor. It looks like this:

It's clear that no hat is isomorphic to any other hat, which means that the original vertices can no longer permute, and we made sure to not add any symmetry. Without a solid proof, we'll claim that this method of adding vertices and edges does break all symmetries. This means that for any complete graph (with four or more vertices), we can anisocrate it with tall hats. We can do this on K₄ and notice that, needing only two hats, we have three added vertices and five added edges, making a score of 11. Not optimal, but not bad either. On our K₅, we only need three hats, so that makes six added vertices and nine added edges for a score of 21. Indeed, we can continue this pattern for any complete graph of n vertices, noticing that the kth hat has a score of 3k + 1 and doing some algebra to derive a formula:

So, for any complete graph of n vertices, we can say that we can at least get a score of $\frac{3n^2-7n+2}{2}$.

What I'm about to do is kind of ill-mannered, devious, and vile. I want to make an assumption, without proof, about graphs, so that working with our W(n) function is a bit easier. It's a pretty believable assumption to me, but I'll make it clear when I use it and what the alternative would be if it were false.

But I think we can do better. Perhaps we can stick with the hat idea, but consider whether or not we always need to add an extra vertex to make a new hat. That is, can we make nonisomorphic hats with the same number of vertices? Yes! I call this the Antler Hat Method, imagining that during the holiday season, the wizards festively meet for their magic circle after turning their hats into reindeer antlers. We can partition the nodes on a hat into two antlers in $\lceil \frac{n}{2}\rceil$ distinct ways.

Things don't actually improve until K₇; the Tall Hat Method gives us a score of 50 whereas the Antler Hat Method gives us a score of 47. A difference of 3 isn't great but it's not negligible. Because this new method, in a sense, recycles hats more and more as n increases, the Antler Hat Method far outpaces the Tall Hat Method for, say, n = 1,000,000,000.

Yet, we can probably still do better. The Antler Hat Method only uses two antlers, but if we used more antlers, we can keep conserving resources, at least when possible. We might call this the Partition Hat Method, because it depends on the number of partitions of the number of nodes. For that matter, we don't even need to just use antlers, we can connect our antlers in unique ways to save on resources. We might call this the Party Hat Method, because we're looking for unique asymmetric hats that have no certain form. And who says we need a new hat for each wizard? Perhaps if we arrange the hats in a certain way, we can reuse old ones. But wait, does each wizard need a hat, or can some wizards maybe share a hat? Okay...it's starting to get really hard to find an optimal algorithm or method to solving complete graphs. Maybe we can shift our focus to other types of graphs.

Cycles

Whereas with the complete graphs, finding an optimal strategy got more and more difficult, with cycles things are really nice. We can prove that for any cycle with six or more vertices, the best score is always 2. Recall that there are no asymmetric graphs with five or fewer vertices, so this only holds for cycles with more than five vertices.

Complete Balanced Binary Trees

Complete balanced binary trees (BBTs or perefect binary trees) are an interesting specimen here. They are both super simple structures and rich in symmetry. With just the fifth tree, which has $2^5-1=31$ vertices, we get a whopping 32,768 automorphisms! Intuitively, at least for me, the simple structure and rich symmetry conflicted, so I didn't know what to expect in terms of best possible score. But we can notice something crucial: we kind of only have to worry about the leaf nodes. And actually only every pair of leaf nodes. That is, if we don't add an edge to a leaf node or add an edge to its sibling, then an automorphism exists that just swaps that leaf node with its sibling. Let's call ${\gamma }_n$ the lowest possible score for a balanced binary tree with $2^n-1$ nodes. Then ${\gamma }_n$ is at least a quarter of the number of leaf nodes (the number of edges it would take to make sure each leaf or its sibling has an added edge). Well, this is just $2^{n-2}/2=2^{n-3}$. So $2^{n-3}\le {\gamma }_n$.

Here is a strategy for guaranteeing ${\gamma }_n\le 2^{n-2}-1$:

So, we have our score bounded by $2^{n-3}\le {\gamma }_n\le 2^{n-2}-1$. But consider the following strategy:

It seems visually clear that this should always work, so I'll forgo a proof, perhaps writing it up at a later time. But this means that ${\gamma }_n=2^{n-3}+1$. And we can reason that we can't do any better than that, i.e., we can't anisocrate a balanced binary tree of $2^n-1$ nodes in only $2^{n-3}$ edges. Well, if this were the case, this would only be able to connect every pair of leaves to some other pair of leaves. You can check that we can always swap some nodes' children to yield an automorphism.

Kill Ratio

In studying balanced binary trees, we saw something really cool: the fifth BBT had 31 nodes and took only 5 edges to anisocrate. Amazingly, those 5 added edges killed 32,768 automorphisms! We can consider what I'll call the 'kill ratio' of that binary tree: the ratio between the number of starting automorphisms and least number of edges needed to anisocrate, $\frac{32,768}{5}=6,553.6$. What is the kill ratio for any BBT? And can we find a better kill ratio?

Firstly, what are we really looking for? Let's define the kill ratio of a graph G as $R_G=\frac{|Aut(G)|}{{\lambda }_G}$, where ${\lambda }_G$ is the best possible isocration score. For reasons explained here, the number of automorphisms of a BBT with $2^n-1$ nodes is $2^{2^{n-1}-1}$. Combining that with what we found in the last section, we get a function that describes the kill ratio of a BBT with $2^n-1$ nodes: $$\begin{array}{r}{R}_{{\text{BBT}}_n}=\frac{2^{2^{n-1}-1}}{2^{n-3}+1}.\end{array}$$

This function grows really fast, so the larger the BBT, the greater the kill ratio. And that's really cool, because you can have so many automorphisms broken with so few edges. In other words, symmetry is fragile.

So what about other types of graphs? We saw that cycle graphs (for $n>5$) can always be anisocrated in two edges. For some $n$, an $n$-cycle has $2n$ automorphisms, so $$\begin{array}{r}{R}_{n\text{-cycle}}=\frac{2n}{2}=n.\end{array}$$ This is really nice! It's kind of a linear baseline for comparing other kill ratios. For now, let's look at only those graphs that can be optimally anisocrated with just new edges. How do other graphs compare?

Archipelagos

We'll look at the kill ratio of graphs of n vertices with no edges, what I like to call archipelagos. When $n>6$ we have an easy strategy to always ensure a score of $n-1$ (for $6<n<15$, I think this is optimal). We can simply form a graph of the form:

This isn't optimal for $n\ge 15$, though, since we can make one of these graphs with 7 vertices and one of these graphs with 8 vertices, saving us an edge. Let's focus on the unoptimal $n-1$, since that extra edge hopefully won't affect us too much. So, how many automorphisms are there of an n-chipelago? Well, the vertices are allowed to permute freely, so there are $n!$ combinations. That gives us a kill ratio of $$\begin{array}{r}{R}_{n\text{-chipelago}}=\frac{n!}{n-1}=n\cdot (n-2)!\end{array}$$

This kill ratio is the best yet!

I think that maybe probably possibly any other family of graphs have kill ratios between these cycles and archipelagos. A 'family of graphs' is kind of non-rigorous term, so let's just say it's a set of 'similar' graphs that has only one graph of n vertices for any number n, up to isomorphism. This way, we're able to push the non-rigor from 'family' to 'similar'.

Summary and Open Questions

We started with a dream of finding a function that takes in the number of starting nodes of a graph and tells us whether we could have done a better job anisocrating the graph or not in hopes of being a better NAP player. We called this function W(n) and found the upper bound $$\begin{array}{r}W(n)\le \frac{3n^2-7n+2}{2}\end{array}$$ by analyzing complete graphs. So, for example, if we started with five nodes and scored 22, then we know we could've done better, since our bound says $W(5)\le 21$. But we found ways to keep optimizing this strategy and shave off points. Describing functions for these strategies proved harder and harder, and showing one strategy was optimal felt even harder.

We moved on to solve more specific kinds of graphs. Cycles proved to be really easy, as we can always anisocrate them with two edges. BBTs are nice too, since we can also strictly use edges, and only use $2^{n-3}+1$ edges. This made us curious about the starting-automorphism-count-to-optimal-anisocration-score ratio. This ratio is a sort of metric for measuring the fragility of a graph's symmetry. For cycles, it's really nice, since that ratio is equal to how many nodes are in the cycle. The BBTs have a pretty good one; its exponential growth shows that its symmetry is very fragile. We then saw that a group of unconnected vertices, which we called archipelagos, had an extremely steep kill ratio function.

I'm still very curious about this game. Aesthetically, the notion of optimally adding to a graph to break all its symmetries is beautiful and fun and tells us a lot about symmetry. In practice, I think it's just really fun. And in practicality, I think studying this asymmetry may have some implication in group theory by way of Frucht's Theorem, which I'll write about in the future. The asymmetry of graphs is also important in logic trees and SAT solvers in formal methods. All in all, studying the symmetry and asymmetry of this game and these graphs lead to very interesting things and leave me with many questions...

I would love to receive ideas, proofs, counterexamples, mistakes, etc. on any of the topics here, especially Conjecture 1 and Conjecture 2, as well as better or even optimal strategies for anisocrating complete graphs, a function that more accurately describes optimal anisocration of archipelagos, and definitely a tighter bound on W(n). You can send any of this and more to my email: ian [at] beanway [dot] me.