Sperner ' teorema s y "empujando las sombras alrededor de"

Question

A la cabeza de descuento en cualquier confusión: estoy hablando de la extremal-combinatoria Sperner del teorema, la delimitación de la tamaños de antichains en un valor Booleano de celosía.

Así que la "canónica" a prueba de este teorema parece ser esencialmente Lubell ... formulado en varias maneras diferentes, pero mi favorito es este. Deje $A$ ser un antichain en $2^{[n]}$. Escoge un arbitrario saturados de cadena y de considerar al azar automorphism $\phi$ de la poset. Desde $A$ es un antichain, por lo que es la imagen de $\phi(A)$, y se espera que el número de elementos de a $\phi(A)$ que se encuentran en la distinguida cadena es en la mayoría de los 1. Ahora si $S \subset [n]$ tiene k elementos, a continuación, $\phi$ mapas de $S$ a nuestra distinguida cadena con una probabilidad de $1/\binom{n}{k}$; la linealidad de la expectativa nos da el LYM la desigualdad y Sperner del teorema siguiente.

Esta es una hermosa prueba, pero la lectura de más de la DHJ polymath hilos he escuchado acerca de otro enfoque - al parecer, el enfoque de Sperner mismo -- que una entidad descrita por la maravillosa frase "empujando las sombras a su alrededor." Sugerente como esta frase es que, no estoy realmente seguro de lo que significa: es de suponer que la idea es reemplazar un antichain por otro antichain, al menos, tan grande y cuyos elementos son "más cerca del centro?" Esta idea parece que debería funcionar, pero no puedo hacer que ir a través de, lo que me hace pensar que me estoy perdiendo algo. ¿Alguien sabe los detalles de esta prueba?

Answer 1

Gjergji ya la respuesta, pero quiero agregar una referencia a un libro excelente que contiene más acerca de Sperner del teorema de cualquier otra fuente: "Sperner Teoría" por Konrad Engel. Como sugiere su nombre, el libro contiene muchas pruebas diferentes de la del teorema, pero una gran cantidad de información que es difícil de encontrar en cualquier otro lugar: diversas generalizaciones, un montón de referencias a los resultados que uno nunca podría ni siquiera oír hablar de otra cosa, etc. Es a partir de este libro que he aprendido el argumento de la pregunta.

Answer 2

Deje $\mathcal{B}$ ser una colección de $k$-conjuntos , subconjuntos de un $n$-establecer $S$. Para $k < n$ definir la sombra de $\mathcal{B}$ $$\nabla \mathcal{B}=\{ D\subset S : |D|=k+1,\exists B\in \mathcal{B},B\subset D\}$$ and the shadow of $\mathcal{B}$ que $$\Delta \mathcal{B}=\{ D\subset S : |D|=k-1,\exists B\in \mathcal{B},D\subset B\}$$ Sperner proved the lemma: $|\Delta \mathcal{B}|\geq \frac{k}{n-k+1}|\mathcal{B}|$ for $k > 0$, and $|\nabla \mathcal{B}|\geq \frac{n-k}{k+1}|\mathcal{B}|$ for $k < n$.

Esto implica que si $k\le \frac{1}{2}(n-1)$, $|\nabla \mathcal{B}|\geq |\mathcal{B}|$ e si $k\geq\frac{1}{2}(n+1)$$|\Delta \mathcal{B}|\geq |\mathcal{B}|$. Ahora la prueba de ganancias en los pasos obvios: Supongamos que tenemos una antichain $\mathcal{A}$, y se ha $p_i$ elementos de tamaño $i$. Si $i < \frac{1}{2}(n-1)$, a continuación, a partir de lo anterior, podemos sustituirlos con $p_i$ elementos de tamaño $i+1$. Lo mismo para los elementos de tamaño $i > \frac{1}{2}(n+1)$. Usted termina con una antichain de elementos de tamaño $\lfloor \frac{n}{2}\rfloor$ dándole la prueba de Sperner del teorema.

Realmente disfruté de la Combinatoria de conjuntos finitos por I. Anderson, que trata el Sperner del teorema, LYM, Erdos-Ko-Rado, prueba de Kruskal-Katona etc. El de arriba es solo un boceto, pero allí se pueden encontrar todos los detalles.