16
$\begingroup$

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

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

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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