una desigualdad de cardinalidad

Question

Denote $E=\{1,2,...,n\}$ para algún número entero positivo $n\geq 2$ . Denote \begin{equation*} E_k=\{\Omega\subset E||\Omega|=k\},\quad k=1,2,...,n. \end{equation*} Aquí, $|\cdot|$ denota la cardinalidad de un conjunto. Sea $S_k\subset E_k$ para $k=1,2,...,n$ . Supongamos que para cualquier $\Omega\in S_k$ con $k<n$ y para cualquier $i\in E\setminus \Omega$ , se mantiene $$(\Omega\cup\{i\})\in S_{k+1}.$$

Supongo que $\frac{|S_k|}{|E_k|}\leq\frac{|S_{k+1}|}{|E_{k+1}|}$ para cualquier $k<n$ ? ¿Es correcta mi propuesta? ¿Puede alguien ayudarme a demostrarla o dar algún contraejemplo?

Answer 1

El resultado es una modificación de un comentario de @OlivierRoche

De cada $\Omega \in S_k$ podemos construir $n-k$ elementos de $S_{k+1}$ adjuntando algunos $i \in E \setminus \Omega$ .

Seamos más explícitos. Consideremos todas las tripletas de la forma $(\Omega, i, \Omega \cup \{i\})$ donde $\Omega \in S_k, i \in E \setminus \Omega$ .

El número de estos tripletes $= |S_k| (n - k)$ porque para cada $\Omega \in S_k$ podemos elegir $i$ en $(n-k)$ diferentes maneras.

En cada una de estas tripletas, el último miembro $(\Omega \cup \{i\}) \in S_{k+1}$ por la propiedad dada en el OP.

Ahora, considere algunos $\Lambda \in S_{k+1}$ . ¿En cuántos trillizos puede $\Lambda$ ¿aparece (como el último miembro, obviamente)? Afirmo que $\Lambda$ puede aparecer como máximo en $k+1$ tales trillizos. Esto se debe a que el $i$ en el triplete debe ser $\in \Lambda$ y sólo hay $k+1$ tales opciones para $i$ . (A esto me refería cuando dije originalmente " $\Lambda$ sólo puede construirse a partir de unos $\Omega$ en un máximo de $k+1$ diferentes maneras").

Dejemos que $N(\Lambda)$ sea el número de veces que $\Lambda$ aparece en estos tripletes, es decir, el número de formas de construir $\Lambda$ utilizando algunos $\Omega \in S_k$ . Por lo tanto, tenemos $N(\Lambda) \le k+1$ .

Sumando todo $\Lambda \in S_{k+1}$ que tenemos:

$$\sum_{\Lambda \in S_{k+1}} N(\Lambda) = \text{no. of triplets} = |S_k| (n-k)$$

Tenga en cuenta que la suma sólo tiene que cubrir $\Lambda \in S_{k+1}$ Porque sólo este tipo de $\Lambda$ puede aparecer como tercer miembro en estas tripletas, por la propiedad dada del OP. Es decir, no necesitamos incluir ningún $\Lambda' \in E_{k+1} \setminus S_{k+1}$ porque tales $\Lambda'$ no puede aparecer en estas tripletas (es decir, no puede construirse a partir de algún $\Omega \in S_k$ ).

Mientras tanto, en base a $N(\Lambda) \le k+1$ también tenemos:

$$\sum_{\Lambda \in S_{k+1}} N(\Lambda) \le \sum_{\Lambda \in S_{k+1}} (k+1) = |S_{k+1}| (k+1)$$

$$|S_{k+1}| \ge {n-k \over k+1} |S_k|$$

El resultado se deduce fácilmente de $|E_k| = {n \choose k}$ expandiéndose en factoriales:

$${|E_{k+1}| \over |E_k|} = {{n \choose k+1} \over {n \choose k}} = {n! \over (k+1)! (n-k-1)!}{k! (n-k)! \over n!} = {n-k \over k+1} \le {|S_{k+1}| \over |S_k|}$$