2
$\begingroup$

Is there a known upper bound on the number of vertex transitive graphs on $n$ vertices?

$\endgroup$
  • $\begingroup$ $2^{n-1}$ times the number of minimal transitive groups would be a fair bound, but I don't know a bound on the number of minimal transitive groups. For this reason, adding a group category to your question might be a good idea. $\endgroup$ – Brendan McKay Jan 22 '14 at 8:30
  • $\begingroup$ What is the reason for the $2^{n-1}$ factor? $\endgroup$ – Amit Levi Jan 27 '14 at 16:56
  • 1
    $\begingroup$ There are $2^{n-1}$ ways to choose the neighbours of the first vertex. Then the group action gives all the other edges. $\endgroup$ – Brendan McKay Jan 27 '14 at 21:23
2
$\begingroup$

I think only very rough bounds are known. In http://arxiv.org/abs/1210.5736, it is conjectured that the answer for fixed valency d is roughly of the form $n^{d\log n}$. This is proved for Cayley graphs and for $d=3$.

As Brendan mentions, obtaining upper bounds on the number of minimal transitive groups of a given degree would yield upper bounds. The best results in this direction are due to Pyber, I believe, but are not tight. I think this may be in :

Pyber, László Asymptotic results for permutation groups. (English summary) Groups and computation (New Brunswick, NJ, 1991), 197–219, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 11, Amer. Math. Soc., Providence, RI, 1993.

$\endgroup$

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.