Finite transitive groups having many suborbits of cardinality at most 2 and an application to the enumeration of Cayley graphs

Let G be a finite transitive group on a set , let , and let be the stabilizer of the point in G. In this paper, we are interested in the proportion

that is, the proportion of elements of lying in a suborbit of cardinality at most 2. We show that, if this proportion is greater than , then each element of lies in a suborbit of cardinality at most 2, and hence G is classified by a result of Bergman and Lenstra. We also classify the permutation groups attaining the bound .

We use these results to answer a question concerning the enumeration of Cayley graphs. Given a transitive group G containing a regular subgroup R, we determine an upper bound on the number of Cayley graphs on R containing G in their automorphism groups.