10
$\begingroup$

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.

  • 0
    @ThomasAndrews Yes, I do mean a left transversal of $H$. Thanks for pointing out the (now corrected) error.2012-04-20

2 Answers 2

5

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$.

1

I have used it several times to work with actions on Riemann surfaces and the corresponding quotient surface. See for instance Lemma 3.3 in "A Galois-theoretic approach to Kanev's correspondence", Manuscripta Math. 125 (2008), no. 2, 225–240; or "Prym-Tyurin varieties via Hecke algebras", J. Reine Angew. Math. 634 (2009), 209–234. I now need to know some algorithm (preferably on Magma) to compute such transversal, can you help me with this?