El teorema de Lovasz-Stein

Dada una familia$\mathcal{F}$de subconjuntos de algún conjunto finito$X$, su número de portada de$\mathcal{F}$,$\text{Cov}(\mathcal{F})$, es el número mínimo de miembros de$\mathcal{F}$cuya unión cubre todos los puntos de$X$.

Teorema 2.16. Si cada miembro de$\mathcal{F}$tiene como máximo$a$elementos y cada punto$x\in X$pertenece al menos$v$de los conjuntos en$\mathcal{F}$, entonces

$$\text{Cov}(\mathcal{F})\leq \dfrac{|\mathcal{F}|}{v}(1+\ln a).$$

Prueba. Dejar$|X|=N, |\mathcal{F}|=M$y considerar el$N\times M$ $0$-$1$matriz$A=(a_{x,i})$, dónde$a_{x,i}=1$si y si$x\in X$pertenece a la$i$-th miembro de$\mathcal{F}$. Por nuestra suposición, cada fila de$A$tiene al menos$v$unos y cada columna como máximo$a$unos. Contando dos veces, tenemos que$Nv\leq Ma$, o equivalente,

$$\frac{M}{v}\geq \frac{N}{a} \quad \quad (*).$$ Nuestro objetivo es mostrar que$A$debe contener un$N\times K$submatriz$C$sin todo-$0$filas y tal que $$K\leq (M/v)(1+\ln a).$$

Describimos un procedimiento constructivo para producir la submatriz deseada.$C$. Dejar$A_a=A$y definir$A'_a$ser cualquier conjunto máximo de columnas de$A_a$cuyos soportes son disjuntos por pares y cuyas columnas tienen cada una$a$unos. Dejar$K_a=|A'_a|$. Descartar de$A_a$las columnas de$A'_a$y cualquier fila con un uno en$A'_a$. Nos quedamos con un$k_a\times (M-K_a)$matriz$A_{a-1}$, dónde$k_a=N-aK_a$. Claramente, las columnas de$A_{a-1}$tener como máximo$a-1$(de hecho, de lo contrario, dicha columna podría agregarse al conjunto previamente descartado, contradiciendo su maximalidad). Seguimos haciendo para$A_{a-1}$lo que le hicimos$A_a$. Eso es lo que definimos$A'_{a-1}$ser cualquier conjunto máximo de columnas de$A_{a-1}$, cuyos soportes son disjuntos por pares y cuyas columnas tienen cada una$a-1$unos. Dejar$K_{a-1}=|A'_{a-1}|$, luego descartar de$A_{a-1}$las columnas de$A'_{a-1}$y cualquier fila con un uno en$A'_{a-1}$conseguir un$k_{a-1}\times (M-K_a-K_{a-1})$matriz$A_{a-2}$, dónde$k_{a-1}=N-aK_a-(a-1)K_{a-1}$.

El proceso terminará después de como máximo$a$pasos. La unión de las columnas de los conjuntos descartados forman la submatriz deseada$C$con$K=\sum \limits_{i=1}^a K_i$. El primer paso del algoritmo da$k_a=N-aK_a$, que reescribimos, estableciendo$k_{a+1}=N$, como

$$K_a=\frac{k_{a+1}-k_a}{a}.$$ Análogamente, $$K_i=\frac{k_{i+1}-k_i}{i} \ \text{for} \ i=1,\dots,a.$$ Ahora derivamos un límite superior para$k_i$contando el número de unos en$A_{i-1}$de dos maneras: cada fila de$A_{i-1}$contiene al menos$v$unos, y cada columna como máximo$i-1$unos, por lo tanto $$vk_i\leq (i-1)(M-K_a-\dots-K_{i+1})\leq (i-1)M,$$ o equivalente $$k_i\leq \frac{(i-1)M}{v}.$$

Entonces,

$$K=\sum\limits_{i=1}^a K_i=\sum\limits_{i=1}^a \frac{k_{i+1}-k_i}{i}=$$ $$=\frac{k_{a+1}}{a}+\frac{k_{a}}{a(a-1)}+\frac{k_{a-1}}{(a-1)(a-2)}+\dots+\frac{k_{2}}{2\cdot 1}-k_1\leq$$ $$\leq \frac{N}{a}+\frac{M}{v}(\frac{1}{a}+\dots+\frac{1}{2})\leq \frac{N}{a}+\frac{M}{v}\ln a.$$ La última desigualdad aquí sigue porque$1+\frac{1}{2}+\dots+\frac{1}{n}$es el$n$-ésimo número armónico que se sabe que se encuentra entre$\ln n$y$\ln n+1$. Juntos con$(*)$, esto produce$K\leq (M/v)(1+\ln a)$, como se desee.

Esta prueba está copiada del libro de Stasys Jukna "Combinatoria extrema" y me gustaría aclarar algunos momentos de esta prueba.

Mis preguntas:

1. Estoy un poco confundido con el procedimiento y cómo funciona. En el primer paso necesitamos encontrar cualquier conjunto máximo de columnas que tengan soportes disjuntos por pares y cada uno de ellos tenga$a$unos. ¿Qué pasa si no hay columnas con$a$¿unos?

2. Intuitivamente puedo entender por qué este proceso termina después de a lo sumo$a$pasos, pero alguien puede explicarlo de una manera rigurosa, por favor?

3. ¿Cómo tomamos la unión de las columnas de los conjuntos descartados si esas columnas tienen diferente tamaño?

4. si tomamos$C$ser la unión de las columnas de los conjuntos descartados. ¿Por qué cualquier fila de$C$tiene$1$entre sus entradas?

Estaría muy agradecido si alguien puede explicar esas preguntas! ¡Muchas gracias por su atencion!