Teorema del matrimonio de Hall

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 un elemento puede ser elegido de cada conjunto sin repetición. La condición de Hall es que para cualquier grupo de conjuntos de la colección, los elementos únicos totales que contienen es al menos tan grande como el número de conjuntos en el grupo.
• La formulación teórica gráfica responde si un gráfico bipartito finito tiene una combinación perfecta, es decir, una manera de igualar cada vértice de un grupo única a un vértice adyacente del otro grupo. La condición de Hall es que cualquier subconjunto de vértices de un grupo tiene un barrio de igual o mayor tamaño.

Formulación combinatoria

Declaración

Vamos F{displaystyle {fnMithcal}} ser una familia finita de conjuntos (nota que aunque F{displaystyle {fnMithcal}} no se permite por sí mismo ser infinito, los conjuntos en puede ser así, y F{displaystyle {fnMithcal}} puede contener el mismo conjunto varias veces). Vamos X{displaystyle X} ser la unión de todos los conjuntos en F{displaystyle {fnMithcal}}, el conjunto de elementos que pertenecen al menos a uno de sus conjuntos. A transversal para F{displaystyle {fnMithcal}} es un subconjunto de X{displaystyle X} que se puede obtener eligiendo un elemento distinto de cada conjunto en F{displaystyle {fnMithcal}}. Este concepto se puede formalizar definiendo un concepto transversal a ser la imagen de una función inyectable f:F→ → X{displaystyle f:{Mathcal {F}to X} tales que f()S)▪ ▪ S{displaystyle f(S)in S} para cada uno S▪ ▪ F{displaystyle Sin {fn}. Un mandato alternativo transversal es sistema de representantes distintos.

La colección F{displaystyle {fnMithcal}} satisfizo el condición matrimonial cuando cada subfamilia de F{displaystyle {fnMithcal}} contiene al menos tantos miembros distintos como su número de conjuntos. Eso es, para todos G⊆ ⊆ F{displaystyle {Mathcal {}subseteq {Mathcal {}}},

SilencioGSilencio≤ ≤ Silencio⋃ ⋃ S▪ ▪ GSSilencio.{displaystyle Silencio {fnMitcal {fnh} {Bigl TENIDO }bigcup _{Sin {Mathcal Está bien.

f{displaystyle f}

G{displaystyle {Mathcal {}}}

SilencioGSilencio{displaystyle Silencio {fnMithcal {fn}

Ejemplos

ejemplo 1, condición matrimonial

Ejemplo 1

Considerar la familia F={}A1,A2,A3}{displaystyle {mathcal {}={A_{1},A_{2},A_{3}}} con X={}1,2,3,4,5}{displaystyle X={1,2,3,4,5} y

A1={}1,2,3}A2={}1,4,5}A3={}3,5}.{displaystyle {begin{aligned}A_{1} limit={1,2,3}A_{2} limit={1,4,5}\\\A_{3} {3}\\\fnMicrosoft Sans Serif}

La transversal {}1,3,5}{displaystyle {1,3,5}} podría ser generado por la función que mapas A1{displaystyle A_{1} a 1{displaystyle 1}, A2{displaystyle A_{2} a 5{displaystyle 5}, y A3{displaystyle A_{3} a 3{displaystyle 3}, o alternativamente por la función que mapa A1{displaystyle A_{1} a 3{displaystyle 3}, A2{displaystyle A_{2} a 1{displaystyle 1}, y A3{displaystyle A_{3} a 5{displaystyle 5}. Hay otros transversales, como {}1,2,3}{displaystyle {1,2,3}} y {}1,4,5}{displaystyle{1,4,5}}. Debido a que esta familia tiene al menos una transversal, se cumple la condición matrimonial. Cada subfamilia de F{displaystyle {fnMithcal}} tiene igual tamaño al conjunto de representantes a los que se asigna, que es inferior o igual al tamaño de la unión de la subfamilia.

ejemplo 2, estado de matrimonio violado

Ejemplo 2

Considerar F={}A1,A2,A3,A4}{displaystyle {mathcal {}={A_{1},A_{2},A_{3},A_{4}}} con

A1={}2,3,4,5}A2={}4,5}A3={}5}A4={}4}.{displaystyle {begin{aligned}A_{1} limit={2,3,4,5}A_{2} âTMa={4,5}\A_{3} â3}{5\\\A_{4} limit={4}\\\\_end{aligned}}}}}}}}}}}}}}}}}}}}}\\\\\\\\\\\\\\\\\\\\\\\splaystyle {displaystyle {}}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

