En combinatoria , una familia de Sperner (o sistema de Sperner ; llamado así en honor a Emanuel Sperner ), o clutter , es una familia F de subconjuntos de un conjunto finito E en el que ninguno de los conjuntos contiene a otro. De manera equivalente, una familia de Sperner es una anticadena en la red de inclusión sobre el conjunto potencia de E. A una familia de Sperner también se la denomina a veces sistema independiente o conjunto irredundante .
Las familias de Sperner se cuentan por los números de Dedekind y su tamaño está limitado por el teorema de Sperner y la desigualdad de Lubell-Yamamoto-Meshalkin . También se pueden describir en el lenguaje de los hipergrafos en lugar de las familias de conjuntos, donde se denominan clutters .
El número de diferentes familias de Sperner en un conjunto de n elementos se cuenta mediante los números de Dedekind , los primeros de los cuales son
Aunque se conocen estimaciones asintóticas precisas para valores mayores de n , se desconoce si existe una fórmula exacta que pueda usarse para calcular estos números de manera eficiente.
La colección de todas las familias de Sperner en un conjunto de n elementos se puede organizar como una red distributiva libre , en la que la unión de dos familias de Sperner se obtiene a partir de la unión de las dos familias eliminando conjuntos que son un superconjunto de otro conjunto en la unión.
Los subconjuntos de k elementos de un conjunto de n elementos forman una familia de Sperner, cuyo tamaño se maximiza cuando k = n /2 (o el entero más cercano). El teorema de Sperner establece que estas familias son las familias de Sperner más grandes posibles sobre un conjunto de n elementos. Formalmente, el teorema establece que, para cada familia de Sperner S sobre un conjunto de n elementos,
La desigualdad de Lubell–Yamamoto–Meshalkin proporciona otro límite para el tamaño de una familia de Sperner y se puede utilizar para demostrar el teorema de Sperner. Establece que, si una k denota el número de conjuntos de tamaño k en una familia de Sperner sobre un conjunto de n elementos, entonces
Un desorden es una familia de subconjuntos de un conjunto finito tal que ninguno contiene a otro; es decir, es una familia de Sperner. La diferencia está en las preguntas que se suelen hacer. Los desordenes son una estructura importante en el estudio de la optimización combinatoria.
En un lenguaje más complicado, un desorden es un hipergrafo con la propiedad adicional de que siempre que y (es decir, ninguna arista contiene apropiadamente a otra). Una noción opuesta a un desorden es un complejo simplicial abstracto , donde cada subconjunto de una arista está contenido en el hipergrafo; este es un ideal de orden en el conjunto parcial de subconjuntos de V .
Si es un desorden, entonces el bloqueador de H , denotado por , es el desorden con el conjunto de vértices V y el conjunto de aristas que consiste en todos los conjuntos mínimos de modo que para cada . Se puede demostrar que (Edmonds y Fulkerson 1970), por lo que los bloqueadores nos dan un tipo de dualidad. Definimos como el tamaño de la colección más grande de aristas disjuntas en H y como el tamaño de la arista más pequeña en . Es fácil ver que .
Existe una relación menor en los desordenes que es similar a la relación menor en los grafos. Si es un desorden y , entonces podemos eliminar v para obtener el desorden con un conjunto de vértices y un conjunto de aristas que consisten en todos los que no contienen a v . Contraemos v para obtener el desorden . Estas dos operaciones conmutan, y si J es otro desorden, decimos que J es un menor de H si un desorden isomorfo a J puede obtenerse a partir de H mediante una secuencia de eliminaciones y contracciones.