2
$\begingroup$

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?

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

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 .

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Brout Jul 19 '16 at 4:50

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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