El teorema de Hall: cuándo existe un matching perfecto

Grafos bipartitos y matchings: definiciones fundamentales

Un grafo bipartito es un grafo $G = (V, E)$ cuyo conjunto de vértices se puede particionar en dos conjuntos $X$ e $Y$ (las partes) de modo que toda arista conecta un vértice de $X$ con uno de $Y$. Escribimos $G = (X \cup Y, E)$.

Los ejemplos más naturales: tableros de ajedrez (escaques blancos vs. negros), conjuntos de personas y tareas (personas vs. trabajos), conjuntos de elementos y subconjuntos (elementos vs. subconjuntos), o dos grupos en un problema de asignación.

Un matching (o emparejamiento) en $G$ es un conjunto $M \subseteq E$ de aristas tal que ningún vértice aparece en más de una arista de $M$. Informalmente, es una "asignación parcial" donde cada persona recibe a lo sumo una tarea y cada tarea es asignada a lo sumo a una persona.

Un matching perfecto (desde $X$ hasta $Y$) es un matching $M$ tal que todo vértice de $X$ aparece en alguna arista de $M$. Si $|X| = |Y|$, esto significa que $M$ es una biyección entre $X$ e $Y$.

Para cada $S \subseteq X$, la vecindad $N(S)$ es el conjunto de vértices de $Y$ adyacentes a al menos un vértice de $S$: $N(S) = \{y \in Y : \exists\, x \in S,\, xy \in E\}$. La condición $|N(S)| \geq |S|$ es natural: si queremos asignar a cada $x \in S$ un vecino distinto en $Y$, necesitamos al menos $|S|$ vecinos disponibles.

El teorema de Hall

El teorema de Hall (Philip Hall, 1935) da una condición necesaria y suficiente para la existencia de un matching perfecto desde $X$.

Condición de Hall: Decimos que $G$ satisface la condición de Hall si para todo subconjunto $S \subseteq X$ se tiene $|N(S)| \geq |S|$.

Demostración de la necesidad: Si existe un matching perfecto $M$, entonces para todo $S \subseteq X$, cada vértice de $S$ está emparejado con un vértice distinto de $N(S)$, luego $|N(S)| \geq |S|$.

Demostración de la suficiencia (por inducción en $|X|$): El caso $|X| = 1$ es inmediato (si $x$ tiene al menos un vecino, podemos emparejarlo). Para el paso inductivo, supongamos que $|X| = n \geq 2$ y que la condición de Hall se cumple.

