Extensiones de las familias de Sperner en conjuntos finitos

Question

Dejemos que $V$ sea un conjunto formado por $n$ puntos, $n\geq 2$ .

Una familia Sperner en $V$ es un conjunto $\{\sigma_1,\sigma_2,\dots,\sigma_m\}$ , $m\geq 1$ donde cada $\sigma_i$ , $i=1,2,\dots,m $ es un subconjunto no vacío de $V$ y para cualquier $i\neq j$ , $\sigma_i$ no contiene $\sigma_j$ .

Dada una familia Sperner $\{\sigma_1,\sigma_2,\dots,\sigma_m\}$ una extensión de la misma es una nueva familia Sperner $\{\sigma_1,\sigma_2,\dots,\sigma_m,\sigma_{m+1}\}$ que se obtiene añadiendo un subconjunto $\sigma_{m+1}$ de $V$ a $\{\sigma_1,\sigma_2,\dots,\sigma_m\}$ .

Pregunta: Dejemos que $R(\sigma_1,\sigma_2,\dots,\sigma_m)$ sea el número de extensiones de la familia Sperner $\{\sigma_1,\sigma_2,\dots,\sigma_m\}$ . ¿Existen métodos o fórmulas para calcular $R(\sigma_1,\sigma_2,\dots,\sigma_m)$ ? ¿Existen referencias?

Gracias.

Answer 1

Lo mejor que se me ocurre es utilizar el principio de inclusión-exclusión para contar el número de conjuntos $\sigma\subset V$ que no contiene ni está contenido en ninguno de los $\sigma_i$ para $i=1,\ldots,m$ .

Dejemos que $V$ sea un conjunto de tamaño $n$ y que $I=\{1,\ldots,m\}$ indexar los conjuntos $\sigma_i$ para $i\in I$ . Voy a asumir $i,i_1,i_2,\ldots\in I$ sin más especificaciones.

El número de conjuntos que no están contenidos en ningún $\sigma_i$ puede expresarse como $$ A = \sum_{J\subset I} (-1)^{|J|} \cdot 2^{|\cap_{j\in J}\sigma_j|} = 2^n - \sum_{i} 2^{|\sigma_i|} + \sum_{i_1<i_2} 2^{|\sigma_{i_1}\cap\sigma_{i_2}|} - \cdots, $$ mientras que el número de conjuntos que no contienen $\sigma_i$ es $$ B = \sum_{J\subset I} (-1)^{|J|} \cdot 2^{n-|\cup_{j\in J}\sigma_j|} = 2^n - \sum_{i} 2^{n-|\sigma_i|} + \sum_{i_1<i_2} 2^{n-|\sigma_{i_1}\cup\sigma_{i_2}|} - \cdots. $$ Por último, el $\sigma\subset V$ excluido de ambos recuentos $A$ y $B$ son los que contienen alguna $\sigma_i$ y está contenida en algunos $\sigma_j$ que sólo es posible para $i=j$ y $\sigma=\sigma_i=\sigma_j$ : es decir, hay $m$ tales conjuntos.

Así que, $2^n-A$ Los conjuntos están excluidos por la primera regla, $2^n-B$ están excluidos por la segunda regla, y $m$ Los conjuntos son excluidos por ambos. Utilizando de nuevo el principio de inclusión-exclusión, el número de conjuntos no excluidos por ninguno de los dos es $$ 2^n-(2^n-A)-(2^n-B)+m = A+B-2^n+m. $$

Esto requiere que se sume sobre todos los subconjuntos $J\subset I$ por lo que el tiempo de cálculo será del orden de $O(2^m\cdot n)$ (el $n$ siendo el tiempo requerido para tomar intersecciones o uniones arbitrarias de conjuntos dentro de $V$ ). Puede ser posible acelerar esto considerablemente si las intersecciones de un gran número de conjuntos tienden a estar vacías y las uniones tienden igualmente a llenar todo $V$ pero eso es otra cosa.

Answer 2

Si su preocupación es la complejidad computacional, entonces se puede evitar el término $2^m$ que tiende a ser doblemente exponencial en $n$ . Uno puede resolver este problema a tiempo $\text{O}(mn 2^n)$ simplemente comprobando para cada subconjunto de $V$ si es o no comparable con alguna elemento de su familia Sperner. (Aquí el factor $n$ cuentas por el coste de dicha comparación).

No creo que haya un algoritmo mucho más rápido como $\text{O}(mn 2^n)$ , I es decir, todos los algoritmos conocidos son exponenciales. Porque debería leer al menos una matriz de tamaño $n \times m$ .

Complejo CW, Einar, y otros, si están más interesados en el área, puedo sugerirles un problema relacionado para resolver que es (probablemente) más difícil.

Encuentra el máximo del número $R(\sigma_1, \ldots)$ cuando el número de conjuntos, $m$ es fijo (pero los conjuntos pueden moverse). Comience con los valores grandes de $m$ . Sea $M$ denotan el mayor valor posible de $m$ Los resultados del teorema de Sperner ( $=$ el mayor coeficiente binomial de orden $n$ ). El problema es trivial para $$m=M, M-1, M-2, \ldots.$$ Empieza a ser menos trivial alrededor de $M-n/2\ldots$ .