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 establece una condición necesaria y suficiente para que exista un objeto:

• La formulación combinatoria responde a la pregunta de 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 es al menos tan grande como el número de conjuntos en el grupo.
• La formulación de la teoría de grafos responde a la pregunta de si un grafo bipartito finito tiene una correspondencia perfecta , es decir, una manera de hacer coincidir cada vértice de un grupo de manera ú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 un vecindario de tamaño igual o mayor.

Formulación combinatoria

Declaración

Sea una familia finita de conjuntos (nótese que aunque no se permite que sea infinita, los conjuntos que la componen pueden serlo, y pueden contener el mismo conjunto varias veces ). ^[1] Sea la unión de todos los conjuntos en , el conjunto de elementos que pertenecen al menos a uno de sus conjuntos. Una transversal para 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 de contiene al menos tantos miembros distintos como su número de conjuntos. Es decir, para todos los , Si existe una transversal entonces la condición de matrimonio debe ser verdadera: la función utilizada para definir la transversal se aplica a un subconjunto de su unión, de tamaño igual a , por lo que toda la unión debe ser al menos tan grande. El teorema de Hall establece que lo inverso también es verdadero: ${\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 la familia con y La transversal podría generarse por la función que asigna a , a , y a , o alternativamente por la función que asigna a , a , y a . Hay 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 un tamaño igual al conjunto de representantes al que se asigna, que es menor o igual al tamaño de la unión de la subfamilia. ${\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}}}$$ ${\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 del matrimonio violada

Ejemplo 2

Consideremos que no existe ninguna transversal válida; la condición de matrimonio se viola como lo muestra la subfamilia . Aquí el número de conjuntos en la subfamilia es , mientras que la unión de los tres conjuntos contiene solo dos elementos. ${\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}}}$$ ${\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 familia finita dada 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 si , o si . ^[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}$

Recordemos que una transversal de una familia es una sucesión ordenada, por lo que dos transversales diferentes podrían tener exactamente los mismos elementos. Por ejemplo, el conjunto , tiene y como transversales distintas. ${\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 coincidencia

Sea un grafo bipartito finito con conjuntos bipartitos y y un conjunto de aristas . Una correspondencia -perfecta (también llamada correspondencia -saturada ) es una correspondencia , un conjunto de aristas disjuntas, que cubre cada vértice en . ${\displaystyle G=(X,Y,E)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle E}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

Para un subconjunto de , denotemos como vecindad de en , el conjunto de todos los vértices en que son adyacentes a al menos un elemento de . El teorema del matrimonio en esta formulación establece que hay una coincidencia -perfecta si y solo si para cada subconjunto de : En otras palabras, cada subconjunto de debe tener suficientes vecinos en . ${\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 a se conecta a un vecino distinto de en , por lo que el número de estos vecinos coincidentes es al menos . El número de todos los vecinos de es al menos tan grande. ${\displaystyle X}$ ${\displaystyle M}$ ${\displaystyle W}$ ${\displaystyle W}$ ${\displaystyle Y}$ ${\displaystyle |W|}$ ${\displaystyle W}$

Suficiencia

Considérese el contrapositivo : si no hay coincidencia -perfecta, entonces la condición de Hall debe violarse para al menos un . Sea una coincidencia máxima, y ​​sea cualquier vértice no coincidente en . Considérense todos los caminos alternos (caminos en que alternativamente usan aristas fuera y dentro de ) comenzando desde . 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 . Entonces cada vértice en es coincidente con un vértice en , porque un camino alternativo a un vértice no coincidente podría usarse para aumentar el tamaño de la coincidencia alternando si cada una de sus aristas pertenece a 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 . Es decir, . Sin embargo, para cada vértice , cada vecino de pertenece a : se puede encontrar un camino alterno hacia , ya sea eliminando la arista coincidente del camino alterno hacia , o agregando la arista no coincidente al camino alterno hacia . Por lo tanto, y , lo que demuestra 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 grafo-teórica

Un problema en la formulación combinatoria, definido por una familia finita de conjuntos finitos con unión , puede ser traducido a un grafo bipartito donde cada arista conecta un conjunto en con un elemento de ese conjunto. Un emparejamiento -perfecto en este grafo define un sistema de representantes únicos para . En la otra dirección, a partir de cualquier grafo bipartito se puede definir una familia finita de conjuntos, la familia de vecindades de los vértices en , tal que cualquier sistema de representantes únicos para esta familia corresponde a un emparejamiento -perfecto en . De esta manera, la formulación combinatoria para familias finitas de conjuntos finitos y la formulación grafo-teórica 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 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 , cada vértice en debe tener grado finito . Los grados de los vértices en no están restringidos. ${\displaystyle G=(X,Y,E)}$ ${\displaystyle X}$ ${\displaystyle Y}$

Prueba topológica

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

Aplicaciones

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

De manera más abstracta, sea un grupo , y sea 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 en . ^[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 puede extenderse 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 forma parte de una colección de teoremas de combinatoria notablemente poderosos, todos los cuales están relacionados entre sí en un sentido informal, ya que es más sencillo demostrar uno de estos teoremas a partir de otro de ellos que a partir de los primeros principios. Estos 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)
• Teorema de flujo máximo y corte mínimo (algoritmo de Ford-Fulkerson)
• El teorema de Birkhoff-Von Neumann (1946)
• Teorema de Dilworth .

En particular, ^{[8] [9]} hay pruebas simples de las implicaciones 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 ajustar el resultado de una manera que permitió que la prueba funcionara para infinito . ^[10] Esta variante extiende 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 sólo si satisface la condición de matrimonio. ${\displaystyle {\mathcal {F}}=\{A_{i}\}_{i\in I}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

La condición del 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 permiten conjuntos infinitos.

Sea la familia, , para . La condición de matrimonio se cumple 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 de la teoría de grafos de la extensión de Marshal Hall del teorema del matrimonio puede enunciarse 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 los bordes del grafo) de C a D , y que es estrictamente menor en el grafo si además no hay inyección en el grafo en la otra dirección. Nótese que la omisión 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 hay un 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) se permite en general sólo si se acepta el axioma de elección .

Variante de correspondencia fraccionaria

Una correspondencia 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 correspondencia 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 un emparejamiento fraccionario X-perfecto. La implicación se deriva directamente del hecho de que el emparejamiento X -perfecto es un caso especial de un emparejamiento fraccionario X -perfecto, en el que cada peso es 1 (si la arista está en el emparejamiento) o 0 (si no lo está).
• G satisface la condición de matrimonio 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 las aristas 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 nos dice solamente que no existe una correspondencia perfecta, pero no nos dice cuál es la correspondencia más grande que existe. Para aprender esta información, necesitamos la noción de deficiencia de un grafo . Dado un grafo bipartito G = ( X + Y , E ), la deficiencia de G con respecto a X es el máximo, sobre todos los subconjuntos W de X , de la diferencia | W | - | N _G ( W )|. Cuanto mayor sea la deficiencia, más lejos está el grafo 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 un emparejamiento de tamaño al menos | X |- d .

Generalizaciones

• El teorema de Tutte proporciona una caracterización de los emparejamientos perfectos en gráficos generales (que no son necesariamente bipartitos) .
• Una generalización del teorema de Hall a los hipergrafos bipartitos se proporciona mediante varios teoremas de tipo Hall para hipergrafos .

Notas

1. Hall 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ág. 90
3. Haxell, P. (2011). "Sobre la formación de comités". The American Mathematical Monthly . 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. Button, Jack; Chiodo, Maurice; Zeron-Medina Laris, Mariano (2014). "Gráficos de intersección de cosets para grupos". The American Mathematical Monthly . 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. Hall, Marshall (1945). "Un teorema de existencia para cuadrados latinos". Bull. Amer. Math. 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. Existe un resultado relacionado con los emparejamientos en grafos 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 el teorema de König, mientras que Roberts & Tesman (2009) se refieren a esta versión como el teorema de Kőnig-Egerváry. La versión del grafo bipartito es llamada teorema de Kőnig por Cameron (1994) y Roberts & Tesman (2009).
8. Equivalencia de siete teoremas mayores en combinatoria
9. Reichmeider 1984
10. Hall 1986, pág. 51
11. Hall 1986, pág. 51
12. Aharoni, Ron (febrero de 1984). "Teorema de dualidad de König para grafos bipartitos infinitos". Journal of the London Mathematical Society . s2-29 (1): 1–12. doi :10.1112/jlms/s2-29.1.1. ISSN  0024-6107.
13. "co.combinatorics - Versión de emparejamiento fraccionario del teorema del matrimonio de Hall". MathOverflow . Consultado el 29 de junio de 2020 .

Referencias

• Brualdi, Richard A. (2010), Combinatoria introductoria , Upper Saddle River, NJ: 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, MR  0033330
• Reichmeider, PF (1984), La equivalencia de algunos teoremas de emparejamiento combinatorio , Polygonal Publishing House, ISBN 978-0-936428-09-3
• Roberts, Fred S.; Tesman, Barry (2009), Combinatoria aplicada (2ª ed.), Boca Ratón: 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 en el momento del corte del nudo
• Teorema y algoritmo del matrimonio en Cut-the-Knot
• El teorema del matrimonio de Hall explicado intuitivamente en las notas de Lucky.

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