Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

EDIT 1-3-2014 Thanks to both answers. I received two estimates of the number of symmetric graphs. I'm still hoping for a better tight asymptotic upper-bound such as $O(f(n))$ where $n= |V(G)|$ or even better a tight asymptotic lower-bound on the number of asymmetric graphs $\omega(g(n))$.

share|improve this question

3 Answers 3

up vote 8 down vote accepted

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

share|improve this answer
1  
Is there a simple justification for your first sentence? –  Andrew D. King Jan 8 at 22:08
2  
@Andrew: It isn't trivial, but isn't hard to prove. Take a random graph ($p=1/2$) and consider the probability $P(\pi)$ that a particular permutation is an automorphism. For a transposition it is $2^{-n+2}$, for a 3-cycle it is $2^{-2n+4}$. For a permutation moving $\Theta(n)$ points, the probability is $2^{-\Theta(n^2)}$. In the sum of $P(\pi)$ over all non-identity permutations $\pi$, the terms from transpositions dominate. This is folklore but I don't recall where it is in print. –  Brendan McKay Jan 8 at 22:58

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.

share|improve this answer
    
Can you simplify the formula for the number of symmetric graphs and give tight asymptotic upper-bound? (such as $o(f(|V|))$) –  Mohammad Al-Turkistany Jan 3 at 18:44

There are some references and some more information in the entry on the number of asymmetric graphs on n nodes in the OEIS (Online Encyclopedia of Integer Sequences):

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 220, Section P3.4.

P. Steinbach, Field Guide to Simple Graphs. Design Lab, Albuquerque NM, 1990.

The number of such graphs goes in the surprising sequence 1, 0, 0, 0, 0, 8, 152, 3696, 135004, 7971848, 805364776, ...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.