familia sperner

En combinatoria , una familia Sperner (o sistema Sperner ; llamado así 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 a otro. De manera equivalente, una familia Sperner es una anticadena en la red de inclusión sobre el conjunto de potencias de E. A una familia Sperner también se le llama a veces sistema independiente o conjunto irredundante .

Las familias de Sperner se cuentan mediante 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 hipergrafías en lugar de familias de conjuntos, donde se les llama desordenes .

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 el OEIS ).

Aunque se conocen estimaciones asintóticas precisas para valores más grandes 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 de la unión de las dos familias eliminando conjuntos que son un superconjunto de otro conjunto en el Unión.

Límites del tamaño de una familia Sperner

teorema de sperner

Los k -subconjuntos de elementos de un conjunto de n -elementos forman una familia de Sperner, cuyo tamaño se maximiza cuando k = n /2 (o el número entero más cercano a él). 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,

${\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 puede utilizarse para demostrar el teorema de Sperner. Afirma que, si a _k ​​denota el número de conjuntos de tamaño k en una familia Sperner sobre un conjunto de n elementos, entonces

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

Desordenes

Un desorden es una familia de subconjuntos de un conjunto finito tal que ninguno contiene a otro; es decir, es una familia Sperner. La diferencia está en las preguntas que normalmente se hacen. 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 cuando y (es decir, ningún borde contiene propiamente otro. Una noción opuesta a un desorden es un complejo simplicial abstracto , donde cada subconjunto de un borde está contenido en el hipergrafo; este es un ideal de orden en el conjunto 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 bordes que consta de todos los conjuntos mínimos, de modo que para cada . Se puede demostrar que (Edmonds y Fulkerson 1970), 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 eso . ${\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 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 coberturas mínimas de vértices . Aquí está el tamaño de la coincidencia más grande y el tamaño de la cubierta de vértice más pequeña. El teorema de Kőnig establece que, para gráficos bipartitos , . Sin embargo, para otros gráficos 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 una gráfica y sea . La colección H de todos los conjuntos de bordes de caminos s - t es un desorden y es la colección de todos los cortes de bordes mínimos que separan s y t . En este caso, es el número máximo de caminos s - t de borde disjunto , y es el tamaño del corte de borde más pequeño que separa s y t , por lo que el teorema de Menger (versión de conectividad de borde) 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 gráfico conexo y sea H el desorden que consta de todos los conjuntos de bordes de árboles generadores de G . Luego está la colección de todos los conjuntos de cortes de borde mínimos en G . ${\displaystyle E(G)}$ ${\displaystyle b(H)}$

Menores

Existe una relación menor en los desordenes que es similar a la relación menor en los gráficos. Si es un desorden y , entonces podemos eliminar v para obtener el desorden con un conjunto de vértices y un conjunto de bordes que consta de todos los que no contienen v . Contraemos v para eliminar el desorden . Estas dos operaciones conmutan, y si J es otro desorden, decimos que J es menor de H si se puede obtener un desorden isomorfo a J 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..
• 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 , 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.