Aplicaciones olímpicas de Hall y König

Reconocer cuándo usar Hall vs. König

Los teoremas de Hall y König son herramientas diferentes para preguntas diferentes:

Teorema de Hall responde: "¿Existe una asignación/matching/SDR?" La estrategia es verificar la condición $|N(S)| \geq |S|$ para todos los subconjuntos $S$, frecuentemente usando doble conteo o argumentos de simetría.

Teorema de König responde: "¿Cuántos elementos son necesarios para cubrir todos los vínculos?" o equivalentemente "¿Cuán grande puede ser un conjunto sin vínculos internos?" La estrategia es construir el grafo bipartito y aplicar $\nu = \tau$.

Señales de Hall en un problema: "Demuestra que es posible asignar/emparejar/elegir..." con condiciones de compatibilidad entre dos grupos. El problema pide existencia.

Señales de König en un problema: "Encuentra el mínimo número de filas/columnas/elementos necesarios para cubrir..." o "¿Cuál es el máximo subconjunto sin intersecciones/colisiones?" El problema pide una cantidad óptima.

Casos combinados: Algunos problemas requieren Hall para mostrar que un matching existe y König para cuantificar exactamente cuánto se puede lograr. En otros, el enunciado reformula König como un problema de existencia (Hall disfrazado).

Hall en problemas de sistemas de conjuntos

Tipo 1 — Transversales: Una familia $A_1, \ldots, A_k$ de subconjuntos de un conjunto $S$ tiene un SDR. El enfoque estándar: verificar Hall por doble conteo. Si $|\bigcup_{i \in I} A_i| \geq |I|$ no es obvio, intentar encontrar una violación (un $I$ donde $\bigcup_{i \in I} A_i$ es "pequeño") o probar Hall por contradicción.

Tipo 2 — Partición en transversales: Si $A_1, \ldots, A_n$ son subconjuntos de $S$ con $|A_i| = k$ para todo $i$, y $|S| = n$, ¿cuándo se pueden encontrar $k$ SDR disjuntos que particionen las aristas del grafo bipartito correspondiente? Por el corolario de König (descomposición en matchings), la respuesta es cuando el grafo bipartito es $k$-regular.

Ejemplo (Cono Sur 2009, estilo): Sea $A_1, \ldots, A_n \subseteq \{1,\ldots,n\}$ con $|A_i| \geq n/2$ para todo $i$. Demuestra que existe un SDR. Solución: Para cualquier $I \subseteq \{1,\ldots,n\}$, queremos $|\bigcup_{i \in I} A_i| \geq |I|$. Si $|I| \leq n/2$, entonces basta un solo $A_i$ para dar $|A_i| \geq n/2 \geq |I|$, luego $|\bigcup A_i| \geq n/2 \geq |I|$. Si $|I| > n/2$, entonces $|\bigcup_{i \in I} A_i|$... supongamos por contradicción que $|\bigcup_{i \in I} A_i| < |I|$. Cada $A_i$ con $i \in I$ tiene al menos $n/2$ elementos, todos en un conjunto de tamaño $< |I| \leq n$. En particular hay un elemento $j$ que está en al menos $\frac{|I| \cdot (n/2)}{|I|} = n/2$ conjuntos $A_i$, lo cual no da contradicción directamente. Un argumento más cuidadoso usando el complement size: $|\bigcup A_i| = n - |\bigcap \overline{A_i}|$, y $|\overline{A_i}| \leq n/2$, luego... La condición $|\bigcup A_i| \geq n - |\overline{A_i}| \geq n/2 \geq |I|/\cdot$ (estimación directa cuando $|I| \leq n$). $\square$

Tip olímpico: Cuando los conjuntos son "grandes" (tamaño $\geq n/2$), la condición de Hall se verifica fácilmente. Cuando son "pequeños", se necesita la estructura específica del problema.

König en tableros: problemas de cubrimiento

Tipo estándar: Dado un conjunto de celdas marcadas en un tablero, ¿cuántas líneas (filas o columnas) son necesarias para cubrirlas? Por König: el mínimo de líneas = el máximo de celdas marcadas sin dos en la misma línea.

