# Group not leaving subset invariant

Let $Y,X$ be two sets of size n,m. Let $Y\subset X$. What is the maximal group(in size) $G< Sym(X)$ such that gY=Y imply that $g=1$? Here I mean that the only permutation which permutes elements of $Y$ between themselves is identity.

-
1) Since there was comment before which was deleted 2) Are you sure that this is HW problem? If yes, I will delete the post –  Klim Efremenko Mar 31 '11 at 18:29
Looks like a hard question to me! An upper bound on $|G|$ is $m \choose n$. This is achieved when $n=1$ (or $m-1$) but not usually otherwise. It is achieved for example for $m=7$, $n=2$ with $G$ the Frobenius group of order 21. –  Derek Holt Mar 31 '11 at 18:44
Does it always possible to achieve $\frac{1}{100}{m\choose n}$ –  Klim Efremenko Mar 31 '11 at 19:48

For the property $P$ discussed, the usual argument that $P(G_1) \wedge P(G_2) \Rightarrow P(\langle G_1, G_2\rangle)$, where $G_1$ and $G_2$ are groups and $\langle G_1, G_2\rangle$ is the group generated by both, doesn't work. The addition of the parenthetical "in size" indicates that @Klim is aware of this, but is there a different argument that says that there is only one maximal-cardinality group having $P$? The question seems to claim that there is, but I don't see it.
As pointed out before, $|G|\leq \binom{n}{m}$ which is approximatively $\frac{n^m}{m!}$ for large $n=|X|$ and fixed $m=|Y|$. On the other hand, if you have $n_1+\dots +n_m=n$ and $n_i\geq 1$ for all $i=1\dots m$, then you can find a group with $|G|=n_1\times\cdots\times n_m$ with desired property. For large $n$ that's close to $\frac{n^m}{m^m}$. So, at least asymptotically you have, for fixed $m$, calling $B(m,n)$ the cardinal of the biggest group satisfying your condition, $\frac{n^m}{m^m}\lesssim B(m,n)\lesssim\frac{n^m}{m!}$ –  Olivier Bégassat Mar 31 '11 at 20:49
I mean that for large $n,~n_1\cdot\dots\cdot n_m$ can be chosen close to $\frac{n^m}{m^m}$. –  Olivier Bégassat Mar 31 '11 at 20:51