Maximum size of antichain-like collection

combinatoricselementary-set-theoryupper-lower-bounds

Lets say we have a set $X$ of $n$ elements and a family $S\subseteq\mathcal{P}(X)$ of subsets such that no set $A\in S$ is the union of some of the others, that is,
$$\forall S'\subseteq S\setminus\{A\}\quad\text{we have}\quad A\ne\bigcup_{B\in S'}B$$
what is the maximum size of such a collection $S$ in terms of $n$? Are there estimates/proofs similar to that of Sperner's theorem?

Thanks!

Best Answer

Andy Loo (Union-Free Families of Subsets, arXiv 2015) has studied this question.

For $n=1,2,3,4$ Loo gives exact maximum values ($1,2,4,7$ nonempty sets, respectively), and for $n=5,\ldots,30$ he gives lower and upper bounds; lower bounds are constructive (explicit set families are given).

For $n=5$ the bounds given are $13$ and $15$. (In fact, my brute-force search, using simple Julia code and 300 seconds of computing, says $13$ is the correct value.)

Note that a Sperner family is always a valid solution (if a set is not a superset of any other set, then it cannot be a union of other sets either). This suggests a strategy of taking a maximal Sperner family and then throwing in some extra small sets.

Examples of maximal families: $$ \begin{array}{lll} 1 & 1 & \{1\} \\ 2 & 2 & \{1\},\{2\} \\ 3 & 4 & \{1\}, \{1,2\}, \{1,3\}, \{2,3\} \\ 4 & 7 & \{1\}, \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\} \\ 5 & 13 & \{1, 5\}, \{2, 3\}, \{2, 4\}, \{3, 4\},\\ && \{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 5\}, \{1, 3, 4\}, \{1, 3, 5\}, \{1, 4, 5\},\\ && \{2, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\} \end{array} $$

Caveat: it seems that "union-free family" more often refers to a family where no set is the union of two other sets. This version was apparently proposed by Erdős.

Related Question