Garnir Elements

Let and be two disjoint sets of positive integers. We’re mostly interested in the symmetric group , which shuffles around all the integers in both sets. But a particularly interesting subgroup is , which shuffles around the integers in and , but doesn’t mix the two together. Clearly, is a subgroup of .

Now, let be a transversal collection of permutations for this subgroup. That is, we can decompose the group into cosets

Then a “Garnir element” is

Now, the problem here is that we’ve written as if it only depends on the sets and , when it clearly depends on the choice of the transversal . But we’ll leave this alone for the moment.

How can we come up with an explicit transversal in the first place? Well, consider the set of pairs of sets so that , , and . That is, each is another way of breaking the same collection of integers up into two parts of the same sizes as and .

Any permutation acts on the collection of such pairs of sets in the obvious way, sending to , which is another such pair. In fact, it’s transitive, since we can always find some with and . If for each we make just such a choice of , then this collection of permutations gives us a transversal!

We can check this by first making sure we have the right number of elements. A pair is determined by taking all integers and picking to go into . That is, we have

pairs. But this is also the number of cosets of in !

Do we accidentally get two representatives and for the same coset? If we did, then we’d have to have . But then , and thus . But we only picked one permutation sending to a given pair, so .

As an example, let and . Then we have six pairs of sets to consider

where in each case I’ve picked a that sends to . This will give us the following Garnir element:

But, again, this is far from the only possible choice for this and .