Is there a known upper bound on the number of vertex transitive graphs on $n$ vertices?
3
-
$\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 McKayJan 22, 2014 at 8:30
-
$\begingroup$ What is the reason for the $2^{n-1}$ factor? $\endgroup$– Amit LeviJan 27, 2014 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 McKayJan 27, 2014 at 21:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
