Teorema de Hall

El teorema del matrimonio de Hall, o simplemente Teorema de Hall, es un teorema con dos formulaciones equivalentes:

• La formulación por matemática combinatoria trata de una colección de conjuntos finitos. Da una condición necesaria y suficiente para poder seleccionar un elemento distinto de cada conjunto.
• La formulación por teoría de grafos trata de un grafo bipartito. Da una condición necesaria y suficiente para encontrar una emparejamiento que cubre por lo menos un lado de la gráfica.

Formulación Combinatoria

Sea S una familia de conjuntos finitos, donde la familia puede contener un número infinito de conjuntos y los conjuntos individuales pueden repetirse varias veces.​

Una transversal para S es un conjunto T y una biyección f desde T a S tal que para todo t en T, t es miembro de f(t). Un término alternativo para transversal es sistema de representantes distintos.

La colección S satisface la condición de matrimonio si y solo si para cada sub colección $W\subseteq S$, tenemos

$|W|\leq {\Bigl |}\bigcup _{A\in W}A{\Bigr |}.$

En otras palabras, el número de conjuntos en cada sub colección W es menor o igual que el número de elementos distintos en la unión sobre la sub colección W.

El teorema de Hall indica que S tiene una transversal si y sólo si S satisface la condición de matrimonio.

Ejemplos

ejemplo

Ejemplo 1: Considere S = {A₁, A₂, A₃} con

A₁ = {1, 2, 3}

A₂ = {1, 4, 5}

A₃ = {3, 5}.

