Teorema del matrimonio de Hall

Resultado en combinatoria y teoría de grafos.

En matemáticas , el teorema del matrimonio de Hall , demostrado por Philip Hall  (1935), es un teorema con dos formulaciones equivalentes. En cada caso, el teorema da una condición necesaria y suficiente para que exista un objeto:

• La formulación combinatoria responde si una colección finita de conjuntos tiene una transversal , es decir, si se puede elegir un elemento de cada conjunto sin repetición. La condición de Hall es que para cualquier grupo de conjuntos de la colección, el total de elementos únicos que contienen sea al menos tan grande como el número de conjuntos del grupo.
• La formulación teórica de grafos responde si un gráfico bipartito finito tiene una coincidencia perfecta , es decir, una forma de hacer coincidir cada vértice de un grupo de forma única con un vértice adyacente del otro grupo. La condición de Hall es que cualquier subconjunto de vértices de un grupo tiene una vecindad de igual o mayor tamaño.

Formulación combinatoria

Declaración

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

La colección satisface la condición de matrimonio cuando cada subfamilia contiene al menos tantos miembros distintos como su número de conjuntos. Es decir, para todos , ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {G}}\subseteq {\mathcal {F}}}$

$${\displaystyle |{\mathcal {G}}|\leq {\Bigl |}\bigcup _{S\in {\mathcal {G}}}S{\Bigr |}.}$$

${\displaystyle f}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle |{\mathcal {G}}|}$

Teorema del matrimonio de Hall  :  una familia de conjuntos finitos tiene una transversal si y sólo si satisface la condición del matrimonio. ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

Ejemplos

ejemplo 1, condición de matrimonio cumplida

Ejemplo 1

Considere a la familia con y ${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},A_{3}\}}$ ${\displaystyle X=\{1,2,3,4,5\}}$

$${\displaystyle {\begin{aligned}A_{1}&=\{1,2,3\}\\A_{2}&=\{1,4,5\}\\A_{3}&=\{3,5\}.\\\end{aligned}}}$$

La transversal podría ser generada por la función que se asigna a , a y a , o alternativamente por la función que se asigna a , a y a . Existen otras transversales, como y . Debido a que esta familia tiene al menos una transversal, se cumple la condición de matrimonio. Cada subfamilia de tiene el mismo tamaño que el conjunto de representantes al que está asignada, que es menor o igual al tamaño de la unión de la subfamilia. ${\displaystyle \{1,3,5\}}$ ${\displaystyle A_{1}}$ ${\displaystyle 1}$ ${\displaystyle A_{2}}$ ${\displaystyle 5}$ ${\displaystyle A_{3}}$ ${\displaystyle 3}$ ${\displaystyle A_{1}}$ ${\displaystyle 3}$ ${\displaystyle A_{2}}$ ${\displaystyle 1}$ ${\displaystyle A_{3}}$ ${\displaystyle 5}$ ${\displaystyle \{1,2,3\}}$ ${\displaystyle \{1,4,5\}}$ ${\displaystyle {\mathcal {F}}}$

ejemplo 2, condición de matrimonio violada

Ejemplo 2

Considere con ${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},A_{3},A_{4}\}}$

