11
$\begingroup$

Suppose $S$ is a set with $n$ elements. What is the maximal value of $m$ such that there exists a collection $\{A_k\}_{k=1,\dots m}$ of subsets of $S$ such that each $A_i$ is not the union of some other elements of $\{A_k\}_{k=1,\dots m}$?

Is there a elegant formula for this number?

$\endgroup$
  • 10
    $\begingroup$ General piece of advice: you have a sequence of integers. Generate the first few terms, then search for it on OEIS. $\endgroup$ – Theo Bendit May 27 '19 at 8:39
7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ But the papers in the addendum are for families where no member is a union of exactly two other members of the family, whereas the question here allows arbitrary unions of other members of the family. The answer for arbitrary unions will surely be lower than for unions of two. $\endgroup$ – Gerry Myerson May 29 '19 at 4:17
  • 1
    $\begingroup$ @GerryMyerson, Živković's title is misleading. He defines $c_n$ as the maximum size of a 2-union free set (i.e. what the title talks about), $b_n$ as the maximum size of a union free set (what this question is about), references a group of Kleitman papers for some bounds which include, as you say, $b_n \le c_n$, and then focusses solely on $b_n$. $\endgroup$ – Peter Taylor May 29 '19 at 5:50
  • $\begingroup$ For $n=0$, $\{\emptyset\}$ does not work, since $\emptyset$ is the union of the empty collection of other sets in the family. $\endgroup$ – Eric Wofsey Jul 2 '19 at 4:20
  • $\begingroup$ @EricWofsey, I interpret "the union of some other elements" (my emphasis) as requiring a non-empty union, but you make a fair point. That may account for some of the discrepancies between my calculations and the table in Živković's paper. $\endgroup$ – Peter Taylor Jul 2 '19 at 6:56

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