Combinatoria de conjuntos

Familias de conjuntos y sus propiedades extremales

Sea $X = \{1, 2, \ldots, n\}$. Una familia $\mathcal{F}$ es una colección (posiblemente con repeticiones, pero en olimpiadas suele ser sin ellas) de subconjuntos de $X$.

Las preguntas extremales más comunes son: ¿cuántos conjuntos puede tener $\mathcal{F}$ si todos los pares se intersectan? ¿Si todos los conjuntos tienen tamaño $k$? ¿Si la familia es una cadena (completamente ordenada por inclusión)?

Estas preguntas, que parecen abstractas, aparecen disfrazadas en problemas de comités, turnos de trabajo, y redes de comunicación en olimpiadas regionales.

Familias intersectantes

Una familia $\mathcal{F}$ es intersectante si $A \cap B \ne \emptyset$ para todo $A, B \in \mathcal{F}$.

¿Cuál es el mayor tamaño de una familia intersectante de subconjuntos de $\{1,\ldots,n\}$?

Observa que para cualquier $A \subseteq X$, no pueden estar ambos $A$ y su complemento $A^c = X \setminus A$ en $\mathcal{F}$ (pues $A \cap A^c = \emptyset$). Los $2^n$ subconjuntos se emparejan en $2^{n-1}$ pares complementarios $\{A, A^c\}$. De cada par, $\mathcal{F}$ puede tomar a lo sumo uno.

Luego $|\mathcal{F}| \le 2^{n-1}$. Esta cota es alcanzada tomando todos los subconjuntos que contienen al elemento 1 (hay exactamente $2^{n-1}$ tales subconjuntos, y cualquier dos de ellos tienen al 1 en común).

El Teorema de Hall: cuándo existe un sistema de representantes

Sea $A_1, A_2, \ldots, A_m$ una familia de subconjuntos finitos de un conjunto $X$. Un sistema de representantes distintos (SDR) es una elección de elementos $a_1 \in A_1, a_2 \in A_2, \ldots, a_m \in A_m$ con todos los $a_i$ distintos.

¿Cuándo existe un SDR? La condición necesaria más obvia es que para cualquier subíndice $I \subseteq \{1,\ldots,m\}$, la unión $\bigcup_{i \in I} A_i$ tenga al menos $|I|$ elementos (pues necesitamos al menos $|I|$ representantes distintos para los conjuntos indexados por $I$).

El Teorema de Hall (1935) afirma que esta condición es también suficiente: existe un SDR si y solo si $\left|\bigcup_{i \in I} A_i\right| \ge |I|$ para todo $I \subseteq \{1, \ldots, m\}$.

Esta condición se llama la condición de Hall o condición del matrimonio (porque fue motivada por el problema de emparejar $m$ hombres con $m$ mujeres donde cada hombre tiene una lista de candidatas aceptables).

Doble conteo aplicado a familias de conjuntos

El doble conteo es una de las técnicas más poderosas en combinatoria de conjuntos. La idea: contar el número de pares $(x, A)$ con $x \in A$ y $A \in \mathcal{F}$ de dos maneras.

Por un lado, para cada $A \in \mathcal{F}$ hay $|A|$ elecciones de $x$: la suma da $\sum_{A \in \mathcal{F}} |A|$.

Por otro lado, para cada $x \in X$ hay $d(x) = |\{A \in \mathcal{F} : x \in A\}|$ (el "grado" de $x$) elecciones de $A$: la suma da $\sum_{x \in X} d(x)$.

Igualar ambas expresiones: $\sum_{A \in \mathcal{F}} |A| = \sum_{x \in X} d(x)$. Esta identidad elemental tiene consecuencias sorprendentes cuando se combina con cotas sobre $|A|$ o $d(x)$.

Por ejemplo: si $\mathcal{F}$ tiene $m$ conjuntos cada uno de tamaño $k$, y $X = \{1,\ldots,n\}$, entonces la suma de los grados es $mk$. Si además los grados son iguales (familia "regular"), cada elemento aparece en exactamente $mk/n$ conjuntos, lo que requiere $n \mid mk$.

Problemas de cobertura y transversales

Un transversal (o "hitting set") de una familia $\mathcal{F}$ es un conjunto $T$ que intersecta a todo $A \in \mathcal{F}$, es decir, $T \cap A \ne \emptyset$ para todo $A \in \mathcal{F}$.

La pregunta extremal: ¿cuál es el menor tamaño posible de un transversal? Esto equivale al problema de cobertura y aparece en olimpiadas bajo el nombre de "¿cuántos elementos bastan para cubrir todos los conjuntos?".

Una cota útil: si $\mathcal{F}$ tiene $m$ conjuntos en un universo $X$ con $|X| = n$, y cada elemento de $X$ cubre a lo sumo $d$ conjuntos, entonces cualquier transversal tiene tamaño al menos $m/d$ (pues cada elemento del transversal "bloquea" a lo sumo $d$ conjuntos).

En muchos problemas regionales, encontrar el tamaño mínimo del transversal es equivalente al problema extremal: se da una cota inferior con el argumento de conteo y una cota superior con la construcción explícita.