$${\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; se viola la condición de matrimonio como lo demuestra la subfamilia . Aquí el número de conjuntos de la subfamilia es , mientras que la unión de los tres conjuntos contiene sólo dos elementos. ${\displaystyle {\mathcal {G}}=\{A_{2},A_{3},A_{4}\}}$ ${\displaystyle |{\mathcal {G}}|=3}$ ${\displaystyle A_{2}\cup A_{3}\cup A_{4}=\{4,5\}}$

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

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

Formulación teórica de grafos

Los bordes azules representan una combinación.

Sea un gráfico bipartito finito con conjuntos bipartitos y un conjunto de aristas . Una coincidencia perfecta (también llamada coincidencia saturada ) es una coincidencia , un conjunto de aristas disjuntas, que cubre todos los vértices de . ${\displaystyle G=(X,Y,E)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle E}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

Para un subconjunto de , denotemos la vecindad de in , el conjunto de todos los vértices de in que son adyacentes a al menos un elemento de . El teorema del matrimonio en esta formulación establece que existe una coincidencia perfecta si y sólo si para cada subconjunto de : ${\displaystyle W}$ ${\displaystyle X}$ ${\displaystyle N_{G}(W)}$ ${\displaystyle W}$ ${\displaystyle G}$ ${\displaystyle Y}$ ${\displaystyle W}$ ${\displaystyle X}$ ${\displaystyle W}$ ${\displaystyle X}$

$${\displaystyle |W|\leq |N_{G}(W)|.}$$

${\displaystyle W}$ ${\displaystyle X}$ ${\displaystyle Y}$

Prueba

Necesidad

En una coincidencia perfecta , cada borde incidente se conecta con un vecino distinto de in , por lo que el número de estos vecinos coincidentes es al menos . El número de todos los vecinos de es al menos igual de grande. ${\displaystyle X}$ ${\displaystyle M}$ ${\displaystyle W}$ ${\displaystyle W}$ ${\displaystyle Y}$ ${\displaystyle |W|}$ ${\displaystyle W}$

Suficiencia

Considere el contrapositivo : si no hay una coincidencia perfecta, entonces se debe violar la condición de Hall para al menos uno . Sea una coincidencia máxima y sea cualquier vértice no coincidente en . Considere todos los caminos alternos (caminos que usan alternativamente bordes exteriores e interiores ) a partir de . Sea el conjunto de vértices en estos caminos que pertenecen a (incluido él mismo) y sea el conjunto de vértices en estos caminos que pertenecen a . Luego, cada vértice en coincide con un vértice en , porque se podría usar una ruta alterna a un vértice no coincidente para aumentar el tamaño de la coincidencia alternando si cada uno de sus bordes pertenece o no. Por lo tanto, el tamaño de es al menos el número de estos vecinos coincidentes de , más uno para el vértice no coincidente . Eso es, . Sin embargo, para cada vértice , cada vecino de pertenece a : se puede encontrar un camino alterno eliminando el borde coincidente del camino alterno a o agregando el borde no coincidente al camino alterno a . Por lo tanto, y , demostrando que se viola la condición de Hall. ${\displaystyle X}$ ${\displaystyle W\subseteq X}$ ${\displaystyle M}$ ${\displaystyle u}$ ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle u}$ ${\displaystyle W}$ ${\displaystyle X}$ ${\displaystyle u}$ ${\displaystyle Z}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle M}$ ${\displaystyle W}$ ${\displaystyle M}$ ${\displaystyle W}$ ${\displaystyle |Z|}$ ${\displaystyle Z}$ ${\displaystyle u}$ ${\displaystyle |W|\geq |Z|+1}$ ${\displaystyle v\in W}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle Z}$ ${\displaystyle w}$ ${\displaystyle vw}$ ${\displaystyle v}$ ${\displaystyle vw}$ ${\displaystyle v}$ ${\displaystyle Z=N_{G}(W)}$ ${\displaystyle |W|\geq |N_{G}(W)|+1}$

Equivalencia de la formulación combinatoria y la formulación teórica de grafos

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

La misma equivalencia se extiende a infinitas familias 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 gráfico bipartito , cada vértice debe tener grado finito . Los grados de los vértices no están restringidos. ${\displaystyle G=(X,Y,E)}$ ${\displaystyle X}$ ${\displaystyle Y}$

Prueba topológica

El teorema de Hall se puede demostrar (de forma no constructiva) basándose en el lema de Sperner . ^{[3] : Thm.4.1, 4.2}

Aplicaciones

El teorema tiene muchas aplicaciones. Por ejemplo, para una baraja de cartas estándar , repartida en 13 montones de 4 cartas cada uno, el teorema del matrimonio implica que es posible seleccionar una carta de cada montón de modo que las cartas seleccionadas contengan exactamente una carta de cada rango (As, 2 , 3, ..., Reina, Rey). Esto se puede hacer construyendo un gráfico bipartito con una partición que contenga las 13 pilas y la otra partición que contenga los 13 rangos. La prueba restante se deriva de la condición del matrimonio. De manera más general, cualquier gráfico bipartito regular tiene una coincidencia perfecta. ^{[4] : 2}

De manera más abstracta, sea un grupo y un subgrupo de índice finito de . Entonces, el teorema del matrimonio se puede utilizar para demostrar que existe un conjunto tal que es transversal tanto para el conjunto de clases laterales izquierdas como para las clases laterales derechas de in . ^[5] ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle H}$ ${\displaystyle G}$

