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.

  • $\begingroup$ 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 $\endgroup$ Mar 31, 2011 at 18:29
  • 4
    $\begingroup$ 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. $\endgroup$
    – Derek Holt
    Mar 31, 2011 at 18:44
  • $\begingroup$ Does it always possible to achieve $\frac{1}{100}{m\choose n}$ $\endgroup$ Mar 31, 2011 at 19:48

1 Answer 1


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.)

  • $\begingroup$ 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 $\endgroup$ Mar 31, 2011 at 19:18
  • 3
    $\begingroup$ 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!}$ $\endgroup$ Mar 31, 2011 at 20:49
  • 1
    $\begingroup$ I mean that for large $n,~n_1\cdot\dots\cdot n_m$ can be chosen close to $\frac{n^m}{m^m}$. $\endgroup$ Mar 31, 2011 at 20:51
  • $\begingroup$ and said group is abelian, I'm sure it can be much improved. $\endgroup$ Mar 31, 2011 at 21:23

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.