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

Improve this question
$\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
    Commented 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$
    – Jukka Suomela
    Commented 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
    Commented Mar 19, 2013 at 15:07

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .