1.8: Teorema de Sperner
- Page ID
- 117124
Los coeficientes binomiales cuentan los subconjuntos de un conjunto dado; vale la pena mirar los propios conjuntos. Primero alguna notación conveniente:
Definición\(\PageIndex{1}\)
Vamos\([n]=\{1,2,3,\ldots,n\}\). Luego\(\displaystyle 2^{[n]}\) denota el conjunto de todos los subconjuntos de\([n]\), y\(\left[\begin{array}{c}n\\k\end{array}\right]\) denota el conjunto de subconjuntos\([n]\) de tamaño\(k\).
Ejemplo\(\PageIndex{1}\)
Vamos\(n=3\). Entonces\[\eqalign{ \left[\begin{array}{c}n\\0\end{array}\right]&=\{\emptyset\}\cr \left[\begin{array}{c}n\\1\end{array}\right]&=\{\{1\},\{2\},\{3\}\}\cr \left[\begin{array}{c}n\\2\end{array}\right]&=\{\{1,2\},\{1,3\},\{2,3\}\}\cr \left[\begin{array}{c}n\\3\end{array}\right]&=\{\{1,2,3\}\}\cr }\nonumber\]
Definición\(\PageIndex{2}\): Chain
Una cadena de\(\displaystyle 2^{[n]}\) entrada es un conjunto de subconjuntos\(\displaystyle 2^{[n]}\) que están ordenados linealmente por inclusión. Una anti-cadena en\(\displaystyle 2^{[n]}\) es un conjunto de subconjuntos de\(\displaystyle 2^{[n]}\) que son incomparables por pares.
Ejemplo\(\PageIndex{2}\)
En\(\displaystyle 2^{[3]}\),\(\displaystyle \{ \emptyset,\{1\},\{1,2,3\} \}\) es una cadena, porque\(\displaystyle \emptyset\subseteq \{1\}\subseteq \{1,2,3\}\). Cada\(\left[\begin{array}{c}n\\k\end{array}\right]\) es una anticadena, tal como es\(\displaystyle \{ \{1\},\{2,3\} \}\). El conjunto no\(\displaystyle \{ \{1\},\{1,3\},\{2,3\} \}\) es una cadena ni una anticadena.
Debido al Teorema 1.4.3 sabemos que entre todas las anticadena de la forma\(\left[\begin{array}{c}n\\k\end{array}\right]\) las más grandes son las “medias”, es decir\(\left[\begin{array}{c}n\\ \lfloor n/2\rfloor\end{array}\right]\) y\(\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]\) (que son iguales si\(n\) es par). Sorprendentemente, estos son los más grandes de todos los anticadena, es decir, estrictamente más grandes que cualquier otra anticadena. Cuando\(n=3\), los anti-cadenas\(\left[\begin{array}{c}3\\1\end{array}\right]\) y\(\left[\begin{array}{c}3\\2\end{array}\right]\) son los únicos anti-cadenas de tamaño 3, y ningún anti-cadena es más grande, como se puede verificar examinando todas las posibilidades.
Antes de probarlo, un poco de notación.
Definición\(\PageIndex{3}\): Permutation
Si\(\sigma\colon A\to A\) es una biyección, entonces\(\sigma\) se llama permutación.
Este uso de la palabra permutación es diferente a nuestro uso anterior, pero los dos están estrechamente relacionados. Considera tal función\(\sigma\colon [n]\to[n]\). Dado que el conjunto\(A\) en este caso es finito, podríamos en principio enumerar cada valor de\(\sigma\):
\[\sigma(1),\sigma(2),\sigma(3),\ldots,\sigma(n).\nonumber \]
Esta es una lista de los números\(\{1,\ldots,n\}\) en algún orden, es decir, esta es una permutación según nuestro uso anterior. Podemos seguir usando la misma palabra para ambas ideas, apoyándonos en el contexto o en una afirmación explícita para indicar a qué nos referimos.
Teorema \(\PageIndex{1}\): Sperner's Theorem
Los únicos anti-cadenas de mayor tamaño son\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\) y\(\left[\begin{array}{c} n \\ \lceil n/2\rceil\end{array}\right]\).
- Prueba
-
Primero mostramos que ningún anticadena es mayor que estos dos. Intentamos particionar\(\displaystyle 2^{[n]}\) en\(k={n\choose \lfloor n/2\rfloor}\) cadenas, es decir, encontrar cadenas para\[\eqalign{ &A_{1,0}\subseteq A_{1,1}\subseteq A_{1,2}\subseteq\cdots\subseteq A_{1,m_1}\cr &A_{2,0}\subseteq A_{2,1}\subseteq A_{2,2}\subseteq\cdots\subseteq A_{2,m_2}\cr &\vdots\cr &A_{k,0}\subseteq A_{k,1}\subseteq A_{k,2}\subseteq\cdots\subseteq A_{k,m_k}\cr }\nonumber\] que cada subconjunto de\([n]\) aparezca exactamente una vez como uno de los\(\displaystyle A_{i,j}\). Si podemos encontrar tal partición, entonces como no pueden estar dos elementos de una anticadena en la misma cadena, ninguna anticadena puede tener más que\(k\) elementos.
Para pequeños valores de\(n\) esto se puede hacer a mano;\(n=3\) porque tenemos\[\eqalign{ &\emptyset\subseteq\{1\}\subseteq\{1,2\}\subseteq\{1,2,3\}\cr &\{2\}\subseteq\{2,3\}\cr &\{3\}\subseteq\{1,3\}\cr }\nonumber\]
Estos pequeños casos forman la base de una inducción. Demostraremos que cualquiera\(\displaystyle 2^{[n]}\) puede dividirse en tales cadenas con dos propiedades adicionales:
- Cada conjunto de una cadena contiene exactamente un elemento más que el siguiente conjunto más pequeño de la cadena.
- La suma de los tamaños del elemento más pequeño y más grande de la cadena es\(n\).
Tenga en cuenta que las cadenas para el caso\(n=3\) tienen ambas propiedades. Las dos propiedades tomadas en conjunto implican que cada cadena “cruza el medio”, es decir, cada cadena contiene un elemento de\(\left[\begin{array}{c}n \\ n/2\end{array}\right]\) si\(n\) es par, y un elemento de ambos\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\) y\(\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]\) si\(n\) es impar. Así, si logramos demostrar que existen tales particiones en cadena, habrá exactamente\(n\choose \lfloor n/2\rfloor\) cadenas.
Para la etapa de inducción, asumimos que hemos particionado\(\displaystyle 2^{[n-1]}\) en tales cadenas, y construimos cadenas para\(\displaystyle 2^{[n]}\).
Primero, para cada cadena\(A_{i,0}\subseteq A_{i,1}\subseteq\cdots\subseteq A_{i,m_i}\) formamos una nueva cadena\(A_{i,0}\subseteq A_{i,1}\subseteq\cdots\subseteq A_{i,m_i}\subseteq A_{i,m_i}\cup \{n\}\). Ya que\(|A_{i,0}|+|A_{i,m_i}|=n-1\)\(|A_{i,0}|+|A_{i,m_i}\cup \{n\}|=n\),, así esta nueva cadena satisface las propiedades (1) y (2).
Además, si\(m_i>0\), formamos una nueva cadena nueva\(A_{i,0}\cup \{n\}\subseteq A_{i,1}\cup \{n\}\subseteq\cdots\subseteq A_{i,m_i-1}\cup \{n\}\). Ahora\[\eqalign{ |A_{i,0}\cup \{n\}|+|A_{i,m_i-1}\cup \{n\}|&= |A_{i,0}|+1+|A_{i,m_i-1}|+1\cr &=|A_{i,0}|+1+|A_{i,m_i}|-1 +1\cr &=n-1+1=n\cr }\nonumber\] así nuevamente las propiedades (1) y (2) están satisfechas.
Debido al primer tipo de cadena, todos los subconjuntos de\([n-1]\) están contenidos exactamente una vez en el nuevo conjunto de cadenas. Además, hemos agregado el elemento\(n\) exactamente una vez a cada subconjunto de\([n-1]\), así que hemos incluido cada subconjunto de\([n]\) contener\(n\) exactamente una vez. Así hemos producido la partición deseada de\(\displaystyle 2^{[n]}\).
Ahora tenemos que demostrar que las únicas anti-cadenas más grandes son\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\) y\(\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]\).
Supongamos que\(A_1,A_2,…,A_m\) es una anticadena; entonces también\(A_1^c,A_2^c,…,A_m^c\) es una anticadena, donde\(A^c\) denota el complemento de\(A\). Por lo tanto, si hay una anticadena que contiene algunos\(A\) con\(|A|>\lceil n/2\rceil\), también hay uno que contiene\(A^c\), y\(|A^c|< \lfloor n/2\rfloor\). Supongamos que algún anti-cadena contiene un conjunto\(A\) con\(|A|< \lfloor n/2\rfloor\). A continuación demostramos que este anticadena no puede ser de tamaño máximo.
Partición\(\displaystyle 2^{[n]}\) como en la primera parte de la prueba. Supongamos que\(A\) es un subconjunto de los elementos de una cadena de uno o dos elementos\(C\), es decir, una cadena que consiste únicamente en un conjunto\(S_1\) de tamaño\(n/2\), si\(n\) es par, o de conjuntos\(S_1\) y\(S_2\) de tamaños\(\lfloor n/2\rfloor\) y\(\lceil n/2\rceil\), con\(A\subseteq S_1\subseteq S_2\), si\(n\) es impar. Entonces ningún miembro de\(C\) está en el anticadena. Por lo tanto, el tamaño más grande posible para un anti-cadena que contiene\(A\) es\({n\choose \lfloor n/2\rfloor}-1\).
Si no\(A\) es un subconjunto de los elementos de una cadena tan corta, ahora demostramos que hay otra partición de cadena de\(\displaystyle 2^{[n]}\) que sí tiene esta propiedad. Tenga en cuenta que en la partición de cadena original debe haber una cadena de longitud 1 o 2,\(C_1\), que consiste en\(S_1\) y posiblemente\(S_2\); si no, cada cadena contendría un conjunto de tamaño\(\lfloor n/2\rfloor -1\), pero no hay suficientes conjuntos de este tipo para dar la vuelta. Supongamos entonces eso\(A=\{x_1,\ldots,x_k\}\) y el set\(S_1\) in\(C_1\) es\(S_1=\{x_1,\ldots,x_q,y_{q+1},\ldots y_l\}\), donde\(0\le q< k\) y\(l>k\).
\(\sigma\)Sea la permutación de\([n]\) tal que\(\sigma(x_{q+i})=y_{q+i}\) y\(\sigma(y_{q+i})=x_{q+i}\), para\(1\le i\le k-q\), y\(\sigma\) fija todos los demás elementos. Ahora para\(U\subseteq [n]\), vamos\(\overline U=\sigma(U)\), y tenga en cuenta que\(U\subseteq V\) si y solo si\(\overline U\subseteq\overline V\). Así, cada cadena en la partición de cadena original se mapea a una cadena. Dado que\(\sigma\) es una bijección, estas nuevas cadenas también forman una partición de\(\displaystyle 2^{[n]}\), con las propiedades adicionales (1) y (2). Por la definición de\(\sigma\),\(A\subseteq\overline S_1\), y\(\{\overline S_1,\overline S_2\}\) es una cadena, digamos\(\overline C_1\). Así, esta nueva partición de cadena tiene la propiedad deseada:\(A\) es un subconjunto de cada elemento de la cadena de 1 o 2 elementos\(\overline C_1\), por lo que no\(A\) está en una anticadena de tamaño máximo.
Por último, tenemos que demostrar que si\(n\) es impar, ningún anticadena de tamaño máximo contiene conjuntos en ambos\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\) y\(\left[\begin{array}{c}n\\ \lceil n/2\rceil\end{array}\right]\). Supongamos que existe tal anticadena, que consiste\(A_{k+1},\ldots,A_l\) en conjuntos en\(\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]\)\(l={n\choose \lceil n/2\rceil}\), dónde y\(B_1,\ldots,B_k\) en\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\). Los conjuntos restantes en\(\left[\begin{array}{c}n\\ \lceil n/2\rceil\end{array}\right]\) son\(A_1,\ldots,A_k\), y los conjuntos restantes en\(\left[\begin{array}{c}n\\ \lfloor n/2\rfloor\end{array}\right]\) son\(B_{k+1},\ldots,B_l\).
Cada conjunto\(B_i\),\(1\le i\le k\), está contenido exactamente en\(\lceil n/2\rceil\) conjuntos en\(\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]\), y todos deben estar entre\(A_1,\ldots,A_k\). En promedio, entonces, cada uno\(A_i\),\(1\le i\le k\), contiene\(\lceil n/2\rceil\) conjuntos entre\(B_1,\ldots,B_k\). Pero cada conjunto\(A_i\),\(1\le i\le k\), contiene exactamente\(\lceil n/2\rceil\) conjuntos en\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\), y así cada uno debe contener exactamente\(\lceil n/2\rceil\) de los conjuntos\(B_1,\ldots,B_k\) y ninguno de los conjuntos\(B_{k+1},\ldots,B_l\).
Dejar\(A_1=A_{j_1}=\{x_1,\ldots,x_r\}\) y\(B_{k+1}=\{x_1,\ldots,x_s,y_{s+1},\ldots,y_{r-1}\}\). Dejar\(B_{i_m}=A_{j_m}\backslash\{x_{s+m}\}\) y\(A_{j_{m+1}}=B_{i_m}\cup\{y_{s+m}\}\), para\(1\le m\le r-s-1\). Obsérvese que por la discusión anterior,\(1\le i_m\le k\) y\(1\le j_m\le k\). Entonces\(A_{j_{r-s}}=\{x_1,\ldots,x_s,y_{s+1},\ldots,y_{r-1},x_r\}\), entonces\(A_{j_{r-s}}\supseteq B_{k+1}\), una contradicción. De ahí que no exista tal anticadena.