Caso 1 — condición estricta: Si $|N(S)| > |S|$ para todo $S \subsetneq X$ (la condición es estricta para todos los subconjuntos propios), elige cualquier arista $xy \in E$, elimina $x$ de $X$ e $y$ de $Y$. El grafo restante $G'$ sigue satisfaciendo la condición de Hall: para cualquier $S \subseteq X \setminus \{x\}$, la vecindad en $G'$ es $N_{G'}(S) \supseteq N_G(S) \setminus \{y\}$, que tiene tamaño $\geq |N_G(S)| - 1 \geq |S|+1-1 = |S|$. Por hipótesis inductiva, $G'$ tiene un matching perfecto $M'$, y $M' \cup \{xy\}$ es matching perfecto de $G$.

Caso 2 — condición justa: Si existe $S \subsetneq X$ con $|N(S)| = |S|$ (un conjunto "ajustado"), emparejar primero $S$ con $N(S)$ por inducción (la condición de Hall se cumple en el subgrafo inducido), y luego emparejar $X \setminus S$ con $Y \setminus N(S)$: la condición de Hall para $X \setminus S$ en $Y \setminus N(S)$ se puede verificar usando que el conjunto $S$ era ajustado. $\square$

Sistemas de representantes distintos (SDR)

La versión "de conjuntos" del teorema de Hall es el teorema de los representantes distintos: dada una familia de conjuntos finitos $A_1, A_2, \ldots, A_n$ (no necesariamente disjuntos), existe un sistema de representantes distintos (SDR) —una elección de elementos $a_1 \in A_1, a_2 \in A_2, \ldots, a_n \in A_n$ con los $a_i$ todos distintos— si y solo si para todo $I \subseteq \{1,\ldots,n\}$ se tiene $\left|\bigcup_{i \in I} A_i\right| \geq |I|$.

La equivalencia con el teorema de Hall es inmediata: construir el grafo bipartito $G$ con $X = \{A_1,\ldots,A_n\}$ (un vértice por conjunto), $Y = \bigcup_i A_i$ (los elementos), y aristas $(A_i, y)$ cuando $y \in A_i$. Un SDR corresponde exactamente a un matching perfecto desde $X$.

Ejemplo básico: ¿Existe un SDR para $A_1 = \{1,2\}$, $A_2 = \{2,3\}$, $A_3 = \{1,3\}$? Verificamos la condición: $|A_1| = 2 \geq 1$, $|A_2| = 2 \geq 1$, $|A_3| = 2 \geq 1$, $|A_1 \cup A_2| = 3 \geq 2$, $|A_1 \cup A_3| = 3 \geq 2$, $|A_2 \cup A_3| = 3 \geq 2$, $|A_1 \cup A_2 \cup A_3| = 3 = 3$. La condición se cumple (el caso $|I|=3$ es justo). SDR posible: $a_1 = 1, a_2 = 2, a_3 = 3$.

Ejemplo donde falla: $A_1 = \{1,2\}$, $A_2 = \{1,2\}$, $A_3 = \{3\}$. Tomando $I = \{1,2\}$: $|A_1 \cup A_2| = |\{1,2\}| = 2 = |I|$, la condición se cumple. Tomando $I = \{1,2,3\}$: $|A_1 \cup A_2 \cup A_3| = 3 = |I|$. La condición se cumple y existe SDR: $a_1 = 1, a_2 = 2, a_3 = 3$ (o $a_1 = 2, a_2 = 1, a_3 = 3$).

Ejemplo donde falla la condición: $A_1 = \{1\}$, $A_2 = \{1\}$. Para $I = \{1,2\}$: $|A_1 \cup A_2| = 1 < 2$. La condición de Hall falla y no existe SDR (ambos conjuntos solo tienen al elemento 1, pero no podemos elegirlo dos veces).

Hall en grafos regulares y doble conteo

Uno de los corolarios más elegantes del teorema de Hall se aplica a grafos bipartitos **$k$-regulares** (donde todo vértice tiene exactamente $k$ vecinos, con $k \geq 1$):

Corolario: Todo grafo bipartito $k$-regular ($k \geq 1$) tiene un matching perfecto.

Demostración: Verificamos la condición de Hall. Sea $S \subseteq X$. Las aristas entre $S$ y $N(S)$ son: desde $S$ hay $k|S|$ aristas (cada vértice de $S$ tiene $k$ vecinos), y todas caen en $N(S)$. Desde $N(S)$, cada vértice tiene $k$ vecinos en $X$, así que hay a lo sumo $k|N(S)|$ aristas entre $N(S)$ y $X$. Entonces $k|S| \leq k|N(S)|$, lo que implica $|N(S)| \geq |S|$. $\square$

Este argumento de doble conteo (contar las aristas entre $S$ y $N(S)$ de dos maneras) es una técnica estándar para verificar la condición de Hall en problemas olímpicos.

Aplicación en tableros: El tablero de ajedrez estándar $8 \times 8$ tiene partes $X$ = escaques blancos, $Y$ = escaques negros. Si eliminamos un escaque blanco y uno negro, ¿se puede cubrir el tablero con $31$ dominós? La respuesta depende de cuáles escaques se eliminan, y el teorema de Hall (o un argumento de coloración) lo resuelve.

Matching perfecto en grafos bipartitos regulares y el teorema de Birkhoff: Toda matriz doblemente estocástica (con entradas no negativas y sumas de fila y columna iguales a 1) es una combinación convexa de matrices de permutación. La demostración usa repetidamente el teorema de Hall para encontrar permutaciones (matchings perfectos) que dan soporte a la matriz.

Defecto de Hall y el teorema generalizado

Cuando la condición de Hall no se cumple, ¿qué tan grande puede ser un matching? El defecto de Hall de $G$ es $\text{def}(G) = \max_{S \subseteq X}(|S| - |N(S)|)$. El teorema generalizado de Hall afirma:

El matching máximo desde $X$ tiene tamaño $|X| - \text{def}(G)$.

En otras palabras, el "cuello de botella" es el subconjunto $S$ que maximiza $|S| - |N(S)|$: exactamente $\text{def}(G)$ vértices de $X$ quedarán sin emparejar en cualquier matching óptimo.

Demostración: Sea $d = \text{def}(G)$. Añadimos $d$ vértices "ficticios" a $Y$, cada uno adyacente a todos los vértices de $X$. El nuevo grafo $G'$ satisface la condición de Hall: para todo $S \subseteq X$, $|N_{G'}(S)| \geq |N_G(S)| + d \geq |S| - (|S| - |N_G(S)|) + d \cdot 0 + d \geq |S|$ (usando $d = \max|S|-|N_G(S)|$). Entonces $G'$ tiene un matching perfecto de tamaño $|X|$, y al quitar los $d$ vértices ficticios obtenemos un matching de tamaño $|X| - d$ en $G$.

Uso en olimpiadas: El defecto de Hall aparece en problemas de la forma "muestra que se pueden asignar al menos $k$ de las $n$ tareas". Se calcula $d = \max_S(|S|-|N(S)|)$ y se concluye que el matching óptimo tiene tamaño $\geq n - d$.

El teorema de König (próxima lección) complementa este resultado dando el tamaño del matching máximo en términos de la cobertura mínima de vértices.

Problema trabajado: asignación de trabajos

Problema: Hay $n$ personas y $n$ trabajos. Cada persona puede realizar exactamente $k$ de los $n$ trabajos ($k$ fijo), y cada trabajo puede ser realizado por exactamente $k$ personas. Demuestra que existe una asignación donde cada persona realiza un trabajo distinto.

Solución: Modelamos el problema con un grafo bipartito $k$-regular $G$ donde $X$ son las personas, $Y$ son los trabajos, y hay arista $(x, y)$ si la persona $x$ puede realizar el trabajo $y$. La condición "$k$ trabajos por persona y $k$ personas por trabajo" significa que $G$ es $k$-regular.

Por el corolario del teorema de Hall para grafos regulares, $G$ tiene un matching perfecto. Este matching es exactamente la asignación pedida: cada persona recibe un trabajo (distinto) que puede realizar. $\square$

Variante: Si en lugar de que cada persona realice exactamente $k$ trabajos, simplemente pedimos que cada persona pueda realizar al menos $k$ trabajos, la regularidad no se garantiza. En ese caso, debemos verificar la condición de Hall directamente o usar el doble conteo adaptado.

Reflexión: La demostración usa la regularidad de manera esencial. El corolario falla si el grafo no es regular: por ejemplo, con 3 personas y 3 trabajos donde las personas 1 y 2 solo pueden hacer el trabajo 1, la condición de Hall falla.