# How dense is the set of asymmetric graphs?

On $n$ nodes, we have $2^{n(n-1)/2}$ graphs. Asymmetric graph is a graph that has only trivial automorphism. We known that asymptotically almost all finite graphs are asymmetric. Therefore, in the limit, the ratio of asymmetric graphs approaches 1.

However, I did not find any reference that provides lower bound on the number of asymmetric graphs on $n$ nodes. What is known about the density of asymmetric graphs as a function of the number of nodes $n$?

-
add comment

## 2 Answers

I don't have a reference, but I suspect that the most natural way to prove that almost all finite graphs are asymmetric is by giving a good estimate on how few symmetric graphs there are, so check where you got the result that almost all finite graphs are asymmetric.

The union bound works: Add up the counts of graphs fixed by each permutation. For any nontrivial permutation $\pi \in S_n$, consider the action on the $n \choose 2$ edges. If there are $r$ orbits on the edges, then the number of graphs fixed by $\pi$ is $2^r$ because there is one independent binary choice per orbit.

For example, if $\pi = (1~2)$, then there are $(n-2)$ orbits of size $2$, and one edge switched by $\pi$, and $n-2 \choose 2$ edges which are not moved at all by $\pi$. So, the number of graphs fixed by $\pi$ is smaller than the total number of graphs by a factor of $2^{n-2}$. There are $n \choose 2$ transpositions, so out of all graphs, at most ${n \choose 2} 2^{-(n-2)}$ of the graphs are fixed by a transposition. These are the most common symmetries.

To bound the number of symmetric graphs, filter permutations by the number of moved points $k$. There aren't many permutations with many fixed points, at most ${n\choose k} k! \le n^k$. Permutations with few fixed points move many edges (even when both endpoints move, this can only reverse at most $n/2$ edges), hence many edges are contained in orbits of size at least $2$, hence there are at most ${n\choose 2} + n/2 - {k \choose 2}/2$ orbits.

$$\frac{\text{# symmetric}}{2^{n \choose 2}} \le \sum_{k \lt n/2} \frac{n^k}{2^{k(n-k)/2}} + \sum_{k\ge n/2} \frac{n!}{2^{{k\choose 2}/2 - n/2}}$$

After that, routine estimates show that when $n$ is large, the term from transpositions is small but dominates the others.

-
add comment

Almost all non-asymmetric graphs have exactly one non-trivial automorphism, namely a transposition swapping two vertices. So, an accurate estimate of their number is obtained by taking an arbitrary graph with one vertex less, choosing a vertex $v$, adding a new vertex $w$ with the same neighbours as $v$, then either joining or not joining $v$ to $w$. For labelled graphs, if $g_n=2^{\binom n2}$ is the number of them we have asymptotically $2ng_{n-1}$ non-asymmetric graphs. This is a small fraction. For unlabelled graphs, divide the total by $n!$ and the non-asymmetric ones by $n!/2$.

-
add comment