El teorema del matrimonio se utiliza en las demostraciones habituales del hecho de que un rectángulo latino siempre se puede extender a un rectángulo latino cuando y, por tanto, en última instancia a un cuadrado latino . ^[6] ${\displaystyle r\times n}$ ${\displaystyle (r+1)\times n}$ ${\displaystyle r<n}$

Equivalencias lógicas

Este teorema es parte de una colección de teoremas notablemente poderosos en combinatoria, todos los cuales están relacionados entre sí en un sentido informal en el sentido de que es más sencillo demostrar uno de estos teoremas a partir de otro que a partir de primeros principios. Éstas incluyen:

• El teorema de König-Egerváry (1931) ( Dénes Kőnig , Jenő Egerváry )
• Teorema de König ^[7]
• Teorema de Menger (1927)
• El teorema del corte mínimo del flujo máximo (algoritmo de Ford-Fulkerson)
• El teorema de Birkhoff-Von Neumann (1946)
• Teorema de Dilworth .

En particular, ^{[8] [9]} hay pruebas simples de las implicaciones del teorema de Dilworth ⇔ teorema de Hall ⇔ teorema de König-Egerváry ⇔ teorema de König.

familias infinitas

Variante de Marshall Hall Jr.

Al examinar cuidadosamente la prueba original de Philip Hall , Marshall Hall Jr. (sin relación con Philip Hall) pudo modificar el resultado de una manera que permitió que la prueba funcionara para infinito . ^[10] Esta variante amplía el teorema del matrimonio de Philip Hall. ${\displaystyle {\mathcal {F}}}$

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

La condición de matrimonio no se extiende.

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

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

Formulación teórica de grafos de la variante de Marshall Hall.

La formulación teórica de grafos de la extensión del teorema del matrimonio de Marshal 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 a un subconjunto D de A en el gráfico si existe una inyección en el gráfico (es decir, usando solo bordes del gráfico) de C a D , y que es estrictamente menor en el gráfico si además no hay inyección en el gráfico en la otra dirección. Tenga en cuenta que omitir en el gráfico produce la noción ordinaria de comparar cardinalidades. El teorema del matrimonio infinito establece que existe una inyección de A a B en el gráfico, si y sólo si no hay un subconjunto C de A tal que N ( C ) sea estrictamente menor que C en el gráfico. ^[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 al tamaño de los conjuntos) se permite en general sólo si el axioma de elección es aceptado.

Variante de coincidencia fraccionaria

Una coincidencia fraccionaria en un gráfico es una asignación de pesos no negativos a cada arista, de modo que la suma de los pesos adyacentes a cada vértice sea como máximo 1. Una coincidencia fraccionaria es X perfecta si la suma de los pesos adyacentes a cada vértice es exactamente 1. Los siguientes son equivalentes para un gráfico bipartito G = ( X+Y, E ): ^[13]

• G admite una coincidencia X-perfecta.
• G admite una coincidencia fraccionaria perfecta X. La implicación se deriva directamente del hecho de que la coincidencia X perfecta es un caso especial de una coincidencia fraccionaria X perfecta, en la que cada peso es 1 (si la arista está en la coincidencia) o 0 (si no lo está).
• G satisface la condición matrimonial de Hall. La implicación es válida porque, para cada subconjunto W de X , la suma de pesos cerca de los vértices de W es | W |, por lo que los bordes adyacentes a ellos son necesariamente adyacentes a al menos |W| vértices de Y .

Variante cuantitativa

Cuando la condición de Hall no se cumple, el teorema original sólo nos dice que no existe una coincidencia perfecta, pero no dice cuál es la coincidencia más grande que existe. Para conocer esta información, necesitamos la noción de deficiencia de un gráfico . Dado un gráfico bipartito G = ( X + Y , E ), la deficiencia de G respecto de X es el máximo, sobre todos los subconjuntos W de X , de la diferencia | W | - | NG ₍ W ) |. Cuanto mayor es la deficiencia, más lejos está la gráfica de satisfacer la condición de Hall.

Utilizando el teorema del matrimonio de Hall, se puede demostrar que, si la deficiencia de un grafo bipartito G es d , entonces G admite una coincidencia de tamaño al menos | X |- d .

Generalizaciones

• El teorema de Tutte proporciona una generalización del teorema de Hall a gráficas generales (que no son necesariamente bipartitas) .
• Varios teoremas de tipo Hall para hipergrafías proporcionan una generalización del teorema de Hall a hipergrafías bipartitas .

