5
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ As a cruder version of Brendan McKay's answer, since the probability that a random graph on $n$ vertices has trivial automorphism group approaches $1$ as $n \to \infty$, you might expect the distrbution to be high at the edges but longand low in the middle. $\endgroup$
    – Derek Holt
    Nov 6, 2013 at 8:04

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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:
 Auto6
And here is the average of $1000$ random trials, again with $n=6$:
         Autos1000_6

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the pictures, as usual! The well for $1000$ trials looks rather steep (as expected) even for small $n$! But I am a bit concerned about the list of orders obtained for a single trial -- shouldn't this list be symmetric about the middle? $\endgroup$
    – Vidit Nanda
    Nov 8, 2013 at 16:09
  • $\begingroup$ @ViditNanda: Since the edges added were chosen randomly, the structure of the graph with $k$ edges is in general not the same as the structure of the complement of the graph for $n-k$ edges. But maybe I am misinterpreting your question... $\endgroup$
    – Joseph O'Rourke
    Nov 8, 2013 at 16:36
  • $\begingroup$ I have to apologize for an anomaly in that the IGraph function inside R that I invoke, "graph.count.isomorphisms.vf2", is somehow not (always) counting correctly when the graph contains isolated vertices. I think this is why we see a slight asymmetry even after 1000 trials. I also have to say, it is unlikely I will clear up this discrepancy, as it involves understanding several pieces of complex software that are not thoroughly familiar to me. Meanwhile, I am confident of the counts once the graph becomes connected. $\endgroup$
    – Joseph O'Rourke
    Nov 9, 2013 at 0:17
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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