Familia Sperner

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 .

Números de Dedekind

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

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 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.

Límites en el tamaño de una familia Sperner

Teorema de Sperner

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 próximo). 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,

${\displaystyle |S|\leq {\binom {n}{\lfloor n/2\rfloor }}.}$

Desigualdad LYM

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

${\displaystyle \sum _{k=0}^{n}{\frac {a_{k}}{n \choose k}}\leq 1.}$

Desorden

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 . ${\displaystyle (V,E)}$ ${\displaystyle A\not \subseteq B}$ ${\displaystyle A,B\in E}$ ${\displaystyle A\neq B}$

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 . ${\displaystyle H=(V,E)}$ ${\displaystyle b(H)}$ ${\displaystyle B\subseteq V}$ ${\displaystyle B\cap A\neq \varnothing }$ ${\displaystyle A\in E}$ ${\displaystyle b(b(H))=H}$ ${\displaystyle \nu (H)}$ ${\displaystyle \tau (H)}$ ${\displaystyle b(H)}$ ${\displaystyle \nu (H)\leq \tau (H)}$

Ejemplos

1. Si G es un grafo simple sin bucles, entonces es un desorden (si las aristas se tratan como pares de vértices desordenados) y es la colección de todas las coberturas de vértices mínimas . Aquí es el tamaño de la coincidencia más grande y es el tamaño de la cobertura de vértices más pequeña. El teorema de König establece que, para grafos bipartitos , . Sin embargo, para otros grafos estas dos cantidades pueden diferir. ${\displaystyle H=(V(G),E(G))}$ ${\displaystyle b(H)}$ ${\displaystyle \nu (H)}$ ${\displaystyle \tau (H)}$ ${\displaystyle \nu (H)=\tau (H)}$
2. Sea G un grafo y sea . La colección H de todos los conjuntos de aristas de caminos s - t es un desorden y es la colección de todos los cortes de aristas mínimos que separan s y t . En este caso es el número máximo de caminos s - t disjuntos en aristas , y es el tamaño del corte de arista más pequeño que separa s y t , por lo que el teorema de Menger (versión de conectividad de aristas) afirma que . ${\displaystyle s,t\in V(G)}$ ${\displaystyle b(H)}$ ${\displaystyle \nu (H)}$ ${\displaystyle \tau (H)}$ ${\displaystyle \nu (H)=\tau (H)}$
3. Sea G un grafo conexo y sea H el desorden en que consiste en todos los conjuntos de aristas de árboles de expansión de G . Entonces es la colección de todos los conjuntos de corte de aristas mínimos en G . ${\displaystyle E(G)}$ ${\displaystyle b(H)}$

Menores de edad

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. ${\displaystyle H=(V,E)}$ ${\displaystyle v\in V}$ ${\displaystyle H\setminus v}$ ${\displaystyle V\setminus \{v\}}$ ${\displaystyle A\in E}$ ${\displaystyle H/v=b(b(H)\setminus v)}$

Referencias

• Anderson, Ian (1987), "Teorema de Sperner", Combinatoria de conjuntos finitos , Oxford University Press, págs. 2-4.
• Edmonds, J. ; Fulkerson, DR (1970), "Extremos de cuello de botella", 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 , vol. 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.