Min Deg

Definition 1.1   The minimum degree $\mathop{\rm min\,deg}(G)$ of a permutation group $G$ is the minimum of the degrees of the nonidentity elements of $G$.

For example, $\mathop{\rm min\,deg}(S_n)=2$, $\mathop{\rm min\,deg}(A_n)=3$, $\mathop{\rm min\,deg}(D_n)$ is $n-2$ if $n$ is even and $n-1$ if $n$ is odd. $\mathop{\rm AGL}(d,q)$ acts on ${\mathbb{F}_q}^d$, which has $n=q^d$ elements, has $\mathop{\rm min\,deg}=q^d-q^{d-1}=n(1-\frac 1q)\ge \frac n2$.

Theorem 1.2 (Jordan)   If $G<S_n$ is primitive, then $\mathop{\rm min\,deg}(G)\to\infty$ as a function of $n$.

For example, $S_k<S_n$ with $n=\binom{k}{2}\sim \frac{k^2}{2}$ acting on two-element subsets, is primitive. The degree of a transposition in this induced action is $2(k-2)$ and $\mathop{\rm min\,deg}=2(k-2)\sim\sqrt{8n}$. The classification of finite simple groups can be used to show that this is minimal among primitive permutation groups of degree $n$, but elementary arguments already give the right order of magnitude; they show that the minimum degree of a primitive permutation group must be at least $c\sqrt{n}$.