No existe ninguna transversal válida; la condición matrimonial es violada como lo muestra la subfamilia G={}A2,A3,A4}{displaystyle {mathcal {}={A_{2},A_{3},A_{4}}}. Aquí está el número de sets en la subfamilia SilencioGSilencio=3{fnMicrosoft Sans Serif}Principalmente*, mientras la unión de los tres conjuntos A2∪ ∪ A3∪ ∪ A4={}4,5}{displaystyle A_{2}cup A_{3}cup A_{4}={4,5} contiene sólo dos elementos.

Un límite inferior en el número de transversales que una determinada familia finita F{displaystyle {fnMithcal}} de tamaño n{displaystyle n} se puede haber obtenido de la siguiente manera: Si cada uno de los conjuntos F{displaystyle {fnMithcal}} tiene cardenalidad ≥ ≥ r{displaystyle geq r}, entonces el número de diferentes transversales para F{displaystyle {fnMithcal}} o r!{displaystyle r} si r≤ ≤ n{displaystyle rleq n}, o r()r− − 1)⋯ ⋯ ()r− − n+1){displaystyle r(r-1)cdots (r-n+1)} si n}" xmlns="http://www.w3.org/1998/Math/MathML">r■n{displaystyle riéndosen}n}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d9bd1c43862f4802ea2e4bd544cddd2d407a0b8e" style="vertical-align: -0.338ex; width:5.542ex; height:1.843ex;"/>.

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

Formulación teórica de grafos

los bordes azules representan una coincidencia

