# Size of automorphism group of random regular graph

If I pick a random regular graph on $n$-vertices and degree $d$ from uniform distribution what is the probability that its automorphism group is of size at least $m$?

--

I want to know what is the largest $\alpha>0$ such that there is a $d$ regular graph $G$ on $n$ vertices with automorphism group larger than ${(n-\alpha)!}$. Are such graphs efficiently constructible and how many such non-isomorphic graphs are possible?

• Have you worked out the answer to your question in the special case where $d=2$? – David A. Jackson Jul 19 '16 at 1:17
• Are the vertices labeled? – Sam Hopkins Jul 19 '16 at 2:28

For $3\le d\le n-4$ the group size is almost always 1. The next most likely group size is 2, which most probably occurs due to a transposition (I don't know where this is proved formally). There is no hope of a general formula, though it is plausible to obtain reasonable upper bounds. For $d=0,1$ the question is trivial. For $d=2$, which David mentions, the question is interesting and difficult, somewhat similar to the structure of random permutations.
Concerning the largest possible group: if $d$ is small and you don't care about connectedness, take a lot of disjoint complete graphs $K_{d+1}$. If you care about connectedness it gets a lot harder; see this and this .
• here it is people.math.ethz.ch/~sudakovb/automorphism.pdf but I cannot find the information I am looking in paper. I want to know what is the largest $\alpha>0$ or largest $\beta\in(0,1)$ such that there is a $d$ regular graph $G$ on $n$ vertices with automorphism group larger than ${n!}^{\frac{\alpha}{1+\alpha}}$ or $n!^\beta$. Are such graphs efficiently constructible? – Brout Jul 19 '16 at 4:50