Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have recently been looking at Hall's marriage theorem. One application of it is that given a finite group $G$ and a subgroup $H\leq G$, there is a left transversal of $H$ that is also a right transversal. I can see the theoretical importance of this, but am struggling to find any situations when one would actually use this. If anybody can enlighten me, that would be greatly appreciated.

share|improve this question
Do you mean a left traversal of $H$? mathworld.wolfram.com/LeftTransversal.html –  Thomas Andrews Apr 20 '12 at 20:32
@ThomasAndrews Yes, I do mean a left transversal of $H$. Thanks for pointing out the (now corrected) error. –  David Ward Apr 20 '12 at 21:29

1 Answer 1

After thinking of this a little, it happens to be easy to give a proof using Hall's marriage theorem.

Let $L$ be the set of left cosets of $H$. Let $R$ be the set of right cosets of $H$.

$L$ and $R$ are partitions of G, and the size of each of their elementes is equal to $|H|$.

Now let define the a bipartite graph with vertex set $(L+R)$ (where $L$ and $R$ are the bipartite sets). We will say that there exists an edge between $A\in L$ and $B \in R$ if and only if $A \cap B \not= \emptyset$.

Suppose that there is a set $S \subset L$ such that that $N(S) < S$ (The opposite of Hall's marriage theorem hypothesis).

It's easy to see that $|\cup N(S)| = |H||N(S)|$ and $|\cup S| = |H||S|$ (if you have troubles seeing this, remember that all the cosets have exactly the same size).

Then, our assumption implies that $|\cup N(S)| < |\cup S|$. But this is absurd.

This is saying that there is at least one element of $\cup S$ that is not covered by an element of $R$, but $L$ and $R$ are both partitions so for sure for each element of $|\cup S|$ there is someone in $R$ containing it.

Then, Hall's marriage theorem hypothesis holds. So there is a perfect matching M. As our edges represent non empty set intersections, its enough to take an element of each intersection in M to get a left transversal of $H$ that is also a right transversal of $H$.

share|improve this answer
Yes that is a good proof that such a transversal exists. However, my question was can anyone think of a situation when the existence of such a transversal would be useful? –  David Ward Mar 8 '13 at 12:07
Ooops. I missed that part when reading. I'm really sorry. I thought you were asking for the proof. As soon as I find a good use for such transversals, I get back to you. –  RChuck Norris Mar 8 '13 at 15:45
Not a problem. It's always good to have a proof as an answer in case people haven't seen it already. –  David Ward Mar 8 '13 at 20:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.