Vamos G=()X,Y,E){displaystyle G=(X,Y,E)} ser un gráfico bipartito finito con conjuntos bipartitos X{displaystyle X} y Y{displaystyle Sí. y filo E{displaystyle E}. An X{displaystyle X}- perfecta coincidencia (también llamado X{displaystyle X}- saturación coincidente) es un conjunto de bordes descomunales, que cubre cada vértice en X{displaystyle X}.

Para un subconjunto W{displaystyle W. de X{displaystyle X}, vamos NG()W){displaystyle N_{G}(W)} denota el barrio W{displaystyle W. dentro G{displaystyle G., el conjunto de todos los vértices en Y{displaystyle Sí. que están adyacentes a al menos un elemento W{displaystyle W.. El teorema matrimonial en esta formulación declara que hay un X{displaystyle X}- perfecto si y sólo si por cada subconjunto W{displaystyle W. de X{displaystyle X}:

SilencioWSilencio≤ ≤ SilencioNG()W)Silencio.{displaystyle SilencioW sobrevivirleq SilencioN_{G}(W)

W{displaystyle W.

X{displaystyle X}

Y{displaystyle Sí.

Prueba

Necesidad

En un X{displaystyle X}- perfecta coincidencia M{displaystyle M}, cada incidente en el borde W{displaystyle W. se conecta a un vecino distinto de W{displaystyle W. dentro Y{displaystyle Sí., por lo que el número de estos vecinos coinciden es al menos SilencioWSilencio{displaystyle Silencioso. El número de todos los vecinos de W{displaystyle W. es al menos tan grande.

Suficiencia

Considere el contrapositivo: si no hay X{displaystyle X}-Perfecto que coincida entonces la condición de Hall debe ser violado por al menos uno W⊆ ⊆ X{displaystyle Wsubseteq X}. Vamos M{displaystyle M} ser un máximo coincidente, y dejar u{displaystyle u} ser cualquier vértice inigualable en X{displaystyle X}. Considerar todos caminos alternantes (pata en G{displaystyle G. que alternativamente usan los bordes fuera y dentro M{displaystyle M}) a partir de u{displaystyle u}. Vamos W{displaystyle W. ser el conjunto de vértices en estos caminos que pertenecen a X{displaystyle X} (incluidas u{displaystyle u} en sí mismo) y Z{displaystyle Z} ser el conjunto de vértices en estos caminos que pertenecen a Y{displaystyle Sí.. Entonces cada vértice en Z{displaystyle Z} es igualado por M{displaystyle M} a un vértice en W{displaystyle W., porque un camino alternado a un vértice inigualable podría ser utilizado para aumentar el tamaño de la coincidencia al mezclar si cada uno de sus bordes pertenece a M{displaystyle M} o no. Por lo tanto, el tamaño de W{displaystyle W. es por lo menos el número SilencioZSilencio{displaystyle Silencioso de estos vecinos emparejados de Z{displaystyle Z}, más uno para el vertex sin igual u{displaystyle u}. Eso es, SilencioWSilencio≥ ≥ SilencioZSilencio+1{displaystyle ← Silencioso. Sin embargo, para cada vértice v▪ ▪ W{displaystyle vin W}, cada vecino w{displaystyle w} de v{displaystyle v} pertenece Z{displaystyle Z}: un camino alternado a w{displaystyle w} se puede encontrar ya sea eliminando el borde emparejado vw{displaystyle vw} desde el camino alternado hasta v{displaystyle v}, o añadiendo el borde inigualable vw{displaystyle vw} a la ruta alternada v{displaystyle v}. Por lo tanto, Z=NG()W){displaystyle Z=N_{G}(W)} y SilencioWSilencio≥ ≥ SilencioNG()W)Silencio+1{fnMicrosoft Sans Serif}*mostrando que la condición de Hall es violada.

Equivalencia de la formulación combinatoria y la formulación grafo-teórica

Un problema en la formulación combinatoria, definida por una familia finita de conjuntos finitos F{displaystyle {fnMithcal}} con unión X{displaystyle X} se puede traducir en un gráfico bipartito G=()F,X,E){displaystyle G=({mathcal {F},X,E)} donde cada borde conecta un conjunto F{displaystyle {fnMithcal}} a un elemento de ese conjunto. An F{displaystyle {fnMithcal}}-perfecto en este gráfico define un sistema de representantes únicos para F{displaystyle {fnMithcal}}. En la otra dirección, desde cualquier gráfico bipartito G=()X,Y,E){displaystyle G=(X,Y,E)} uno puede definir una familia finita de conjuntos, la familia de barrios de los vértices en X{displaystyle X}, tal que cualquier sistema de representantes únicos para esta familia corresponde a un X{displaystyle X}-Perfecto que coincida en G{displaystyle G.. De esta manera, la formulación combinatoria para familias finitas de conjuntos finitos y la formulación gráfica-teorética para gráficos finitos son equivalentes.

La misma equivalencia se extiende a familias infinitas de conjuntos finitos y a ciertos gráficos infinitos. En este caso, la condición de que cada conjunto sea finito corresponde a una condición que en el gráfico bipartito G=()X,Y,E){displaystyle G=(X,Y,E)}, cada vértice en X{displaystyle X} debería tener un grado finito. Los grados de los vértices en Y{displaystyle Sí. no están limitados.

Prueba topológica

El teorema de Hall se puede probar (de manera no constructiva) con base en el lema de Sperner.

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). De manera más general, cualquier gráfico bipartito regular tiene una coincidencia perfecta.

Más abstractamente, vamos G{displaystyle G. ser un grupo, y H{displaystyle H. ser un subgrupo de índice finito G{displaystyle G.. Entonces el teorema del matrimonio se puede utilizar para demostrar que hay un conjunto T{displaystyle T} tales que T{displaystyle T} es una transversal para el conjunto de cosets izquierdos y cosets derecho de H{displaystyle H. dentro G{displaystyle G..

El teorema de matrimonio se utiliza en las pruebas habituales del hecho de que un r× × n{displaystyle rtimes n} El rectángulo latino siempre se puede extender a un ()r+1)× × n{displaystyle (r+1)times n} rectángulo latino cuando <math alttext="{displaystyle rr.n{displaystyle r maden}<img alt="{displaystyle r, y así, en última instancia a una plaza latina.

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 que es más sencillo demostrar uno de estos teoremas a partir de otro que a partir de los primeros principios. Éstas incluyen:

• The König–Egerváry theorem (1931) (Dénes Kőnig, Jenő Egerváry)
• Teorema de König
• Teorema de Menger (1927)
• The max-flow min-cut theorem (Ford–Fulkerson algoritmo)
• El teorema Birkhoff-Von Neumann (1946)
• El teorema de Dilworth.

En particular, existen demostraciones 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) fue capaz de ajustar el resultado de una manera que permitió que la prueba trabajara para infinito F{displaystyle {fnMithcal}}. Esta variante extiende el teorema del matrimonio de Philip Hall.

Supongamos que F={}Ai}i▪ ▪ I{fnMicrosoft} {fnMicrosoft} {fnMicrosoft} {fn} {fn} {fn}} {fn}f}}fn}fnfn}fnfnfn}\fnfn}}\fnfnKcH0}fn}}}\\fn}\\\fn}\\\\fn}\\fn}\fn}\\\fn}\\\\\\fn}\\fn}fn}\\\\\fn}fn}fn}fn}\\\\\fn}\\\fn}fn}fn}fn}\\\\\\fn}\\\ I}, es una familia (posiblemente infinita) de conjuntos finitos que no necesitan ser distintos, entonces F{displaystyle {fnMithcal}} tiene una transversal si y sólo si F{displaystyle {fnMithcal}} satisface la condición matrimonial.

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 permiten conjuntos infinitos.

