Welcome to MathOverflow

Question

5

1

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.

edited Mar 31 2011 at 17:52

asked Mar 31 2011 at 17:46

Klim Efremenko
1,399●4●14

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 2011 at 18:29

4

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 2011 at 18:44

Does it always possible to achieve $\frac{1}{100}{m\choose n}$ – Klim Efremenko Mar 31 2011 at 19:48

Erik P. · Answer 1 · 2011-03-31 18:59:47Z UTC

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

answered Mar 31 2011 at 18:59

Erik P.
36●2

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 2011 at 19:18

3

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 2011 at 20:49

1

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 2011 at 20:51

and said group is abelian, I'm sure it can be much improved. – Olivier Bégassat Mar 31 2011 at 21:23

Group not leaving subset invariant

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.