Tracking automorphism groups of graph processes Start with an edgeless graph on $n$ labeled vertices, and note that the automorphism group is $\Sigma_n$, the symmetric group on $n$ elements. Now imagine that we randomly start throwing in all of the $\binom{n}{2}$ edges one at a time. 

How does the automorphism group change?

The first edge that goes in reduces the automorphism group drastically to $\Sigma_{n-2} \times \mathbb{Z}_2$: we can still switch around the disconnected vertices at will, but the two linked vertices may only be switched with one another. Note also that by the time we have reached the complete graph $K_n$, the automorphism group has grown back up to $\Sigma_n$.

What is the expected order of the automorphism group as a function of $m$, where $m \in \{0,\ldots,\binom{n}{2}\}$ is the edge count?

Aside from a comment by Matt Kahle that this order should be symmetric about the middle, I'm quite unsure about how to proceed.
 A: There is no simple exact answer to this question.  The harmonic mean of the automorphism group sizes is related to the ratio between the labelled and unlabelled graph counts (since the number of graphs in the isomorphism class of $G$ is $n!/|\mathrm{Aut}(G)|$), so the theory of unlabelled enumeration (Polya, etc) provides an answer of sorts for the harmonic mean.  The domain where most graphs start to have trivial automorphism groups has been explored: you could start with Chapter 9 of Bollobás, Random Graphs, 2nd edn.
A: I computed the number of automorphisms of the graph as edges are added randomly
(with help from the Mathematica StackExchange community).
Below is one instance for $n=6$, with $0$ on the horizontal axis the graph of no
edges, and $15$ the graph $K_6$.
The count of the number of automorphisms is
$$720, 48, 12, 12, 24, 6, 2, 1, 2, 8, 4, 4, 4, 12, 48, 720 \;$$
The one graph that occurred in this run
with just the trivial automorphism is shown at right:
 
And here is the average of $1000$ random trials, again with $n=6$:
         
A: This is almost a model situation for having the so-called cut-off phenomenon. The point is that originally edges are unlikely to have common vertices. Then there will be a quite short phase transition period, after which the graphs will be mostly rigid. At the other end of the parameter interval the situation will repeat in the opposite direction (in fact, the whole picture is symmetric with respect to the transformation $t\mapsto n-t$, because the groups of automorphisms of the graph and of its edge complement coincide).  
