En combinatoria , una familia Sperner (o sistema Sperner ; nombrado en honor a Emanuel Sperner ), o desorden , es una familia F de subconjuntos de un conjunto finito E en el que ninguno de los conjuntos contiene otro. De manera equivalente, una familia Sperner es un anticadena en la inclusión de celosía sobre el conjunto potencia de E . Una familia Sperner también se denomina a veces un sistema independiente o un 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 pueden describirse en el lenguaje de los hipergráficos en lugar de establecer familias, donde se les llama desorden .
Números de Dedekind
El número de familias de Sperner diferentes en un conjunto de n elementos se cuenta mediante los números de Dedekind , los primeros de los cuales son
- 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (secuencia A000372 en la OEIS ).
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 celosía distributiva libre , en la que la unión de dos familias de Sperner se obtiene de la unión de las dos familias eliminando conjuntos que son un superconjunto de otro conjunto en el Unión.
Limita al tamaño de una familia Sperner
Teorema de sperner
Los subconjuntos de elementos k de un conjunto de elementos n forman una familia de Sperner, cuyo tamaño se maximiza cuando k = n / 2 (o el número entero más cercano). El teorema de Sperner establece que estas familias 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 sobre un conjunto de n elementos,
Desigualdad LYM
La desigualdad de Lubell-Yamamoto-Meshalkin proporciona otro límite en el tamaño de una familia de Sperner y puede usarse para probar el teorema de Sperner. Establece que, si a k denota el número de conjuntos de tamaño k en una familia de Sperner sobre un conjunto de n elementos, entonces
Desorden
Un desorden es una familia de subconjuntos de un conjunto finito tal que ninguno contiene a ningún otro; es decir, es una familia Sperner. La diferencia está en las preguntas que se hacen habitualmente. Los desorden son una estructura importante en el estudio de la optimización combinatoria.
(En un lenguaje más complicado, un desorden es un hipergráfico con la propiedad añadida de que cuando sea y (es decir, ningún borde contiene correctamente a otro. Una noción opuesta a un desorden es un complejo simplicial abstracto , donde cada subconjunto de un borde está contenido en el hipergráfico; este es un ideal de orden en el posconjunto 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 bordes formado por todos los conjuntos mínimos así que eso para cada . Se puede demostrar que( Edmonds & Fulkerson 1970 ), entonces los bloqueadores nos dan un tipo de dualidad. Definimostener el tamaño de la colección más grande de bordes disjuntos en H y ser del tamaño del borde más pequeño en . Es fácil ver eso.
Ejemplos de
- Si G es un gráfico simple sin bucles, entonces es un desorden (si los bordes se tratan como pares de vértices desordenados) y es la colección de todas las cubiertas de vértices mínimas . Aquí es el tamaño de la coincidencia más grande y es el tamaño de la cubierta de vértice más pequeña. El teorema de Kőnig establece que, para grafos bipartitos ,. Sin embargo, para otros gráficos, estas dos cantidades pueden diferir.
- Sea G una gráfica y sea. La colección H de todos los conjuntos de bordes de caminos s - t es un desorden yes la colección de todos los cortes de borde mínimos que separan s y t . En este casoes el número máximo de trayectorias s - t de borde disjunto , yes el tamaño de la más pequeña de borde corte de separación s y t , de modo de teorema de Menger (versión borde-conectividad) afirma que.
- Sea G un gráfico conectado y sea H el desorden enque consiste en todo borde conjuntos de árboles de expansión de G . Luegoes la colección de todas cutsets borde mínimos en G .
Menores
Existe una relación menor en los desorden que es similar a la relación menor en los gráficos. Si es un desorden y , luego podemos eliminar v para obtener el desorden con conjunto de vértices y juego de bordes que consta de todos que no contienen v . Nosotros contratamos v para obtener el desorden. Estas dos operaciones conmutan, y si J es otro desorden, decimos que J es menor de H si un desorden isomorfo a J puede obtenerse de H mediante una secuencia de deleciones y contracciones.
Referencias
- Anderson, Ian (1987), "Teorema de Sperner", Combinatoria de conjuntos finitos , Oxford University Press, págs. 2-4.
- Edmonds, J .; Fulkerson, DR (1970), "Bottleneck extrema", Journal of Combinatorial Theory , 8 (3): 299-306, doi : 10.1016 / S0021-9800 (70) 80083-7.
- Knuth, Donald E. (2005), "Borrador de la sección 7.2.1.6: Generación de todos los árboles" , El arte de la programación informática , IV , págs. 17-19.
- Sperner, Emanuel (1928), "Ein Satz über Untermengen einer endlichen Menge" (PDF) , Mathematische Zeitschrift (en alemán), 27 (1): 544–548, doi : 10.1007 / BF01171114 , JFM 54.0090.06.