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

  • $\begingroup$ So you're asking if there's an upper bound of nm ? $\endgroup$ Nov 19, 2010 at 17:04
  • $\begingroup$ 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). $\endgroup$ Nov 19, 2010 at 17:18
  • $\begingroup$ How are the subsets given? "Adjacency matrix" or "edge list"? $\endgroup$ Nov 20, 2010 at 23:22
  • $\begingroup$ The input is an adjacency matrix. $\endgroup$ Nov 21, 2010 at 9:11
  • 9
    $\begingroup$ +1 for trying to get us to solve the matrix multiplication problem without realizing it. :-) $\endgroup$ Nov 21, 2010 at 14:31

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.