# 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.

*asymmetrize*and

*desymmetrate*get the idea across, which is probably what I should be striving for, but are really lame. Busting out a list of Latin/Greek roots, I've decided on

**anisocrate**, which will be our cool-sounding word for the act of making a symmetric graph asymmetric. (I also made up and like

*aggrechirate*and

*anihichirate*for anisocrations that involve only adding nodes/edges and only subtracting nodes/edges, respectively.) Thus, the goal of NAP is to give the cheapest anisocration of the starting graph.

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

*Can we define a function that, given a number of vertices n, returns the worst possible score a perfect player can get with a starting graph that has n vertices?*In other words, we want a function

*W(n)*such that if we start with a graph that has

*n*vertices and we score greater than

*W(n)*, we are certain we can do better.

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

*Proof.*

*If \(G\) is symmetric, then there exists some nontrivial automorphism \(A\) of \(G\). We want to show that \(A\) is also an automorphism of \(G'\). Let \(V\) be the set of vertices of \(G\). We have for all vertices \(v\) of \(V\), there is some vertex \(w\) such that \(A(v) = w\). If \(N_x\) is the set of neighbors of a vertex \(x\) (the set of all vertices connected via one edge to x), then, by definition, \(A(N_x) = N_x\). Now let \(v'\) be the corresponding vertex to \(v\) of \(G'\). Then, because \(G'\) is the compliment graph of \(G\), \(N_{v'} = V - N_v\). So we have that \begin{align} A(N_{v'}) &= A(V - N_{v})\\ &= A(V) - A(N_v) \\ &= V - N_v\\ &= N_{v'}.\end{align} Thus \(A\) is an automorphism of \(G'\). \(\Box\)*

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:

*n = 4*. This is a bit tougher, because the number of graphs of

*n*vertices rises quickly as

*n*increases. But here we can be a little tricky (or lazy!), and use Theorem 1 to say that we actually only need to check graphs with 4 vertices and \(\frac{1}{2}\cdot\begin{pmatrix}4\\2\end{pmatrix} = 3\) edges, since if a graph had more than three edges, we would have already considered its compliment, which must have three or less. Furthermore, we only have to check such graphs that are connected, since if we found a disconnected asymmetric graph of four vertices, we would need an asymmetric graph of less than four vertices. Using these tricks, we're able to shrink our considerations down to only two graphs, both of which are clearly symmetric:

