Proportion of asymmetric graphs

Question

Wikipedia states, that the proportion

$$p(n):=\frac{number\ of \ asymmetric \ graphs \ with\ n\ nodes}{number\ of\ graphs\ with \ n\ nodes}$$

satisfies

$$\lim_{n->\infty }p(n)=1$$

I wonder how fast this convergence is. For $n=9$, there are $135004$ asymmetric graphs and $274668$ graphs altogether, so $p(9) = 0.4915$.

So only about the half of the graphs with $9$ nodes is asymmetric. Is it known for which $n$, $p(n)$ exceeds $0.99$, for example ?

Answer 1

The following is a partial answer, perhaps useful in pointing out a subtlety in how graphs are to be counted for the purpose of giving an asymmetric proportion. Edit: It turns out that much the same point is made (more forcefully) by Brendan McKay's accepted answer to this MathOverflow Question about density of asymmetric graphs.

According to Babai's Chapter 27 for Handbook of Combinatorics the proportion of asymmetric graphs tends to unity like $1 - \binom{n}{2}2^{-n-2}(1+o(1))$ as vertices $n \to \infty$, attributing the result to Polya(1937) and to Erdős and Rényi(1963).

If we set $o(1) = 1$ in the above, so that it becomes in seemingly conservative fashion an estimate $1 - \binom{n}{2}2^{-n-1}$, then $\binom{n}{2}2^{-n-1} \le 0.01$ for all $n \ge 12$. But Peter's figures for $n=11$ suggest that such an approximation cannot be relied on fully.

Part of this apparent discrepancy may arise from qualifying the domain as labeled or unlabeled graphs. Babai writes:

The results establishing “almost always asymmetry” mentioned above are valid for labeled as well as for unlabeled graphs; the latter is a substantially stronger statement with important consequences to counting unlabeled objects.

The reason for this "annoying distinction" (in Babai's words) is that for unlabeled graphs the counting is done by isomorphism classes, in which case the isomorphism class of an asymmetric graph on $n$ vertices gives rise to $n!$ distinct labeled graphs, while a graph with nontrivial symmetry will have an accordingly smaller number of distinct labeled versions for a given (unlabeled) isomorphism class. In short counting in the labeled domain inflates the number of asymmetric graphs more than the number of graphs with nontrivial symmetries, so that the proportion of asymmetric labeled graphs tends to $1$ more rapidly than the corresponding proportion of asymmetric unlabeled isomorphism classes.