Suppose $\Gamma(V, E) \sim G(n, p)$ is an Erdos-Reyi random graph with $n$ vertices and edge probability $p$. What is the expected size of the automorphism group of $\Gamma$?
What have I tried:
Suppose, $I_{Aut(\Gamma)}$ is the indicator function of $Aut(\Gamma)$ in $Sym(V)$. Then $|Aut(\Gamma)| = \sum_{\sigma \in Sym(V)} I_{Aut(\Gamma)}(\sigma)$. Thus $$E(|Aut(\Gamma)|) = E(\sum_{\sigma \in Sym(V)} I_{Aut(\Gamma)}(\sigma)) = \sum_{\sigma \in Sym(V)} E(I_{Aut(\Gamma)}(\sigma)) = \sum_{\sigma \in Sym(V)} P(\sigma \in Aut(\Gamma))$$ However, I do not know how to proceed further.
Here is also the analysis of the situation for small $n$:
If $n = 1$, then $E(|Aut(\Gamma)|) = 1$ because $|Aut(\Gamma)| = 1$ almost surely.
If $n = 2$, then $E(|Aut(\Gamma)|) = 2$ because $|Aut(\Gamma)| = 2$ almost surely.
If $n = 3$, then $|Aut(\Gamma)| = 6$ with probability $p^3 + (1 – p)^3$ and $|Aut(\Gamma)| = 2$ with probability with probability $1 – (p^3 + (1 – p)^3)$. Thus $E(|Aut(\Gamma)|) = 2 + 4(p^3 + (1 – p)^3)$.
Also note, that because the automorphism group of a graph is always isomorphic to the automorphism group of its complement graph, that value is invariant under the map $p \mapsto (1-p)$
Best Answer
It is a theorem that the proportion of isomorphism classes of graphs on $n$ vertices with a non-identity automorphism goes to zero as $n$ increases. It’s quite standard; one proof can be found in "Algebraic Graph Theory" by me and Royle.