Después de pensar un poco en esto, resulta que es fácil dar una prueba utilizando el formulación teórica de los gráficos del teorema del matrimonio de Hall .
Dejemos que $L$ sea el conjunto de cosetas izquierdas de $H$ . Sea $R$ sea el conjunto de cosets derechos de $H$ .
$L$ y $R$ son particiones de G, y el tamaño de cada uno de sus elementos es igual a $|H|$ .
Definamos ahora el grafo bipartito con conjunto de vértices $(L+R)$ (donde $L$ y $R$ son los conjuntos bipartitos). Diremos que existe una arista entre $A\in L$ y $B \in R$ si y sólo si $A \cap B \not= \emptyset$ .
Supongamos que existe un conjunto $S \subset L$ de tal manera que $|N(S)| < |S|$ (Lo contrario de la hipótesis del teorema del matrimonio de Hall).
Es fácil ver que $|\cup N(S)| = |H||N(S)|$ y $|\cup S| = |H||S|$ (si tienes problemas para ver esto, recuerda que todos los cosets tienen exactamente el mismo tamaño).
Entonces, nuestra suposición implica que $|\cup N(S)| < |\cup S|$ . Pero esto es absurdo.
Esto es decir que hay al menos un elemento de $\cup S$ que no está cubierto por un elemento de $R$ pero $L$ y $R$ son ambas particiones por lo que seguro que para cada elemento de $|\cup S|$ hay alguien en $R$ que lo contiene.
Entonces, se cumple la hipótesis del teorema del matrimonio de Hall. Como nuestras aristas representan intersecciones de conjuntos no vacíos, basta con tomar un elemento de cada intersección en M para obtener una transversal izquierda de $H$ que también es una transversal derecha de $H$ .
0 votos
¿Se refiere a una travesía por la izquierda de $H$ ? mathworld.wolfram.com/Transversal izquierda.html
0 votos
@ThomasAndrews Sí, me refiero a una transversal izquierda de $H$ . Gracias por señalar el error (ahora corregido).