MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.

(I'd leave this as a comment if I had the rep, but I don't. Admins, please feel free to convert it into one.)

share|cite|improve this answer
No I did not claim that there is only one maximal group. Just one can understand that maximal group in sense that there is no group including it which has property P – Klim Efremenko Mar 31 '11 at 19:18
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
and said group is abelian, I'm sure it can be much improved. – Olivier Bégassat Mar 31 '11 at 21:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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