Extensions of Sperner families on finite sets 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.
 A: 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.
A: 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$.
