Complejidad de decidir si una familia es una familia Sperner

Se nos da una familia de subconjuntos de {1, ..., n}. ¿Es posible encontrar un límite inferior no trivial sobre la complejidad de decidir si es una familia Sperner? El límite inferior trivial es y sospecho fuertemente que no es apretado.$\mathcal{F}$$m$$\mathcal{F}$$O(n m)$

Recuerde que un conjunto es una familia Sperner si para e en ; implica que y Y \ X nsubseteq . X Y S X ≠ Y X ⊈ Y Y ⊈ $\mathcal{S}$$X$$Y$$\mathcal{S}$$X \ne Y$$X \nsubseteq Y$$Y \nsubseteq X$

¿No puedes resolver esto mediante la multiplicación de matrices? Deje que los conjuntos sean , S 2 , ... , S m . Tome la matriz A para ser la matriz m × n donde A i j = 1 si j ∈ S i y 0 de lo contrario, y B para ser la m × $S_1$$S_2$$\ldots$$S_m$$A$$m \times n$$A_{ij}=1$$j \in S_i$$B$$m \times n$ matriz donde si j ∉ S i y 0 de lo contrario. Ahora, A B $B_{ij}=1$$j \notin S_i$$AB^T$tiene una entrada si y solo si hay un conjunto de F contenido en otro.$0$$\mathcal{F}$

Entonces, si demuestras un límite inferior de para el caso donde m = θ ( n ) , ha demostrado el mismo límite inferior para la multiplicación de matrices. Este es un famoso problema abierto.$\Omega(n^{2+\epsilon})$$m = \theta(n)$

No he pensado mucho en ello, pero no veo ninguna manera de que pueda probar que este caso particular de multiplicación de matrices es esencialmente tan difícil como el caso general; si realmente necesita un límite inferior, esta parece ser la única esperanza que tiene de probar uno sin resolver el problema de multiplicación de matrices.

En el lado positivo, esto proporciona algoritmos para este problema que son mejores que el algoritmo ingenuo que toma .$\theta(m^2n)$