Notas

1. Salón 1986, pág. 51. Una forma alternativa del teorema del matrimonio se aplica a familias finitas de conjuntos que pueden ser infinitos. Sin embargo, no se permite la situación de tener un número infinito de conjuntos y permitir conjuntos infinitos.
2. Reichmeider 1984, p.90
3. Haxell, P. (2011). "Sobre la formación de comités". El Mensual Matemático Estadounidense . 118 (9): 777–788. doi : 10.4169/amer.math.monthly.118.09.777. ISSN  0002-9890. JSTOR  10.4169/amer.math.monthly.118.09.777. S2CID  27202372.
4. DeVos, Matt. "Teoría de grafos" (PDF) . Universidad Simon Fraser .
5. Botón, Jack; Chiodo, Mauricio; Zeron-Medina Laris, Mariano (2014). "Gráficos de intersección de Coset para grupos". El Mensual Matemático Estadounidense . 121 (10): 922–26. arXiv : 1304.6111 . doi : 10.4169/amer.math.monthly.121.10.922. S2CID  16417209. Para un subgrupo de índice finito de , la existencia de una transversal izquierda-derecha es bien conocida, a veces presentada como una aplicación del teorema del matrimonio de Hall. ${\displaystyle H}$ ${\displaystyle G}$
6. Salón, Marshall (1945). "Un teorema de existencia de cuadrados latinos". Toro. América. Matemáticas. Soc . 51 (6): 387–388. doi : 10.1090/S0002-9904-1945-08361-X .
7. La denominación de este teorema es inconsistente en la literatura. Está el resultado sobre las coincidencias en gráficos bipartitos y su interpretación como una cobertura de matrices (0,1). Hall (1986) y van Lint & Wilson (1992) se refieren a la forma matricial como teorema de König, mientras que Roberts & Tesman (2009) se refieren a esta versión como teorema de Kőnig-Egerváry. La versión del gráfico bipartito se denomina teorema de Kőnig por Cameron (1994) y Roberts y Tesman (2009).
8. Equivalencia de siete teoremas principales en combinatoria
9. Reichmeider 1984
10. Salón 1986, pág. 51
11. Salón 1986, pág. 51
12. Aharoni, Ron (febrero de 1984). "Teorema de dualidad de König para gráficos bipartitos infinitos". Revista de la Sociedad Matemática de Londres . T2-29 (1): 1-12. doi :10.1112/jlms/s2-29.1.1. ISSN  0024-6107.
13. "co.combinatorics - Versión de correspondencia fraccionada del teorema del matrimonio de Hall". Desbordamiento matemático . Consultado el 29 de junio de 2020 .

Referencias

• Brualdi, Richard A. (2010), Combinatoria introductoria , Upper Saddle River, Nueva Jersey: Prentice-Hall/Pearson, ISBN 978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatoria: temas, técnicas, algoritmos , Cambridge: Cambridge University Press, ISBN 978-0-521-45761-3
• Hall, Marshall Jr. (1986), Teoría combinatoria (2ª ed.), Nueva York: John Wiley & Sons, ISBN 978-0-471-09138-7
• Hall, Philip (1935), "Sobre representantes de subconjuntos", J. London Math. Soc. , 10 (1): 26–30, doi :10.1112/jlms/s1-10.37.26
• Halmos, Paul R .; Vaughan, Herbert E. (1950), "El problema del matrimonio", American Journal of Mathematics , 72 (1): 214–215, doi :10.2307/2372148, JSTOR  2372148, SEÑOR  0033330
• Reichmeider, PF (1984), La equivalencia de algunos teoremas de emparejamiento combinatorio , Editorial Poligonal, ISBN 978-0-936428-09-3
• Roberts, Fred S.; Tesman, Barry (2009), Combinatoria aplicada (2ª ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
• van Lint, JH; Wilson, RM (1992), Un curso de combinatoria , Cambridge: Cambridge University Press, ISBN 978-0-521-42260-4

enlaces externos

• Teorema del matrimonio al cortar el nudo
• Teorema y algoritmo del matrimonio al cortar el nudo
• El teorema del matrimonio de Hall se explica intuitivamente en las notas de Lucky.

Este artículo incorpora material de la prueba del teorema del matrimonio de Hall en PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .