<p>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. </p>

<p>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.</p>

<p>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.</p>

<p>On the plus side, this gives algorithms for this problem that are better than the naive algorithm that takes $\theta(m^2n)$.</p>

CC BY-SA 2.5
2010-11-21T14:13:52.263Z
2010-11-21T14:26:09.750Z
2010-11-21T14:26:09.750Z
Peter Shor 
<p>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.</p>

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

CC BY-SA 2.5
2010-11-19T17:04:21.913Z
So you're asking if there's an **upper bound** of nm ?
Suresh Venkat
CC BY-SA 2.5
2010-11-19T17:18:48.353Z
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
CC BY-SA 2.5
2010-11-20T23:22:59.860Z
How are the subsets given? "Adjacency matrix" or "edge list"?
Yuval Filmus
CC BY-SA 2.5
2010-11-21T09:11:38.670Z
The input is an adjacency matrix.
Anthony Leverrier
CC BY-SA 2.5
2010-11-21T14:31:09.370Z
+1 for trying to get us to solve the matrix multiplication problem without realizing it. :-)
Peter Shor 
<ds.algorithms><co.combinatorics>
Complexity of deciding whether a family is a Sperner familiy
Anthony Leverrier
# Complexity of deciding whether a family is a Sperner familiy

(Asked by: username_0 on 2010-11-19)

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

**Tags:** ds.algorithms, co.combinatorics

> **Comments:**
> **username_1**: So you're asking if there's an **upper bound** of nm ?  
> **username_0**: 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).  
> **username_2**: How are the subsets given? "Adjacency matrix" or "edge list"?  
> **username_0**: The input is an adjacency matrix.  
> **username_3**: +1 for trying to get us to solve the matrix multiplication problem without realizing it. :-)  

---

## 1 answers

### Answer by username_3 on 2010-11-21. Score: 17 | Accepted answer

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


---

