What is the maximal number of subsets of a finite set, such that no one is the unions of some other ones? [closed]

Solution 1:

This was stated as an open problem on page 161 of Mitchell, Turan's graph theorem and maximum independent sets in Brandt semigroups, which is pages 151-162 of Isabel M Araujo et al., eds., Proceedings of the Workshop Semigroups and Languages, 2004: "Let $X$ denote the set of subsets of an $n$ element set. What is the maximum cardinality of a subset $Y$ of $X$ with the property that no set in $Y$ is the union of other sets in $Y$?"

There is no further discussion of the problem in the paper.

A pdf of the paper is available here.

Solution 2:

This is only a partial answer: it gives a construction which gives a lower bound and produces exactly all of the maximum solutions for $n \in [0, 4]$. I assume for ease of labelling that $S_n = [1, n]$.

For $n=0$ we take the non-empty subset of $2^{\{\}}$, i.e. $\{\emptyset\}$.

For $n > 0$ we take a maximum solution for $n-1$ and adjoin $\{ s \subseteq S_n : n \in s \wedge |s| = k\}$, choosing $k$ to maximise the result. This means that when $n-1$ is even we take $k-1 = \frac{n-1}{2}$, and when it's odd we take $k-1 = \frac{n-1 \pm 1}{2}$.

The number of sets so produced is a partial sum of $1, \binom{0}{0}, \binom{1}{0}, \binom{2}{1}, \binom{3}{1}, \binom{4}{2}, \binom{5}{2}, \ldots$. This partial sum is in OEIS as A072100.

It's within the realms of brute force to verify whether the value given for $n=5$ is tight or not. For $n=6$ I doubt that it is brute force verifiable.

Addendum Živković, Extremal families containing no two sets and their union, Linear Algebra and its Applications 436.4 (2012) pp845-849 proves a tighter bound:

$$m \ge 2^{\lceil n/2 \rceil - 3} - 2 + \sum_{k=0}^{n-1}\binom{k}{\lceil k/2 \rceil}$$

and references Kleitman (I think Extremal properties of collections of subsets containing no two sets and their union, J. Combin. Theory Ser. A 20 (1976) pp390-392, but the reference is vague and I haven't access to the paper to verify) for

$$m \ge \binom{n}{\lceil n/2 \rceil} + \left\lceil \frac1n \binom{n}{\lceil n/2 \rceil - 1}\right\rceil$$

which is larger for large even $n$.