Sobre el tamaño de la intersección de subconjuntos

Question

Quiero demostrar/desmentir la siguiente afirmación: Considere $s+1$ conjuntos arbitrarios $A_i\subseteq \{1,2,\dots,s\}$ , $i\in\{1,2,\dots,s+1\}$ . Siempre existe un conjunto $P\subseteq\{1,2,\dots,s+1\}$ tal que $$\Big|\bigcap_{i\in P}A_i\Big|=|P|-1$$

He probado con un valor pequeño de $s$ (hasta 6) y demostró que tales $P$ siempre existe. Me pregunto si la afirmación anterior se puede demostrar/desmentir para el caso general.

Gracias de antemano.

Answer 1

La afirmación en cuestión es verdadera, y así es como se puede demostrar.

Por comodidad, dejemos que $B=\{b_1,b_2,\dots,b_s\}$ sea el conjunto base sobre el que los conjuntos $A_1,A_2,\dots,A_{s+1}$ se definen (en lugar de $\{1,2,\dots,s\}$ en la declaración original). En primer lugar, hay que tener en cuenta que si $A_i=\varnothing$ para algunos $i$ entonces $P=\{i\}$ es un subconjunto adecuado de índices. Así, podemos considerar sólo el caso en que todos los $A_i$ son no vacíos. Apliquemos la inducción sobre $s$ .

El caso base, $s=1$ es claro: $A_1=A_2=\{b_1\}$ y podemos tomar $P=\{1,2\}$ .

Para aplicar el paso inductivo para cualquier $s>1$ necesitamos el siguiente lema.

Lema. Dejemos que $A_1,A_2,\dots,A_m$ sean subconjuntos no vacíos de algún conjunto finito $B=\{b_1,b_2,\dots,b_n\}$ . Si $\langle b \rangle \stackrel{\text{def}}= \left|\left\{j \mid b \in A_j \right\}\right|$ para cualquier $b \in B$ entonces existe un par $(b_i, A_j)$ tal que $b_i \in A_j$ y $$\frac m n \le \frac {\langle b_i \rangle}{|A_j|}.$$

Prueba del lema. Considere la matriz $X_{n \times m} = (x_{ij})$ , donde $$x_{ij} = \begin{cases} \dfrac 1 {|A_j|}, & b_i \in A_j \\ \phantom{-} 0, & b_i \notin A_j \end{cases}$$ Como cada $A_j$ es no vacía, la suma de los elementos de cada columna de esta matriz es igual a $1$ (es la suma de $|A_j|$ elementos idénticos). Así, la suma de todos los elementos de $X$ es exactamente $m$ .

Por otro lado, contando esta suma por filas, deberíamos obtener el mismo resultado. Sea $i$ sea el índice de la fila que tenga la mayor suma en ella. Esta suma no es menor que la media de las sumas de todas las filas: $$\frac m n \le \sum_{j\,:\,b_i \in A_j} \frac 1 {|A_j|},$$ y, por supuesto, no está vacío, por lo tanto, tomando $j$ con el más pequeño $|A_j|$ entre todos $j$ de tal manera que $b_i \in A_j,$ obtenemos el lado derecho de la última desigualdad limitada por $\frac {\langle b_i \rangle}{|A_j|}$ Justo lo que necesitamos. $\blacksquare$

Volviendo a la demostración del enunciado principal, podemos aplicar el lema a $n = s$ , $m = s + 1$ , encontrando así un elemento $b_i$ y un conjunto $A_j$ que lo contiene, de manera que $$1 < \frac {s+1} s \le \frac {\langle b_i \rangle}{|A_j|}.$$ Esto significa que el número de conjuntos que contienen $b_i$ es estrictamente mayor que el tamaño de uno de ellos, $A_j$ . Sea $t = |A_j|$ . Tenemos un conjunto $A_j$ que contiene $b_i$ y al menos $t$ otros conjuntos que lo contienen, por lo que hay un conjunto de índices $K \!\not\owns j$ tal que $|K|\! = t$ y $\forall k \in K \!\!: b_i\in A_k$ .

El caso $t = 1$ es evidente: $P = \{j\} \cup K$ .

Dejemos que $t>1$ . Desde $t+1 \le s+1 \implies t-1<s$ podemos aplicar la afirmación a $s' = t - 1$ , $B' = A_j \setminus \{b_i\}$ y $\{A'_1,A'_2,\dots,A'_{s'+1}\}=\{A_k \cap B' \mid k \in K\}$ . Esto nos da $P' \subseteq \{1,2,\dots,t\}$ tal que $|\bigcap_{q \in P'}A'_q|=|P'|-1$ . Ahora toma $P = \{j\} \cup P''$ , donde $P''$ es un subconjunto de $K$ correspondiente a $P'$ (es decir $q \in P' \leftrightarrow k \in P'', A'_q = A_k \cap B'$ ), y observe que $$\bigcap_{k \in P}A_k = \{b_i\} \cup \bigcap_{q \in P'}A'_q,$$ donde la unión es disjunta, al igual que en $P = \{j\} \cup P''$ . Así, $$|\bigcap_{k \in P}A_k| = 1 + (|P'| - 1) = |P'| = |P''| = |P| - 1.$$