Este team de expertos luego de muchos días de investigación y recopilación de de datos, hemos dado con la respuesta, nuestro deseo es que te sea útil para tu plan.
Solución:
Lo mejor que se me ocurre es usar el principio de inclusión-exclusión para contar el número de conjuntos $sigmasubset V$ que ni contiene ni está contenido en ninguno de los $sigma_i$ para $i=1,ldots, m$.
Sea $V$ un conjunto de tamaño $n$ y $I=1,ldots,m$ indexe los conjuntos $sigma_i$ para $iin I$. Asumiré $i,i_1,i_2,ldotsin I$ sin más especificaciones.
El número de conjuntos que no están contenidos en ningún $sigma_i$ se puede expresar como $$ A = sum_Jsubset I (-1)^ cdot 2^ = 2^n – sum_i 2^ + sum_{i_1
Por lo tanto, los conjuntos de $2^nA$ están excluidos por la primera regla, los conjuntos de $2^nB$ están excluidos por la segunda regla y los conjuntos de $m$ están excluidos por ambas. Nuevamente, utilizando el principio de inclusión-exclusión, el número de conjuntos no excluidos por ninguno de los dos es $$ 2^n-(2^nA)-(2^nB)+m = A+B-2^n+m. $$
Esto requiere que sume todos los subconjuntos $Jsubset I$, por lo que el tiempo computacional será del orden de $O(2^mcdot n)$ (siendo $n$ el tiempo requerido para tomar intersecciones o uniones arbitrarias de conjuntos dentro de $V$). Puede ser posible acelerar esto considerablemente si las intersecciones de una gran cantidad de conjuntos tienden a estar vacías y las uniones tienden a llenar todo $V$, pero eso es un asunto diferente.
Si su preocupación es la complejidad computacional, entonces puede evitar el término $2^m$ que tiende a ser doblemente exponencial en $n$. Uno puede resolver este problema en el tiempo $textO(mn 2^n)$ simplemente verificando cada subconjunto de $V$ si es o no comparable a algún elemento de su familia Sperner. (Aquí el factor $n$ representa el costo de tal comparación).
No creo que exista un algoritmo mucho más rápido como $textO(mn 2^n)$, es decir, todos los algoritmos conocidos son exponenciales. Porque debería leer al menos una matriz de tamaño $n times m$.
CW Complex, Einar y otros, si está más interesado en el área, puedo sugerirle 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 se pueden mover). Comience con los valores grandes de $m$. Sea $M$ 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 $Mn/2ldots$.
Recuerda que tienes la capacidad de agregar una reseña si diste con el hallazgo.