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

Spiga, Pablo

Canadian journal of mathematics, Tome 76 (2024) no. 1, pp. 345-366

Résumé

Let G be a finite transitive group on a set $\Omega $, let $\alpha \in \Omega $, and let $G_{\alpha }$ be the stabilizer of the point $\alpha $ in G. In this paper, we are interested in the proportion $$ \begin{align*} \frac{|\{\omega\in \Omega\mid \omega \textrm{ lies in a }G_{\alpha}\textrm{-orbit of cardinality at most 2}\}|}{|\Omega|}, \end{align*} $$that is, the proportion of elements of $\Omega $ lying in a suborbit of cardinality at most 2. We show that, if this proportion is greater than $5/6$, then each element of $\Omega $ 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 $5/6$.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.

Détail

DOI : 10.4153/S0008414X23000093

Mots-clés : Suborbits, Cayley graph, automorphism group, asymptotic enumeration, graphical regular representation