When is $S_n \times S_m$ a subgroup of $S_p$? I asked the following question on math.stackexchange several months ago:

Let $n,m,p>1$ be such that $S_n \times S_m \hookrightarrow S_p$. Does it imply that $p \geq n+m$?

Derek Holt gave a positive answer. However, because the problem is easy to solve for small values of $p$, I am really curious to know if there exists an "elementary" solution.
 A: I think I can do this with an elementary argument, but I have to rush off somewhere soon, so I will answer quickly and hope I get it roughly right!
Assume $p < n+m$, so we can assume also that $n>p/2$. $S_n$ must have a faithful orbit in its action on $p$ points, and if that orbit has size $k$ then $n \le k \le p < 2n$.
Let $H$ be the point stabilizer of the action of $S_n$ on this orbit of length $k$. Then since $|S_n:H| < 2n$ and any proper subgroup of $A_n$ has index at least $n$ (I am assuming $n \ge 5$, since you can do small cases separately), we cannot have $H < A_n$, so $H$ must be a maximal subgroup of $S_n$.
But then the action of $S_n$ on this orbit is primitive, and primitive groups have trivial centralizer. (That's because the point stabilizer in a primitive group fixes a unique point, since otherwise its fixed points would be a block, and hence the centralizer fixes that point and hence all points.)
So the other factor, $S_m$ must fix all points in that orbit, but that's impossible, because $m > p-k$.
A: Here is a solution to Brendan McKay's more general question, which I'll do as a separate answer.
Let $n_1,n_2,\ldots,n_k$ be integers, with $1 < n_1 \le n_2 \le \cdots \le n_k$, let $n = n_1+n_2 + \cdots +n_k$, and suppose that $G = S_{n_1} \times S_{n_2} \times \cdots S_{n_k} \le S_p$ for some $p$. Then $n \le p$.
To make the inductive argument work, I found that I needed to prove this also for the alternating groups, but then we need degree greater than $2$, because $A_2$ is trivial. So, for $1 \le i \le k$, let $G_i = S_{n_i}$ or (if $n_i>2$) $A_{n_i}$, and assume that $G = G_1 \times \cdots \times G_k \le S_p$, Then $n\le p$, where $n = n_1+n_2 + \cdots +n_k$.
Suppose not, and choose $p$ minimal such that there is a counterexample. Clearly $k > 1$.
If $G$ is intransitive (as a subgroup of $S_p$), then $p = p_1 + p_2$ for some $p_1,p_2 >0$, and $G$ fixes sets of sizes $p_1$ and $p_2$. By induction, those $G_{i}$ that act faithfully on first of these sets have degrees summing to at most $p_1$ and those acting faithfully on the second set have degrees summing to at most $p_2$, and since each $G_{i}$ must act faithfully on at least one of the two sets, we get $n \le p$, contrary to assumption.
So $G$ is transitive. Suppose next that it is imprimitive, with blocks $p_2$ blocks of size $p_1$, where $p_1,p_2>1$ and $p_1p_2=p$. Some of the $G_{i}$ act faithfully on the set of $p_2$ blocks and, by induction, there degrees sum to at most $p_2$. The remaining $G_i$ either lie in the kernel of the action on the block system, or else $n_i>2$ and $A_{n_i}$ lies in the kernel of this action. Since the actions of the kernel on each of the blocks are equivalent, they must all act faithfully on each individual block of size $p_1$. So, by induction, the sum of their degrees is at most $p_1$ and hence $n \le p_1 + p_2$ which is not possible, since $n > p = p_1p_2$.
So $G$ must be primitive of degree $p$. Since normal subgroups of primitive groups are transitive, $S_{n_1}$ is transitive, and hence $p \le n_1!$. Now, the centralizer of a transitive group of degree $p$ has order at most $p$ (its order is equal to the number of fixed points of the point stabilizer of the transitive group being centralized), so we get $n_2!n_3! \cdots n_k! \le p$, which is impossible except when $k=2$ and $p=n_1!=n_2!$, but then $n_1+n_2 \le p$ (except when $n_1=n_2=2$), contrary to assumption.
A: There is a more general result to be had (which I presume is known to permutation group specialists). For a finite group $G,$ let $m(G)$ denote the smallest degree of a faithful permutation representation  of $G.$ Let $X_{1},X_{2},\ldots X_{t}$ be finite simple groups with possibly some of the $X_{i}$ being Abelian: then $m( X_{1} \times X_{2} \times \ldots \times X_{t}) = \sum_{i=1}^{t} m(X_{i}).$ Clearly the minimal degree of the product is at most the sum of the minimal degree of the individual components. We prove the reverse inequality by induction on $t,$ the result being clear when $t = 1.$  The proof is not so different from Derek's, but differs in places, so I give it.
Set $X$ to be the direct product of the $X_{i},$ and suppose that $X$ acts faithfully on $\Omega$ with $|\Omega| = m(X).$ Then it follows that we may suppose that $X$ acts transitively on $\Omega.$ For if $\Omega = \Omega_{1} \cup \Omega_{2}$ with each $\Omega_{i}$ being $X$-invariant, and the union being disjoint, let $N$ be the pointwise stabilizer of $\Omega_{1},$ which is proper and non-trivial. Then $N$ acts faithfully on $\Omega_{2}$ and $X/N$ acts faithfully on $\Omega_{1}.$ Since $N$ is isomorphic to a direct product of some of the $X_{i}$ and $X/N$ is isomorphic to the direct product of the remaining ones, our claim is established. If possible, let $\Gamma$ be a proper orbit (on $\Omega$) of a proper non-trivial normal subgroup $N$ of $X,$ and choose $N$ as large as possible. Let $K$ be the kernel of the action of $N$ on $\Gamma.$ Since $X$ is a direct of simple groups, all subnormal subgroups of $X$ are normal, so $K \lhd X.$ But $X$ then permutes the fixed points of $K$ on $\Omega,$ while $X$ is also transitive, so $K =1$ and $N$ acts faithfully on $\Gamma.$ 
Now all orbits of $N$ on $\Omega$ have size $|\Gamma|$, and $X/N$ acts faithfully as a permutation group on the set of such orbits by maximality of $N.$ 
Thus $|\Omega| \geq m(N) m(X/N) \geq \sum_{i} m(X_{i})$ . Hence we may suppose that each non-trivial normal subgroup of $X$ acts transitively on $\Omega.$ Then for any $i,$ we see that $\prod_{j \neq i} X_{j}$ acts regularly on $\Omega,$ since $X_{i}$ permutes the fixed points of any element of that product, while the product also acts transitively. But likewise, since $t >1$, $X_{i}$ must also act regularly. If we label to that $|X_{i}| \leq |X_{j}|$ whenever $i \leq j,$ then we see that we must have $t =2$ and $|X_{1}| = |X_{2}| = |\Omega|.$
If $X_{1}$ is Abelian, then we have a contradiction since an elementary Abelian group of order $p^{2}$ can't act faithfully on $p$ points when $p$ is prime. If $X_{1}$ is non-Abelian, we note that $m(X_{1}) \leq \frac{|X_{1}|}{3}$, since $X_{1}$ has a corefree subgroup of order greater than $2.$ Thus $m(X_{1} \times X_{2}) \leq 2 \frac{|X_{1}|}{3},$ a contradiction.
  The special result about symmetric groups can be recovered from this one, since if $Y$ is a direct product of symmetric groups, then $F^{*}(Y)$ is a direct product of simple groups,
and we get an alternating group factor of degree $k$ for each symmetric group of degree $k \geq 5,$ while we get a cyclic factor of degree $k$ for each symmetric group $S_{k}$ with $k \leq 3,$ while we get two cyclic factors of degree $2$ for each symmetric group factor $S_{4}.$ Since $S_{4}$ has minimal degree $4,$ this works as required.
(Later edit: A couple of further remarks: if $S$ is a non-Abelian finite simple group, there is indeed a faithful action of $S \times S$ on a set of $|S|$ points in which both factors act regularly. The action is on the cosets of the diagonal subgroup $\Delta(S)$ of $S \times S.$ It is also the case, with a little more thought, that any such simple group $S$ has $m(S) \leq \frac{|S|}{12},$ though the much cruder bound above was sufficient for that argument. For if $S$ has even order, then if $S$ has a Sylow $2$-subgroup of order less than $16$,$S$ has a subgroup of order $12$ or $56$ by transfer arguments, while if $S$ has odd order, $|S|$ is divisible by by $p^{3},$ again by transfer, where $p$ is the smallest prime divisor of $|S|$, as was known to Burnside (the latter is just a device to avoid invoking the full strength of the Feit-Thompson odd order theorem)).
