# Complexity of deciding whether a family is a Sperner familiy

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$.

• So you're asking if there's an upper bound of nm ? – Suresh Venkat Nov 19 '10 at 17:04
• Basically yes. Actually, I'd like to prove that there isn't any algorithm that can succeed (in the worst case) with complexity O(mn). – Anthony Leverrier Nov 19 '10 at 17:18
• How are the subsets given? "Adjacency matrix" or "edge list"? – Yuval Filmus Nov 20 '10 at 23:22
• The input is an adjacency matrix. – Anthony Leverrier Nov 21 '10 at 9:11
• +1 for trying to get us to solve the matrix multiplication problem without realizing it. :-) – Peter Shor Nov 21 '10 at 14:31

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.
On the plus side, this gives algorithms for this problem that are better than the naive algorithm that takes $\theta(m^2n)$.