Vamos F{displaystyle {fnMithcal}} ser la familia, A0=N{displaystyle A_{0}=Mathbb {N}, Ai={}i− − 1}{displaystyle A_{i}={i-1} para i≥ ≥ 1{displaystyle igeq 1}. La condición matrimonial es para esta familia infinita, pero no se puede construir transversalmente.

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 establecer de la siguiente manera: dado un grafo bipartito con lados A y B, decir que un subconjunto C de B es más pequeño 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 los 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 el otro sentido. 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 solo si no hay un subconjunto C de A tal que N(C) es estrictamente menor que C en el gráfico.

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 solo si el axioma de elección es aceptada.

Variante de coincidencia fraccional

Una coincidencia fraccionaria en un gráfico es una asignación de pesos no negativos a cada borde, de modo que la suma de los pesos adyacentes a cada vértice es como máximo 1. Una coincidencia fraccionaria es X-perfecto 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):

• G Admite que un X-perfecto coincide.
• G admite una coincidencia fraccional X-perfecto. La implicación se debe directamente al hecho de que X-La coincidencia perfecta es un caso especial X-porfecto emparejamiento fraccional, en el que cada peso es 1 (si el borde está en juego) o 0 (si no lo es).
• G satisface la condición matrimonial de Hall. La implicación sostiene porque, para cada subconjunto W de X, la suma de pesos cerca de vértices de W es la vidaWtención, por lo que los bordes adyacentes a ellos están necesariamente adyacentes a al menos Silencio vertices de Y.

Variante cuantitativa

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

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

Generalizaciones

• El teorema de Tutte proporciona una generalización del teorema de Hall a los gráficos generales (que no son necesariamente bipartitos).
• La generalización del teorema de Hall a hipergrafías bipartitas es proporcionada por varios teoremas tipo Hall para hipergrafos.