Asymptotically free action of permutation groups on subsets and multisets

S. Yu. Sadov

Diskretnaya Matematika, Tome 26 (2014) no. 3, pp. 101-120

Résumé

Let $G$ be a permutation group acting on a finite set $\Omega$ of cardinality $n$. The number of orbits of the induced action of $G$ on the set $\Omega_m$ of all $m$-element subsets of $\Omega$ obeys the trivial estimates $|\Omega_m|/|G|\leq |\Omega_m/G|\leq |\Omega_m|$. In this paper the upper estimate is improved in terms of the minimal degree of the group $G$ or the minimal degree of its subset with small complement. In particular, using the universal estimates obtained by Bochert for the minimal degree of a group and by Babai–Pyber for the order of a group, in terms of $n$ only we demonstrate that if $G$ is a 2-transitive group other than the full symmetric or the alternating groups, $m$ and $n$ are large enough, and the ratio $m/n$ is bounded away from $0$ and $1$, then $|\Omega_m/G|\approx |\Omega_m|/|G|$. Similar results hold true for the induced action of $G$ on the set $\Omega_{(m)}$ of all $m$-element multisets with elements drawn from $\Omega$, provided that the ratio $m/(m+n)$ is uniformly bounded away from $0$ and $1$.

Détail

Keywords: permutation group, regular orbits, average size of the stabilizer, minimal degree of a group, asymptotics of the number of orbits, enumeration of affine configurations, enumeration of graphs, asymptotically free action.