Teorema del matrimonio de Hall

Dejar${\displaystyle {\mathcal {F}}}$ser una familia finita de conjuntos (nótese que aunque${\displaystyle {\mathcal {F}}}$No se permite que sea infinito en sí mismo, los conjuntos en él pueden serlo, y${\displaystyle {\mathcal {F}}}$puede contener el mismo conjunto varias veces ). ^{[ 1 ]} Sea${\displaystyle X}$sea ​​la unión de todos los conjuntos en${\displaystyle {\mathcal {F}}}$, el conjunto de elementos que pertenecen al menos a uno de sus conjuntos. Una transversal para${\displaystyle {\mathcal {F}}}$es un subconjunto de${\displaystyle X}$que se puede obtener eligiendo un elemento distinto de cada conjunto en${\displaystyle {\mathcal {F}}}$Este concepto puede formalizarse definiendo una transversal como la imagen de una función inyectiva.${\displaystyle f:{\mathcal {F}}\to X}$de tal manera que${\displaystyle f(S)\in S}$para cada${\displaystyle S\in {\mathcal {F}}}$. Un término alternativo para transversal es sistema de representantes distintos .

La colección${\displaystyle {\mathcal {F}}}$satisface la condición de matrimonio cuando cada subfamilia de${\displaystyle {\mathcal {F}}}$contiene al menos tantos miembros distintos como su número de conjuntos. Es decir, para todos${\displaystyle {\mathcal {G}}\subseteq {\mathcal {F}}}$, $${\displaystyle |{\mathcal {G}}|\leq {\Bigl |}\bigcup _{S\in {\mathcal {G}}}S{\Bigr |}.}$$ Si existe una transversal, entonces la condición de matrimonio debe ser verdadera: la función${\displaystyle f}$utilizado para definir los mapas transversales${\displaystyle {\mathcal {G}}}$a un subconjunto de su unión, de tamaño igual a${\displaystyle |{\mathcal {G}}|}$, por lo que toda la unión debe ser al menos igual de grande. El teorema de Hall afirma que lo contrario también es cierto:

El nombre "teorema del matrimonio" proviene de ( Halmos y Vaughan 1950 ).

Supongamos que cada uno de un conjunto (posiblemente infinito) de chicos conoce a un conjunto finito de chicas. ¿Bajo qué condiciones es posible que cada chico se case con una de sus conocidas? Es evidente que es necesario que cada conjunto finito de k chicos conozca, en conjunto, al menos a k chicas... esta condición también es suficiente.

Ejemplo 1

Consideremos a la familia${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},A_{3}\}}$con${\displaystyle X=\{1,2,3,4,5\}}$y$${\displaystyle {\begin{aligned}A_{1}&=\{1,2,3\}\\A_{2}&=\{1,4,5\}\\A_{3}&=\{3,5\}.\\\end{aligned}}}$$La transversal${\displaystyle \{1,3,5\}}$podría ser generado por la función que mapea${\displaystyle A_{1}}$a${\displaystyle 1}$,${\displaystyle A_{2}}$a${\displaystyle 5}$, y${\displaystyle A_{3}}$a${\displaystyle 3}$, o alternativamente mediante la función que mapea${\displaystyle A_{1}}$a${\displaystyle 3}$,${\displaystyle A_{2}}$a${\displaystyle 1}$, y${\displaystyle A_{3}}$a${\displaystyle 5}$. Existen otras transversales, como${\displaystyle \{1,2,3\}}$y${\displaystyle \{1,4,5\}}$. Debido a que esta familia tiene al menos una transversal, se cumple la condición de matrimonio. Cada subfamilia de${\displaystyle {\mathcal {F}}}$tiene el mismo tamaño que el conjunto de representantes al que se asigna, que es menor o igual al tamaño de la unión de la subfamilia.

Ejemplo 2

Considerar${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},A_{3},A_{4}\}}$con$${\displaystyle {\begin{aligned}A_{1}&=\{2,3,4,5\}\\A_{2}&=\{4,5\}\\A_{3}&=\{5\}\\A_{4}&=\{4\}.\\\end{aligned}}}$$No existe una transversal válida; la condición de matrimonio se viola como lo demuestra la subfamilia.${\displaystyle {\mathcal {G}}=\{A_{2},A_{3},A_{4}\}}$. Aquí el número de conjuntos en la subfamilia es${\displaystyle |{\mathcal {G}}|=3}$, mientras que la unión de los tres conjuntos${\displaystyle A_{2}\cup A_{3}\cup A_{4}=\{4,5\}}$Contiene solo dos elementos.

