Minimal embedding of a group into the group $S_n$

I am aware this has come up recently (Embedding of finite groups for example) but after searching I haven't found the particular answer I'm looking for. Suppose I know the character table and can figure out the minimal (degree) faithful representation of group G (such as a subgroup of a Frobenius group): can I then find/bound accurately the smallest m such that our group G embeds into S$_m$? It is merely my idle curiosity as to whether it is possible, but I would like to be able to give as accurate a bound on n as possible, or indeed find it. www.austms.org.au/Gazette/2008/Nov08/TechPaperSaunders.pdf seems to suggest in the first few lines that it simply is the degree of the min. faithful representation, but is it really that simple? Could anyone suggest anything? Thank you very much - Tom H

EDIT: Just to let everyone know I spoke further with a colleague and after reading a few books I circumvented the issue I was having, so problem solved: I now consider this question closed, in case it needs marking as such.

-
Certainly it is at least one more than the degree of the minimal faithful representation (since any faithful permutation representation on a set of size $n$ gives rise to a faithful representation of dimension $n-1$ given by taking the free vector space then subtracting a copy of the trivial rep). – Qiaochu Yuan May 4 '11 at 2:55
Yes, I didn't think of that, of course. Is there any way in particular to tell when you can obtain this bound and when you can't? I suppose there's no more you can do than check whether your minimal faithful representation or an equally small one is a permutation representation, is there? – T. Hughes May 4 '11 at 3:17

The paper you mention does not claim that the minimal degree of a faithful representation is your $n$, it says "of a faithful permutation representation." It is easy to see that the other statement would be too strong: $S_3$ has an irreducible faithful 2-dimensional representation, but you certainly cannot embed $S_3$ into $S_2$. Similarly, you cannot embed a cyclic group into $S_1$.

Your question has been asked on Mathoverflow, and as you can see from that discussion, it is a fairly delicate issue. You will not find a simple relationship between the minimal degree of a faithful representation and the smallest $n$, as the example of cyclic groups shows (the former is always 1, the latter can be arbitrarily large).

-
Ah sorry, I obviously missed 'permutation'. I did see the mathoverflow discussion, though I thought perhaps with the given advantages of a little additional knowledge it might be feasible in certain small cases. I am surprised GAP doesn't have the capabilities, though evidently it is one of those problems which is far simpler to state than it is to solve. – T. Hughes May 4 '11 at 3:16

The character table does not determine the minimum size of a faithful permutation representation. For instance the two non-abelian groups of order 8 have the same character table, but the minimum sizes are 4 and 8. (Their minimal faithful complex representations have degree 2.)

For which group are you trying to find the minimal permutation representation?

-
Sorry for slow response: I've been abroad in London. The groups I am interested in were subgroups of e.g. Frobenius/permutation groups (of course there is an obvious embedding, but I was curious how to find out whether it embeds in smaller groups). I looked into a few specific cases but couldn't see anything obvious. I'm not averse to using other methods than representations - they were a suggestion from a colleague - I just want a way better than evaluating the entire group in depth. However, as has been stated, it's far from trivial, so don't worry if there is no solution! – T. Hughes May 9 '11 at 23:20