El teorema de Sperner , en matemáticas discretas , describe las familias más grandes posibles de conjuntos finitos, ninguno de los cuales contiene ningún otro conjunto en la familia. Es uno de los resultados centrales de la teoría de conjuntos extremos . Lleva el nombre de Emanuel Sperner , quien lo publicó en 1928.
Este resultado a veces se denomina lema de Sperner, pero el nombre " lema de Sperner " también se refiere a un resultado no relacionado en las triangulaciones coloreadas. Para diferenciar los dos resultados, el resultado sobre el tamaño de una familia de Sperner ahora se conoce más comúnmente como teorema de Sperner.
Declaración
Una familia de conjuntos en la que ninguno de los conjuntos es un subconjunto estricto de otro se llama familia Sperner , o antichain de conjuntos, o desorden. Por ejemplo, la familia de subconjuntos de elementos k de un conjunto de elementos n es una familia de Sperner. Ningún conjunto de esta familia puede contener a ninguno de los demás, porque un conjunto contenedor tiene que ser estrictamente más grande que el conjunto que contiene, y en esta familia todos los conjuntos tienen el mismo tamaño. El valor de k que hace que este ejemplo tener tantos conjuntos como sea posible es n / 2 si n es par, o el número entero más próximo a n / 2 si n es impar. Para esta elección, el número de conjuntos en la familia es.
El teorema de Sperner establece que estos ejemplos son las familias de Sperner más grandes posibles en un conjunto de n elementos. Formalmente, el teorema establece que,
- para cada familia Sperner S cuya unión tiene un total de n elementos, y
- la igualdad se cumple si y solo si S consta de todos los subconjuntos de un conjunto de n elementos que tienen tamaño o todo lo que tenga tamaño .
Órdenes parciales
El teorema de Sperner también se puede enunciar en términos de ancho de orden parcial . La familia de todos los subconjuntos de un conjunto de n elementos (su conjunto de potencias ) se puede ordenar parcialmente por inclusión de conjuntos; en este orden parcial, se dice que dos elementos distintos son incomparables cuando ninguno de ellos contiene al otro. El ancho de un pedido parcial es el mayor número de elementos en un antichain , un conjunto de elementos incomparables por pares. Al traducir esta terminología al lenguaje de conjuntos, un antichain es solo una familia Sperner, y el ancho del orden parcial es el número máximo de conjuntos en una familia Sperner. Por tanto, otra forma de enunciar el teorema de Sperner es que el ancho del orden de inclusión en un conjunto de potencias es.
Se dice que un conjunto graduado parcialmente ordenado tiene la propiedad de Sperner cuando uno de sus antichains más grandes está formado por un conjunto de elementos que tienen todos el mismo rango. En esta terminología, el teorema de Sperner establece que el conjunto parcialmente ordenado de todos los subconjuntos de un conjunto finito, parcialmente ordenado por inclusión de conjuntos, tiene la propiedad de Sperner.
Prueba
Hay muchas pruebas del teorema de Sperner, cada una de las cuales conduce a diferentes generalizaciones (véase Anderson (1987)).
La siguiente prueba se debe a Lubell (1966) . Let s k denota el número de k conjuntos-en S . Para todo 0 ≤ k ≤ n ,
y por lo tanto,
Desde S es un anticadena, podemos suma sobre la desigualdad anterior de k = 0 a n y luego aplicar el desigualdad LYM para obtener
lo que significa
Esto completa la prueba de la parte 1.
Para tener igualdad, todas las desigualdades en la prueba anterior deben ser iguales. Desde
si y solo si o llegamos a la conclusión de que la igualdad implica que S consta solo de conjuntos de tamaños o Para incluso n eso concluye la demostración de la parte 2.
Para n impar hay más trabajo por hacer, que omitimos aquí porque es complicado. Véase Anderson (1987), págs. 3-4.
Generalizaciones
Hay varias generalizaciones del teorema de Sperner para subconjuntos de el conjunto parcialmente ordenado de todos los subconjuntos de E .
Sin cadenas largas
Una cadena es una subfamilia que está totalmente ordenado, es decir, (posiblemente después de renumerar). La cadena tiene r + 1 miembros y una longitud r . Un r familia libre de cadena beta (también llamado un r -family ) es una familia de subconjuntos de E que no contiene la cadena de longitud r . Erdős (1945) demostró que el tamaño más grande de una familia libre de cadenas r es la suma de los coeficientes binomiales r más grandes. El caso r = 1 es el teorema de Sperner.
p -composiciones de un conjunto
En el set de p -tuplas de subconjuntos de E , decimos una p -tupla es ≤ otro, Si para cada i = 1,2, ..., p . Nosotros llamamosuna p -composición de E si los conjuntosformar una partición de E . Meshalkin (1963) demostró que el tamaño máximo de un antichain de p -composiciones es el mayor coeficiente p -multinomiales decir, el coeficiente en el que todos los n i son tan casi iguales como sea posible (es decir, difieren como máximo en 1). Meshalkin demostró esto demostrando una desigualdad LYM generalizada.
El caso p = 2 es el teorema de Sperner, porque entonces y los supuestos se reducen a los conjuntos ser una familia Sperner.
Sin cadenas largas en p -composiciones de un conjunto
Beck y Zaslavsky (2002) combinaron los teoremas de Erdös y Meshalkin adaptando la prueba de Meshalkin de su desigualdad LYM generalizada. Demostraron que el tamaño más grande de una familia de p -composiciones tales que los conjuntos en la i -ésima posición de las p -tuplas, ignorando las duplicaciones, están libres de r -chain, para cada(pero no necesariamente para i = p ), no es mayor que la suma delos coeficientes p -multinomiales más grandes.
Analógica de geometría proyectiva
En la geometría proyectiva finita PG ( d , F q ) de dimensión d sobre un campo finito de orden q , seaser la familia de todos los subespacios. Cuando se ordena parcialmente por inclusión de conjuntos, esta familia es una celosía. Rota y Harper (1971) demostraron que el tamaño más grande de un antichain enes el mayor coeficiente gaussiano este es el análogo proyectiva-geometría, o q -analógico , del teorema de Sperner.
Además, demostraron que el tamaño más grande de una familia sin cadenas r enes la suma de los r coeficientes gaussianos más grandes. Su prueba es por un análogo proyectivo de la desigualdad LYM.
Sin largas cadenas en p -composiciones de un espacio proyectivo
Beck y Zaslavsky (2003) obtuvieron una generalización similar a la de Meshalkin del teorema de Rota-Harper. En PG ( d , F q ), una secuencia de Meshalkin de longitud p es una secuenciade subespacios proyectivos tales que ningún subespacio propio de PG ( d , F q ) los contiene a todos y sus dimensiones suman. El teorema es que una familia de secuencias de Meshalkin de longitud p en PG ( d , F q ), tal que los subespacios que aparecen en la posición i de las secuencias no contienen cadenas de longitud r para cada no es más que la suma de la mayor de las cantidades
dónde (en el que asumimos que ) denota el coeficiente p -Gaussiano
y
la segunda función simétrica elemental de los números
Ver también
Referencias
- Anderson, Ian (1987), Combinatoria de conjuntos finitos , Oxford University Press.
- Beck, Matthias; Zaslavsky, Thomas (2002), "Una prueba más corta, simple y sólida de los límites de Meshalkin-Hochberg-Hirsch en antichains por componentes", Journal of Combinatorial Theory, Serie A , 100 (1): 196-199, arXiv : math / 0112068 , doi : 10.1006 / jcta.2002.3295 , MR 1932078.
- Beck, Matthias; Zaslavsky, Thomas (2003), "Un teorema de Meshalkin para geometrías proyectivas", Journal of Combinatorial Theory, Serie A , 102 (2): 433–441, arXiv : math / 0112069 , doi : 10.1016 / S0097-3165 (03) 00049 -9 , MR 1979545.
- Engel, Konrad (1997), teoría de Sperner , Enciclopedia de las matemáticas y sus aplicaciones, 65 , Cambridge: Cambridge University Press, p. x + 417, doi : 10.1017 / CBO9780511574719 , ISBN 0-521-45206-6, Señor 1429390.
- Engel, K. (2001) [1994], "Teorema de Sperner" , Enciclopedia de Matemáticas , EMS Press
- Erdős, P. (1945), "Sobre un lema de Littlewood y Offord" (PDF) , Boletín de la American Mathematical Society , 51 (12): 898–902, doi : 10.1090 / S0002-9904-1945-08454-7 , MR 0014608
- Lubell, D. (1966), "Una breve prueba del lema de Sperner", Journal of Combinatorial Theory , 1 (2): 299, doi : 10.1016 / S0021-9800 (66) 80035-2 , MR 0194348.
- Meshalkin, LD (1963), "Generalización del teorema de Sperner sobre el número de subconjuntos de un conjunto finito (en ruso)", Teoría de la probabilidad y sus aplicaciones , 8 (2): 203-204, doi : 10.1137 / 1108023.
- Rota, Gian-Carlo ; Harper, LH (1971), "Teoría de emparejamiento, una introducción", Avances en probabilidad y temas relacionados, vol. 1 , Nueva York: Dekker, págs. 169–215, MR 0282855.
- Sperner, Emanuel (1928), "Ein Satz über Untermengen einer endlichen Menge", Mathematische Zeitschrift (en alemán), 27 (1): 544–548, doi : 10.1007 / BF01171114 , hdl : 10338.dmlcz / 127405 , JFM 54.0090. 06.
enlaces externos
- Teorema de Sperner en cortar el nudo
- Teorema de Sperner en el wiki de polymath1