Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
We are given a family $\mathcal{F}$ of $m$ subsets of {1, ...,n}. Is it possible to find a non-trivial lower bound on the complexity of deciding whether $\mathcal{F}$ is a Sperner family ? The trivial lower bound is $O(n m)$ and I strongly suspect that it is not tight.
Recall that a set $\mathcal{S}$ is a Sperner family if for $X$ and $Y$ in $\mathcal{S}$; $X \ne Y$ implies that $X \nsubseteq Y$ and $Y \nsubseteq X$.
Can't you solve this by matrix multiplication? Let the sets be $S_1$, $S_2$, $\ldots$, $S_m$. Take matrix $A$ to be the $m \times n$ matrix where $A_{ij}=1$ if $j \in S_i$ and 0 otherwise, and $B$ to be the $m \times n$ matrix where $B_{ij}=1$ if $j \notin S_i$ and 0 otherwise. Now, $AB^T$ has a $0$ entry if and only if there is one set of $\mathcal{F}$ contained in another.
So if you prove a lower bound of $\Omega(n^{2+\epsilon})$ for the case where $m = \theta(n)$, you have proven the same lower bound for matrix multiplication. This is a famous open problem.
I haven't thought much about it, but I don't see any way you could prove that this particular case of matrix multiplication is essentially as hard as the general case; if you really need a lower bound, this would seem to be the only hope you have of proving one without solving the matrix multiplication problem.
On the plus side, this gives algorithms for this problem that are better than the naive algorithm that takes $\theta(m^2n)$.