Similarly for graphs of five vertices, we can look at those graphs which are connected and have \(\frac{1}{2}\cdot\begin{pmatrix}5\\2\end{pmatrix} = 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\begin{pmatrix}6\\2\end{pmatrix}\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

*W(0) = 18*

*W(1) = 16*

*W(2) = 14*

*W(3) = 12*

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:

*Remark 1.*When starting with a complete graph, we need to 'interact uniquely' with every starting vertex except for one. Otherwise if we have more than one vertex not interacted with uniquely, we can define some automorphism that permutes those vertices.

Here, 'interacting uniquely' means that we need to add an edge to each starting vertex, connecting it with some unique subgraph. For example, we can try adding the three nodes to our

*K₄*without interacting with all but one starting vertices: But this configuration allows us to swap those uninteracted vertices. We can try to interact with all but one starting vertices, but do so non-uniquely: This, of course, doesn't work either.

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

Asymmetric! We added three vertices and four edges, so we have a score of*W(4) = 10*. This happens to be the same score as starting with four unconnected vertices. We'll see that things only get more complicated.

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 *k*th hat has a score of *3n + 1*
and doing some algebra to derive a formula:

## Work

We notice that the \(h\)th hat gives a score of \(3h + 1\). Using the finite summation formula, we get \begin{align} \frac{h(4 + 3h + 1)}{2} = \frac{3h^2 + 5h}{2} \end{align} total points after \(h\) hats. Notice, though, that \(K_n\) only needs \(n-2\) hats, so we can plug in \(h = n-2\) to get \begin{align} \frac{3(n-2)^2 + 5(n-2)}{2} &= \frac{3(n^2 - 4n + 4) + 5n - 10}{2}\\ &= \frac{3n^2 - 12n + 12 + 5n - 10}{2}\\ &= \frac{3n^2 - 7n + 2}{2}. \end{align}
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.

*Conjecture 1.*For

*n > 4*, the complete graph of

*n*vertices is the worst possible starting graph of all graphs with

*n*vertices.

Assuming this, we can immediately start to bound

*W(n)*.

*Theorem 2. For \(n\) starting vertices, the worst possible score a perfect player can make is \(W(n) \leq \frac{3n^2 - 7n + 2}{2}\).*

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.

This means we get a pattern that looks likeHats h |
Vertices of hth Hat |
Edges of hth Hat |
Score of hth Hat |
Total Score |
---|---|---|---|---|

1 | 1 | 2 | 4 | 4 |

2 | 2 | 3 | 7 | 11 |

3 | 3 | 4 | 10 | 21 |

4 | 4 | 5 | 13 | 34 |

5 | 4 | 5 | 13 | 47 |

6 | 5 | 6 | 16 | 63 |

7 | 5 | 6 | 16 | 79 |

8 | 6 | 7 | 19 | 98 |

9 | 6 | 7 | 19 | 117 |

10 | 6 | 7 | 19 | 136 |

11 | 7 | 8 | 22 | 158 |

... | ... | ... | ... | ... |

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.

*Theorem 2.*For any cycle graph with more than five vertices, the best score is 2.

*Proof.*

*We'll first want to show that no cycle has a best score of 1, i.e. adding an edge won't make a graph asymmetric. Well, if such an edge connected v and w, then there would be an automorphism that moves v to w and w to v (think reflectional symmetry still exists in the graph).*

We can now show a two-move strategy that always works on cycles. Consider some node v, and call the node two places to the right v+2 and the one three places to the right v+3. Connecting an edge from v to v+2 and an edge from v to v+3 creates an asymmetric graph. To prove this, suppose there existed some automorphism A of this graph. Notice that v has degree 4, v+2 and v+3 both have degree 3, and all else has degree 2. By nature of automorphisms, A(v) = v (A must fix v), since there is no other vertex of degree 4. Now, A must either fix v+2 and v+3, or swap them. If A doesn't fix them, then we can see that distance between v+2 and v is 2, while the distance between v+3 and v is 3 from one direction and at least 3 in the other direction. Since automorphisms preserve distance between vertices and fixed points, this isn't possible. If A fixed v+2 and v+3, then we can see that all other nodes must be fixed, and we're left with the trivial automorphism. Thus, the only possible automorphism is the trivial automorphism, and the graph is asymmetric. \(\Box\)

We can now show a two-move strategy that always works on cycles. Consider some node v, and call the node two places to the right v+2 and the one three places to the right v+3. Connecting an edge from v to v+2 and an edge from v to v+3 creates an asymmetric graph. To prove this, suppose there existed some automorphism A of this graph. Notice that v has degree 4, v+2 and v+3 both have degree 3, and all else has degree 2. By nature of automorphisms, A(v) = v (A must fix v), since there is no other vertex of degree 4. Now, A must either fix v+2 and v+3, or swap them. If A doesn't fix them, then we can see that distance between v+2 and v is 2, while the distance between v+3 and v is 3 from one direction and at least 3 in the other direction. Since automorphisms preserve distance between vertices and fixed points, this isn't possible. If A fixed v+2 and v+3, then we can see that all other nodes must be fixed, and we're left with the trivial automorphism. Thus, the only possible automorphism is the trivial automorphism, and the graph is asymmetric. \(\Box\)

## 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} \leq \gamma_n\).

Here is a strategy for guaranteeing \(\gamma_n \leq 2^{n-2}-1\):

And it's true we can shave off a couple of these lines. But, as we'll see, there might be a better way to do it.So, we have our score bounded by \(2^{n-3} \leq \gamma_n \leq 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{align}R_{\text{BBT}_n} = \frac{2^{2^{n-1}-1}}{2^{n-3}+1}.\end{align}

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{align}R_{n\text{-cycle}} = \frac{2n}{2} = n.\end{align} 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 <1 5\), I *
think* this is optimal). We can simply form a graph of the form:

This isn't optimal for \(n\geq 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{align}R_{n\text{-chipelago}} = \frac{n!}{n-1} = n\cdot(n-2)!\end{align}

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'.

*Conjecture 2.*Any family of graphs has a kill ratio function that eventually resides between that of cycles and archipelagos.

## 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{align}W(n) \leq\frac{3n^2 - 7n + 2}{2}\end{align}
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)\leq21\). 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.