Problema tipo Iberoamericana: Hay $n$ filas y $n$ columnas. Se marcan celdas tal que ninguna fila ni columna tiene más de $k$ celdas marcadas. Demuestra que se pueden cubrir todas las celdas marcadas con a lo sumo $k$ filas más $k$ columnas... usando König y el grado máximo.

Ejemplo resuelto: En un tablero $5 \times 5$ se marcan 12 celdas tal que ninguna fila ni columna tiene más de 3 marcas. ¿Cuántas líneas (filas o columnas) son suficientes para cubrir todas las celdas? Por König, el mínimo de líneas es igual al máximo matching sin repetición de fila/columna. Como cada fila tiene a lo sumo 3 celdas y el grafo bipartito tiene grado máximo 3, el matching máximo puede ser a lo sumo $\min(5,5) = 5$. Por König, el mínimo de líneas es $\leq 5$. (La cota exacta depende de la configuración específica.)

Tablero de ajedrez y dominós: El tablero $8 \times 8$ sin dos esquinas opuestas no se puede cubrir con $31$ dominós. La prueba clásica usa coloración, que equivale a mostrar que el grafo bipartito no tiene matching perfecto (la condición de Hall falla: hay más escaques de un color que del otro). Esta es una aplicación del contrapositivo de Hall.

Formulación general: Un tablero rectangular con $m$ filas y $n$ columnas (con $m \leq n$) con ciertas celdas marcadas admite un conjunto de $m$ celdas marcadas sin dos en la misma fila ni en la misma columna si y solo si la condición de Hall se cumple para el grafo bipartito de filas y columnas.

Coloración de grafos bipartitos y Hall

Teorema: Un grafo bipartito $k$-regular es $k$-coloreable por aristas (sus aristas se pueden colorear con $k$ colores de modo que aristas incidentes tengan colores distintos). Equivalentemente, sus aristas se pueden particionar en $k$ matchings perfectos.

Demostración: Por el corolario de Hall (un grafo bipartito $k$-regular tiene matching perfecto), encontramos un matching perfecto $M_1$. El grafo restante $G \setminus M_1$ es $(k-1)$-regular (bipartito). Por inducción, encontramos matchings perfectos $M_1, M_2, \ldots, M_k$ que particionan todas las aristas. $\square$

Aplicación: $n$ equipos juegan un torneo round-robin (cada par juega exactamente una vez). ¿Cuántas rondas son necesarias si en cada ronda cada equipo juega a lo sumo un partido? El grafo de partidos es $K_n$ (grafo completo) que no es bipartito, pero si $n$ es par, $K_n$ es $(n-1)$-regular y se puede descomponer en $n-1$ matchings perfectos (rondas), cada uno con $n/2$ partidos. Si $n$ es impar, se necesitan $n$ rondas con algunos equipos libres.

La condición de Hall y el teorema de Vizing: El teorema de Vizing dice que el índice cromático (número mínimo de colores para colorear aristas) de cualquier grafo simple es $\Delta$ o $\Delta + 1$, donde $\Delta$ es el grado máximo. Para grafos bipartitos, el teorema de König implica que el índice cromático es exactamente $\Delta$ (el caso "Clase 1"). Esto generaliza el resultado anterior para grafos regulares.

En olimpiadas: Problemas de la forma "¿cuántas rondas necesita un torneo?" o "¿cómo dividir una competencia en etapas?" suelen reducirse a coloración de aristas, que para grafos bipartitos se resuelve con Hall y el resultado anterior.

Hall disfrazado: problemas sin grafo explícito

Muchos problemas olímpicos aplican el teorema de Hall sin mencionar grafos explícitamente. Reconocer la estructura bipartita subyacente es la habilidad clave.

Patrón 1 — Matrices con restricciones: Se tiene una matriz $n \times n$ de ceros y unos. ¿Existe una selección de $n$ unos, uno por fila y uno por columna? Esto es un matching perfecto en el grafo bipartito de filas y columnas, y aplica Hall.

