I'm interested in determining the existence of a permutation group $G\subseteq S_n$ of the following form.

  1. $G$ is large. Meaning that $G$ have at least $n!/2^{o(n)}$ elements. Equivalently, their index is at most $2^{o(n)}$.
  2. For some fixed $d$, no subgroup $H$ of $G$ is isomorphic to $S_d$ or to $A_d$.

Question 1: How small can $d$ be? For instance, is there a subgroup $G$ of $S_n$ of index $2^{o(n)}$ such that no subgroup of $G$ is isomorphic to $S_{\sqrt{n}}$ or $A_{\sqrt{n}}$?

The second question is whether there are Ramsey-theoretic results relating symmetric groups of size $d$ with large subgroups of $S_n$.

Question 2: Are there functions $f,g:\mathbb{N}\rightarrow \mathbb{N}$ such that for every $d<f(n)$, any subgroup $G$ of $S_n$ of order at least $g(d)$ contains a subgroup $H$ isomorphic to $S_d$ (or to $A_n$)?

  • $\begingroup$ "For small enough $d$..." usually means "for each small enough $d$" which here is completely senseless. Do you mean "for some fixed $d$" (given that $n$ varies)? or for some function $d(n)$ with some nontrivial condition (it would be useful to write $G_n$ instead of $G$). $\endgroup$ – YCor Apr 19 '18 at 9:47

Essentially the only subgroups of $S_n$ with subexponential index have an orbit of size greater than $n/2$ on which the induced action contains the alternating group. So it looks as though the answer to your Question 1 is yes, even with $n/2$ in place of $\sqrt{n}$.

This follows from Theorem 5.2B of "Permutation Groups" by Dixon and Mortimer, applied with $r = \lfloor n/2 \rfloor$.

Let $n := |\Omega| \ge 5$, let $r$ be an integer with $1 \le r \le n/2$, and let $G \le S_\Omega$ have index less than $\binom{n}{r}$. Then one of the following holds:

(i) for some $\Delta \subset \Omega$ with $|\Delta|<r$, we have $A_{(\Delta)} \le G \le S_{\{\Delta\}}$;

(ii) $n=2m$ is even and $G$ is imprimitive with two blocks of size $m$ and $|S_\Omega:G| = \frac{1}{2}\binom{n}{m}$;

(iii) one of six specific exceptional cases holds (which I won't list here).

Here $A_{(\Delta)}$ denotes the pointwise stabilizer of $\Delta$ in $A_\Omega$, and $S_{\{\Delta\}}$ is the setwise stabilizer of $\Delta$ in $S_\Omega$.

Note that the the index in Case (ii) is greater than $2^m$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.