Una transversal válida sería (1, 4, 5). (Tenga en cuenta que esto no es único: (2, 1, 3 funciona igualmente bien, por ejemplo.)

ejemplo 2

Ejemplo 2: Considere S = {A₁, A₂, A₃, A₄} con

A₁ = {2, 3, 4, 5}

A₂ = {4, 5}

A₃ = {5}

A₄ = {4}.

No existe ninguna transversal válida. La condición de matrimonio es violada como lo demuestra la sub colección {A₂, A₃, A₄}.

Ejemplo 3: Considere S= {A₁, A₂, A₃, A₄} con

A₁ = {a, b, c}

A₂ = {b, d}

A₃ = {a, b, d}

A₄ = {b, d}.

Las únicas transversales válidas son (c, b, a, d) y (c, d, a, b).

Aplicaciones

El ejemplo estándar de una aplicación del teorema del matrimonio es imaginar dos grupos; uno de n hombres, y uno de n mujeres. Por cada mujer hay un subconjunto de los hombres, cualquiera de los cuales se casaría felizmente; y cualquier hombre estaría feliz de casarse con una mujer que quiere casarse con él. Considere si es posible hacer pareja (en el matrimonio) a los hombres y mujeres para que cada persona sea feliz.

Si dejamos que A_i sea el conjunto de hombres que la mujer i-th sería feliz de casarse, entonces el teorema del matrimonio establece que cada mujer puede casarse felizmente con un hombre si y sólo si la colección de conjuntos {A_i} cumple con la condición de matrimonio.

Tenga en cuenta que la condición de matrimonio es que, para cualquier subconjunto $I$ de las mujeres, el número de hombres que al menos una de las mujeres estaría feliz de casarse, $|\bigcup _{i\in I}A_{i}|$, ser al menos tan grande como el número de mujeres en ese subconjunto, $|I|$. Es obvio que esta condición es necesaria, como si no se sostenga, no hay suficientes hombres para compartir entre las $I$ mujeres. Lo interesante es que también es una condición suficiente .

Formulación de teoría de grafos

emparejamiento

Sea G un grafo bipartito finito con conjuntos bipartitos X y Y (G:= (X + Y, E)). Para un conjunto W de vértices en X, sea $N_{G}(W)$ que denota vecindad de W en G, i.e. el conjunto de todos los vértices en Y adyacentes a algún elemento de W. El teorema del matrimonio en esta formulación establece que hay un emparejamiento que abarca completamente X si y solo si para cada subconjunto W de X:

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

En otras palabras cada subconjunto W de X tiene suficientes vértices adyacentes en Y.

Dado un grafo bipartito finito G:= (X + Y, E), con conjuntos bipartitos X y Y de igual tamaño, el teorema del matrimonio proporciona condiciones necesarias y suficientes para la existencia de un emparejamiento perfecto en el grafo.

Una generalización para grafos en general (no necesariamente bipartitos) es proporcionada por el Teorema de Tutte.

Demostración de la versión por Teoría de Grafos

Un X- emparejamiento saturado es un emparejamiento que cubre cada vértice en X.

Primero demostramos: Si un grafo bipartito G = (X + Y, E) = G(X, Y) tiene un X-emparejamiento saturado, entonces |N_G(W)| ≥ |W| para todo W ⊆ X.

Supongamos que M es un emparejamiento que satura cada vértice de X. Sea el conjunto de todos los vértices Y emparejado por M con un W denotado como M(W). Por lo tanto, |M(W)|=|W|, por la definición de emparejamiento. Pero M(W) ⊆ N_G(W), ya que todos los elementos de M(W) son vecinos de W. Así, |N_G(W)| ≥ |M(W)| y por lo tanto, |N_G(W)| ≥ |W|.

Ahora probamos: Si |N_G(W)| ≥ |W| para todo W ⊆ X, entonces G(X,Y)tiene un emparejamiento que satura cada vértice en X.

Supongamos que G(X,Y) es un grafo bipartito que no tiene un emparejamiento que satura todo los vértices de X. Sea M un emparejamiento máximo, y u un vértice no saturado por M. Considere todos los caminos alternativos (es decir, caminos en G que alterna entre aristas hacia afuera y hacia adentro en M) comenzando desde u. Sea T el conjunto de todos los puntos de Y conectados a u por estos caminos alternativos, y W el conjunto de todos los puntos en X conectados a u por estos caminos alternativos (incluyendo u). Un camino alternativo no maximal puede terminar en un vértice en Y, para que no sea un camino aumentativo, para que pudiéramos aumentar M a un emparejamiento estrictamente mayor. Así cada vértice en T es emparejado por M con un vértice en W \ {u}. Por el contrario, cada vértice v en W \ {u} es emparejado por M a un vértice en T (es decir, el vértice precedente v en un camino alternativo que termina en v). Por lo tanto, M proporciona una biyección de W \ {u} y T, lo que implica que |W| = |T| + 1. Por otra parte, N_G(W) ⊆ T: deje v en Y se conecte a un vértice w in W. Si la arista (w,v) está en M, entonces v esta en T por la parte anterior de la demostración, por otra parte podemos tomar un camino alternativo que acaba en w y extenderlo con v, obteniendo un camino aumentativo y mostrando que v esta en T. Por lo tanto, |N_G(W)| = |T| = |W| − 1, una contradicción.

Equivalencia de la formulación combinatoria y la formulación por teoría de grafos

Sea S = (A₁, A₂,..., A_n) donde los A_i son conjuntos finitos no necesariamente distintos. Sea el conjunto X = {A₁, A₂,..., A_n} (que es, el conjunto de nombres de los elementos S) y el conjunto Y sea la unión de todos los elementos en todos los A_i.

Formamos un grafo bipartito finito G:= (X + Y, E con conjuntos bipartitos X y Y uniendo cualquier elemento en Y a cada A_i del que es miembro. Una transversal de S es un X- emparejamiento saturado un emparejamiento que cubre cada vértice en X) de un grafo bipartito G. Así un problema en formulación combinatoria puede ser fácilmente traducido a un problema con una formulación basada en teoría de grafos.

Variante de Marshall Hall Jr.

Al examinar cuidadosamente la demostración 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 funcionara para S infinito.​ Esta variante refina el teorema del matrimonio y proporciona un límite inferior sobre el número de transversales que puede tener un S dado. Esta variante es:​

Supongamos que (A₁, A₂, ..., A_n), donde los A_i son conjuntos finitos que no necesitan ser distintos, es una familia de conjuntos que satisfacen la condición de matrimonio, y supongamos que |A_i| ≥ r para i = 1, ..., n. Entonces el número de transversales diferentes para la familia es al menos r! si r ≤ n y r(r - 1) ... (r - n +1) si r > n.

Recordemos que una transversal para una familia S es una secuencia ordenada, por lo que dos transversales diferentes podrían tener exactamente los mismos elementos. Por ejemplo, la familia A₁ = {1,2,3}, A₂ = {1,2,5} tiene ambos (1,2) y (2,1) como transversales diferentes.

Aplicaciones

El teorema tiene muchas otras aplicaciones "no maritales". Por ejemplo, tomar una baraja de cartas estándar, y repartir las cartas en 13 pilas de 4 cada una. Entonces, usando el teorema del matrimonio, podemos mostrar que siempre es posible seleccionar exactamente una carta de cada pila, de modo que las 13 cartas seleccionadas contengan exactamente una carta de cada rango (As, 2, 3, ..., Reina, Rey).

De forma más abstracta, sea G un grupo, y H un subgrupo finito de G. Entonces el teorema del matrimonio puede usarse para demostrar que hay un conjunto T tal que T es una transversal tanto para el conjunto de cosets izquierdos y cosets derechos de H en G.

El teorema del matrimonio se utiliza en las pruebas habituales del hecho de que un Rectángulo Latino (r × n) siempre puede extenderse a un Rectángulo latino ((r+1) × n) cuando r < n, y así, últimamente a un Cuadrado latino.

La condición de matrimonio no se extiende

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

Sea S la familia, A₀ = {1, 2, 3, ...}, A₁ = {1}, A₂ = {2}, ..., A_i = {i}, ...

La condición matrimonial es válida para esta familia infinita, pero no puede construirse transversal.​

El problema más general de seleccionar un elemento (no necesariamente distinto) de cada una de una colección de conjuntos (sin restricción en cuanto al número de conjuntos o el tamaño de los conjuntos) sólo se permite en general si se acepta el axioma de elecció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 que es más sencillo demostrar uno de ellos a partir de otro que a partir de principios elementales. Estos incluyen:

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

En particular,​​ hay pruebas sencillas de las implicaciones del Teorema de Dilworth ⇔Teorema de Hall ⇔Teorema de König–Egerváry ⇔ Teorema de König.

Referencias

• Brualdi, Richard A. (2010), Introductory Combinatorics, Upper Saddle River, NJ: Prentice-Hall/Pearson, ISBN 978-0-13-602040-0 .
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge: Cambridge University Press, ISBN 0-521-45761-0 .
• Dongchen, Jiang; Nipkow, Tobias (2010), «Hall's Marriage Theorem», The Archive of Formal Proofs, ISSN 2150-914X. Computer-checked proof. .
• Hall, Jr., Marshall (1986), Combinatorial Theory (2nd edición), New York: John Wiley &Sons, ISBN 0-471-09138-3 .
• Hall, Philip (1935), «On Representatives of Subsets», J. London Math. Soc. 10 (1): 26-30, doi:10.1112/jlms/s1-10.37.26 .
• Halmos, Paul R. and Vaughan, Herbert E. "The marriage problem". American Journal of Mathematics 72, (1950). 214–215.
• Reichmeider, P.F. (1984), The Equivalence of Some Combinatorial Matching Theorems, Polygonal Publishing House, ISBN 0-936428-09-0 .
• Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd edición), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9 .
• van Lint, J. H.; Wilson, R.M. (1992), A Course in Combinatorics, Cambridge: Cambridge University Press, ISBN 0-521-42260-4 .

Enlaces externos

• Marriage Theorem at cut-the-knot
• Marriage Theorem and Algorithm at cut-the-knot
• Hall's marriage theorem explained intuitively at Lucky's notes.

• Datos: Q536640