Please forgive the rather imprecise title, this was the best that I could come up with that could fit in a line.
Let $n$ be a [large] integer. Pick according to the uniform distribution a graph $G$ out of the set $\cal{G}_n$ of $2^{n \choose 2}$ graphs on $\{1,\ldots,n\}$. It is known that the expected size $A_1$ of Aut$(G)$ is close to $1$.
Main Question: Suppose however, we were to collapse $\cal{G}_n$ as follows:
$$[\cal{G}_n] \doteq \{\ [G]; \ G \in \cal{G}_n \}$$, where
$[G]=[G']$; $G,G' \in \cal{G}_n$; iff $G$ and $G'$ are isomorphic. Now, let us pick a $[G]$ from $[\cal{G}_n]$ according to the uniform distribution on $[\cal{G}_n]$. What is the expected size $A_2$ of Aut$(G)$, where $G$ is a graph in $\cal{G}_n$ in $[G]$. Is it still close to $1$?
Now, let $A_1$ be the expected size of Aut$(G)$, where $G$ is picked according to
the uniform distribution on $\cal{G}_n$, and let $A_2$ be the expected size of Aut$(G)$, where $[G]$ is picked according to
the uniform distribution on $[\cal{G}_n]$ [and of course, $G \in [G]$]. Then $A_2$ is what the Main Question above is interested in. We now make an observation in the meanwhle however: The inequality $A_2 > A_1$ holds. Indeed, each $[G] \in [\cal{G}_n]$ is a set of $\frac{n!}{\text{Aut}(G)}$ graphs $G' \in \cal{G}_n$ that are isomorphic but distinct. So $A_2$ is the expected size of Aut$(G')$, where $G'$ is picked from $\cal{G}_n$ as follows:
- Give each $G \in$ Aut$(G)$ a weighting $\omega(G) = \frac{{\text{Aut}}(G)}{n!}$.
- Then, letting $\Omega \dot = \sum_{G \in \cal{G}_n} \omega(G)$, pick each $G' \in \cal{G}$ with probability $\frac{\omega(G')}{\Omega}$.
- Then $A_2$ is the expected size of Aut$(G')$. Note that in this probability measure, graphs with larger automorphism groups are given larger relative weight, and graphs with small automorphism groups smaller relative weight, than they would be in the uniform distribution on $\cal{G}_n$.
**Given a graph $G$ on $\{1,\ldots, n\}$, the automorphism group Aut$(G)$, which is a subset of the permutation group $S_n$ on $\{1,\ldots, n\}$, is defined as follows: a permutation $\pi \in S_n$ is in Aut$(G)$ iff $\pi(i)\pi(j)$ form an edge in $G$ for each edge $ij \in G$ [where $i,j \in \{1,2,\ldots, n\}$].
Best Answer
The density tends to 1 also for unlabelled graphs, see this answer
A good reference is László Babai. 1996. Automorphism groups, isomorphism, reconstruction. Handbook of combinatorics (vol. 2). MIT Press, Cambridge, MA, USA, 1447–1540.
(see 1.6. Asymmetry, rigidity. Almost all graphs. Unlabelled counting.)