I do not understand several assertions in the proof below:

Let G be a permutation group on a set $\Omega$, and let $k$ be an integer s.t. $k<|\Omega|$. Then the following are equivalent:

(i) for all $\Delta$ with $|\Delta|=k$ the group $G_{(\Delta)}^{\Delta}=S_\Delta$, (where $G_{(\Delta)}^{\Delta}$ is the permutation group induced by the set-wise stabiliser of $\Delta$ on $\Delta$.)

(ii) the number of orbits of G as a permutation group on the ordered subsets of k points of $\Omega$ is equal to the number of orbits of G as a permutation group on the unordered subsets of k points of $\Omega$.

Proof. The points of $\Delta$ form k! ordered sets of k points. Two of these ordered sets lie in the same orbit of G precisely when there exists an element of $G_{(\Delta)}^{\Delta}$mapping one onto the other. Consequently the number of different orbits of G in which the ordered sets of k points of $S_\Delta$ lie, is equal to the index of $G_{(\Delta)}^{\Delta}$ in $S_\Delta$. The result now follows.

The first two sentences are obvious, but why does the number of orbits equal the index in $S_\Delta$ ? Do the cosets also give orbits? And then how does the equivalence follow? I have tried to use the orbit counting lemma, and simply to think about the structure, but something is not coming together.


Fix $\Delta$ a set of $k$ points, and let $X$ be the set of $k!$ orderings of the elements of $\Delta$. It is easy to check that the action of $G_{(\Delta)}^\Delta$ on $X$ is semiregular. (That is, all the point-stabilisers are trivial. Note that the points here are elements of $X$, not the original elements of $\Omega$ or $\Delta$.) It follows that all the orbits of $G_{(\Delta)}^\Delta$ have size $|G_{(\Delta)}^\Delta|$ and thus the number of orbits is $k!/|G_{(\Delta)}^\Delta|=|S_\Delta:G_{(\Delta)}^\Delta|$ .

| cite | improve this answer | |
  • $\begingroup$ I still cannot understand how the discussion of the orbit of the stabiliser on one particular k-point subset transfers to the discussion about the orbits of the whole group G. Could you help me here? $\endgroup$ – Sveti Ivan Rilski Apr 8 at 1:09
  • $\begingroup$ I already gave you a proof of the whole argument, from start to finish. If you have a question about a specific part of that, then ask it. $\endgroup$ – verret Apr 9 at 1:17
  • $\begingroup$ You haven't. You have shown that the number of orbits of $G_{(\Delta)}^\Delta$ is its index in the symmetric group on $\Delta$. The proof in my question states that this index is equal to the number of the orbits of G, not just the stabiliser subgroup, on the set of all ordered k-subsets of $\Omega$, not just those of $\Delta$. My original question also asked for an explanation of how the full result in the theorem "follows". So there must be an implication from the proof you gave to the proof about G-orbits (i.e. not just $G_{(\Delta)}^\Delta$-orbit). That implication is what I do not see. $\endgroup$ – Sveti Ivan Rilski Apr 9 at 10:30
  • $\begingroup$ Oh wait I see my mistake. It says number of orbits of $S_\Delta$. So we are talking about orbits on orderings of $\Delta$, not on general k-subsets of $\Omega$. The result is trivial I was misreading it. Thank you very much for your help. $\endgroup$ – Sveti Ivan Rilski Apr 9 at 10:47

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.