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$
$\endgroup$
3
-
$\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$– Klim EfremenkoCommented 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 HoltCommented Mar 31, 2011 at 18:44
-
$\begingroup$ Does it always possible to achieve $\frac{1}{100}{m\choose n}$ $\endgroup$– Klim EfremenkoCommented Mar 31, 2011 at 19:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$ Commented 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$ Commented 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$ Commented Mar 31, 2011 at 20:51
-
$\begingroup$ and said group is abelian, I'm sure it can be much improved. $\endgroup$ Commented Mar 31, 2011 at 21:23