Patrón 2 — Sucesiones y subconjuntos: Dada una sucesión $a_1, \ldots, a_n$ y subconjuntos $S_1, \ldots, S_n$ de $\{1,\ldots,n\}$, ¿existe una permutación $\sigma$ tal que $a_{\sigma(i)} \in S_i$ para todo $i$? Esto es un SDR, y aplica Hall.

Patrón 3 — Selecciones evitando colisiones: "Elige un representante de cada grupo tal que no haya dos representantes que compartan cierta propiedad." Si la propiedad define una partición del universo, esto es Hall.

Ejemplo olímpico (Iberoamericana 2016, estilo): Sea $A_1, \ldots, A_n$ una familia de subconjuntos de $\{1,\ldots,2n\}$, cada uno de tamaño $n+1$. Demuestra que existe un SDR. Solución: Para cualquier $I \subseteq [n]$, la unión $\bigcup_{i \in I} A_i$ es un subconjunto de $\{1,\ldots,2n\}$. Si $|I| \leq n$, queremos mostrar que $|\bigcup_{i \in I} A_i| \geq |I|$. Esto es trivial pues $|A_i| = n+1 \geq 1$ para todo $i$, así que la unión tiene al menos 1 elemento. Pero necesitamos $|\bigcup_{i \in I} A_i| \geq |I|$. Por el tamaño: $|\bigcup_{i \in I} A_i| \leq 2n$, y queremos $\geq |I| \leq n$. ¿Es siempre así? Sí: por la desigualdad de unión, $|\bigcup A_i| \geq \max_i |A_i| = n+1 > n \geq |I|$. La condición de Hall se cumple trivialmente cuando $|I| \leq n$. Para $|I| = n$, $|\bigcup A_i| \leq 2n = 2 \cdot |I|$, pero necesitamos $\geq n = |I|$, que se satisface pues $|\bigcup A_i| \geq n+1 > n$. Luego existe SDR. $\square$

Lección clave: Cuando los conjuntos son grandes respecto al universo, la condición de Hall se verifica con cotas simples sobre el tamaño de la unión.

Combinando Hall-König con PIE y coloración

Los mejores problemas de la Iberoamericana y el Cono Sur combinan varias herramientas. Aquí algunos patrones de combinación:

Hall + PIE: Cuenta las SDR con el PIE (cada "mala" SDR es aquella donde algún $A_i$ elige un elemento "prohibido"), y usa Hall para garantizar que al menos una SDR existe antes de contar. El PIE luego da el número exacto usando las intersecciones.

König + coloración: Encuentra el índice cromático de un grafo bipartito usando la descomposición en matchings (König) y luego cuenta coloraciones usando el polinomio cromático o el PIE sobre colores prohibidos.

Hall + inducción: Demuestra que todo grafo bipartito $k$-regular tiene $k$ matchings perfectos disjuntos por inducción en $k$, usando Hall en cada paso para garantizar la existencia del siguiente matching.

Hall sobre posets: Usa el teorema de Dilworth (que se demuestra con König) para descomponer un poset en cadenas, y luego aplica Hall para encontrar un SDR de representantes de las cadenas.

Estrategia de olimpiada: En un problema de existencia combinatoria con dos grupos naturales de objetos y condiciones de compatibilidad entre ellos, el primer instinto debe ser construir el grafo bipartito y buscar un matching. Si la existencia es la pregunta, probar Hall. Si la cantidad óptima es la pregunta, probar König. Si el problema mezcla conteo y existencia, combinar con PIE.

Resumen del capítulo: Los grafos bipartitos y los matchings son la infraestructura de muchos problemas de asignación, cobertura y representación en combinatoria. El teorema de Hall da la condición de existencia perfecta; el teorema de König da la dualidad min-max entre matchings y coberturas. Con estas herramientas más el PIE del capítulo anterior y la teoría de grafos de los capítulos 1 y 2, se está bien equipado para los problemas de combinatoria de la Iberoamericana y el Cono Sur.