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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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$.