Extensions of Sperner families on finite sets

Question

Let $V$ be a set consisting of $n$ points, $n\geq 2$.

A Sperner family on $V$ is a set $\{\sigma_1,\sigma_2,\dots,\sigma_m\}$, $m\geq 1$, where each $\sigma_i$, $i=1,2,\dots,m $, is a nonempty subset of $V$, and for any $i\neq j$, $\sigma_i$ does not contain $\sigma_j$.

Given a Sperner family $\{\sigma_1,\sigma_2,\dots,\sigma_m\}$, an extension of it is a new Sperner family $\{\sigma_1,\sigma_2,\dots,\sigma_m,\sigma_{m+1}\}$ obtained by adding a subset $\sigma_{m+1}$ of $V$ to $\{\sigma_1,\sigma_2,\dots,\sigma_m\}$.

Question: Let $R(\sigma_1,\sigma_2,\dots,\sigma_m)$ be the number of extensions of the Sperner family $\{\sigma_1,\sigma_2,\dots,\sigma_m\}$. Are there any methods or formulas to compute $R(\sigma_1,\sigma_2,\dots,\sigma_m)$? Are there any references?

Thanks.

Answer 1

The best I can think of is to use the inclusion-exclusion principle to count the number of sets $\sigma\subset V$ which neither contains nor is contained in any of the $\sigma_i$ for $i=1,\ldots,m$.

Let $V$ be a set of size $n$, and let $I=\{1,\ldots,m\}$ index the sets $\sigma_i$ for $i\in I$. I'll assume $i,i_1,i_2,\ldots\in I$ without further specification.

The number of sets which are not contained in any $\sigma_i$ may be expressed as $$ A = \sum_{J\subset I} (-1)^{|J|} \cdot 2^{|\cap_{j\in J}\sigma_j|} = 2^n - \sum_{i} 2^{|\sigma_i|} + \sum_{i_1<i_2} 2^{|\sigma_{i_1}\cap\sigma_{i_2}|} - \cdots, $$ while the number of sets that contain no $\sigma_i$ is $$ B = \sum_{J\subset I} (-1)^{|J|} \cdot 2^{n-|\cup_{j\in J}\sigma_j|} = 2^n - \sum_{i} 2^{n-|\sigma_i|} + \sum_{i_1<i_2} 2^{n-|\sigma_{i_1}\cup\sigma_{i_2}|} - \cdots. $$ Finally, the $\sigma\subset V$ excluded from both counts $A$ and $B$ are those that contain some $\sigma_i$ and is contained in some $\sigma_j$, which is only possible for $i=j$ and $\sigma=\sigma_i=\sigma_j$: ie, there are $m$ such sets.

So, $2^n-A$ sets are excluded by the first rule, $2^n-B$ are excluded by the second rule, and $m$ sets are excluded by both. Again using the inclusion-exclusion principle, the number of sets not excluded by any of the two are $$ 2^n-(2^n-A)-(2^n-B)+m = A+B-2^n+m. $$

This requires that you sum over all subsets $J\subset I$, so the computational time will be of order $O(2^m\cdot n)$ (the $n$ being the time required to take arbitrary intersections or unions of sets within $V$). It may be possible to speed this up considerably if intersections of a large number of sets tends to be empty and unions similarly tend to fill up all of $V$, but that's a different matter.

Answer 2

If your concern is computational complexity then one can avoid the term $2^m$ which tends to be doubly exponential in $n$. One can solve this problem in time $\text{O}(mn 2^n)$ simply by checking for each subset of $V$ whether or not it is comparable to some element of your Sperner family. (Here the factor $n$ accounts for the cost of such a comparison.)

I do not think that there is a much faster algorithm as $\text{O}(mn 2^n)$, I mean, all known algorithms are exponential. Because it should read at least a matrix of size $n \times m$.

CW Complex, Einar, and others, if you are further interested in the area, I can suggest you a related problem to solve which is (probably) more difficult.

Find the maximum of the number $R(\sigma_1, \ldots)$ when the number of sets, $m$ is fixed (but the sets can be moved). Start with the large values of $m$. Let $M$ denote the largest possible value of $m$: the results of the Sperner theorem ($=$ the largest binomial coefficient of order $n$). The problem is trivial for$$m=M, M-1, M-2, \ldots.$$It starts to be less trivial around $M-n/2\ldots$.