4
$\begingroup$

I am interested in a family of sets $C$ with the following property:

  • if you take any $k$ distinct subsets $S_1, S_2, \dotsc, S_k \in C$, then $S_1$ is not a subset of $S_2 \cup S_3 \cup \dotso \cup S_k$.

If we have $k = 2$, these are Sperner families.

Has the case $k > 2$ been discussed in the literature?


Edit: A colleague just pointed out that Jukna (2011): "Extremal Combinatorics", Section 8.6 briefly discusses these families and gives some references. The book uses the term union-free families.

However, it seems that none of the results mentioned in the book address the following corner case that I am mainly interested in:

  • The size of the universe $U$ is $O(k)$.
  • The size of the family is "non-trivial" (say, $\Omega(k^2)$).

I would like to know more about positive results for this case (I do not need an explicit construction; an existential result is fine).

It seems that in the literature, the main focus has been on families that are exponentially large in $|U|$, and to construct such families we need to have a fairly large $|U|$ in comparison with $k$. However, I would like to understand the case of a small $|U|$ (and not necessarily exponentially large $|C|$).

$\endgroup$
3
  • 1
    $\begingroup$ Union-free family is a different beast entirely! A family is a k-union-free if union of k set is not equal to a set in a family. You ask about containment, not equality. What are you really interested in? $\endgroup$
    – Boris Bukh
    Mar 19, 2013 at 13:34
  • $\begingroup$ @Boris Bukh: I am interested in containment, not equality. Jukna seems to use the term "union-free family" for this case; see the link in the post. It seems that the term is overloaded, apologies. $\endgroup$ Mar 19, 2013 at 14:08
  • 1
    $\begingroup$ Theorem 8.13 from the book that you linked to seems to answer the question. In your case $n=ck$ and $r=k$, which gives $t=1$ and so $|\mathcal{F}|\leq k+n$. Hence there are no "non-trivial" families. $\endgroup$
    – Boris Bukh
    Mar 19, 2013 at 15:07

1 Answer 1

2
$\begingroup$

For $k=3$ case, there is a result of Kleitman, Shearer and Sturtevant, which gives a bound of $2^{0.7549 n}$ on the size of $C$. In fact they show a similar bound for a $k$-uniform family for any $k$. In a follow-up paper by Alon an explicit set family of exponential size is constructed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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