Un límite inferior en el número diferente de transversales que una familia finita dada${\displaystyle {\mathcal {F}}}$de tamaño${\displaystyle n}$puede tener se obtiene de la siguiente manera: Si cada uno de los conjuntos en${\displaystyle {\mathcal {F}}}$tiene cardinalidad${\displaystyle \geq r}$, entonces el número de transversales diferentes para${\displaystyle {\mathcal {F}}}$es o${\displaystyle r!}$si${\displaystyle r\leq n}$, o${\displaystyle r(r-1)\cdots (r-n+1)}$si${\displaystyle r>n}$. ^{[ 2 ]}

Recuerda que una transversal para una familia${\displaystyle {\mathcal {F}}}$es una secuencia ordenada, por lo que dos transversales diferentes podrían tener exactamente los mismos elementos. Por ejemplo, la colección${\displaystyle A_{1}=\{1,2,3\}}$,${\displaystyle A_{2}=\{1,2,5\}}$tiene${\displaystyle (1,2)}$y${\displaystyle (2,1)}$como transversales distintas.

Un problema en la formulación combinatoria, definido por una familia finita de conjuntos finitos.${\displaystyle {\mathcal {F}}}$con unión${\displaystyle X}$se puede traducir en un grafo bipartito${\displaystyle G=({\mathcal {F}},X,E)}$donde cada arista conecta un conjunto en${\displaystyle {\mathcal {F}}}$a un elemento de ese conjunto. Un${\displaystyle {\mathcal {F}}}$-la correspondencia perfecta en este gráfico define un sistema de representantes únicos para${\displaystyle {\mathcal {F}}}$. En la otra dirección, desde cualquier grafo bipartito${\displaystyle G=(X,Y,E)}$se puede definir una familia finita de conjuntos, la familia de vecindarios de los vértices en${\displaystyle X}$, de tal manera que cualquier sistema de representantes únicos para esta familia corresponde a un${\displaystyle X}$-combinación perfecta en${\displaystyle G}$De esta forma, la formulación combinatoria para familias finitas de conjuntos finitos y la formulación teórica de grafos para grafos finitos son equivalentes.

La misma equivalencia se extiende a familias infinitas de conjuntos finitos y a ciertos grafos infinitos. En este caso, la condición de que cada conjunto sea finito corresponde a una condición de que en el grafo bipartito${\displaystyle G=(X,Y,E)}$, cada vértice en${\displaystyle X}$debe tener grado finito . Los grados de los vértices en${\displaystyle Y}$no están restringidos.

Al examinar cuidadosamente la demostración original de Philip Hall , Marshall Hall Jr. (sin parentesco con Philip Hall) pudo modificar el resultado de manera que la demostración funcionara para un número infinito de casos.${\displaystyle {\mathcal {F}}}$. ^{[ 10 ]} Esta variante extiende el teorema del matrimonio de Philip Hall.

Supongamos que${\displaystyle {\mathcal {F}}=\{A_{i}\}_{i\in I}}$es una familia (posiblemente infinita) de conjuntos finitos que no necesariamente son distintos, entonces${\displaystyle {\mathcal {F}}}$tiene una transversal si y solo si${\displaystyle {\mathcal {F}}}$cumple con la condición de matrimonio.

El siguiente ejemplo, debido a Marshall Hall Jr., muestra que la condición de matrimonio no garantiza la existencia de una transversal en una familia infinita en la que se permiten conjuntos infinitos.

Dejar${\displaystyle {\mathcal {F}}}$ser la familia,${\displaystyle A_{0}=\mathbb {N} }$,${\displaystyle A_{i}=\{i-1\}}$para${\displaystyle i\geq 1}$. La condición de matrimonio se cumple para esta familia infinita, pero no se puede construir ninguna transversal. ^{[ 11 ]}

La formulación en teoría de grafos de la extensión del teorema del matrimonio de Marshall Hall se puede enunciar de la siguiente manera: Dado un grafo bipartito con lados A y B , decimos que un subconjunto C de B es menor o igual en tamaño que un subconjunto D de A en el grafo si existe una inyección en el grafo (es decir, utilizando solo aristas del grafo) de C a D , y que es estrictamente menor en el grafo si, además, no existe ninguna inyección en el grafo en la otra dirección. Nótese que omitir en el grafo produce la noción ordinaria de comparación de cardinalidades. El teorema del matrimonio infinito establece que existe una inyección de A a B en el grafo, si y solo si no existe ningún subconjunto C de A tal que N ( C ) sea estrictamente menor que C en el grafo. ^{[ 12 ]}

El problema más general de seleccionar un elemento (no necesariamente distinto) de cada uno de una colección de conjuntos no vacíos (sin restricción en cuanto al número de conjuntos o el tamaño de los conjuntos) está permitido en general solo si se acepta el axioma de elección .