6
$\begingroup$

I have come across the following problem in a technical application. For a given integer $n$, what is the minimal collection of subsets of $\{1,\dots,n\}$ such that all "singleton" sets $\{1\}, \{2\}, \dots, \{n\}$ can be "reconstructed" by set operations (intersection, union, set difference, complement) on those subsets?

For example, with $n = 5$ a possible collection is $S_1 = \{1,2,3\}, S_2 = \{2,3,4\}, S_3 = \{3,4,5\}$, because we can write $$ \{1\} = S_1 \setminus S_2 \\ \{2\} = S_2 \setminus S_3 \\ \{3\} = S_1 \cap S_2 \cap S_3 \\ \{4\} = S_2 \setminus S_1 \\ \{5\} = S_3 \setminus S_2$$

In believe that in general, the sets $S_k = \{k,k+1,\dots,k+c-1\}$, $1\le k \le n-c+1$ and $c = \lceil n / 2 \rceil $ are sufficient, but I am not convinced they are minimal.

I am sure this problem has been studied in some context but I am not a professional mathematician and I don't even know where to look ... Any help appreciated!

$\endgroup$
4
  • $\begingroup$ Any "elementary" set operation would be allowed, I edited to clarify this. $\endgroup$
    – Roland
    May 9, 2015 at 14:57
  • $\begingroup$ To clarify, by "complement", do you mean the operation taking a set $S$ to $\{1,\ldots,n\}\setminus S$? $\endgroup$
    – Tad
    May 10, 2015 at 0:50
  • $\begingroup$ Isn't it just $\lceil\log_2n\rceil$? I.e. working with subsets of $\{0,\dots,n-1\},$ let $S_k$ be the set of numbers whose $k$-th binary digit (from the right) is a $1$? $\endgroup$
    – bof
    May 10, 2015 at 1:14
  • $\begingroup$ Ah, of course! It is indeed logarithmic in n. I did not see this -- then the problem is quite easy. Thanks! $\endgroup$
    – Roland
    May 10, 2015 at 7:42

2 Answers 2

1
$\begingroup$

It turns out you can get by with only $\lceil \lg n\rceil$ sets, where $\lg$ as usual denotes logarithm base $2$. I'll give a construction and prove that it is optimal.

Note that you can construct all singletons with set operations if and only if you can construct all subsets of $[n]=\{1,\ldots,n\}$; it can be useful to think of the latter as an equivalent goal.

For each $i\ge 0$, let $S_i$ be the subset of $[n-1]$ whose binary expansions contain a $1$ in the $i$-th position. (We don't need to include $n$ in any of our sets; it's unnecessary, since the union of the $S_i$'s is $[n-1]$, so we can get the singleton $\{n\}$ by complementing.) So $S_i$ is nonempty precisely when $n-1\ge 2^i$, i.e. $i<\lg n$. Thus the nonempty $S_i$'s are indexed from $0,\ldots \lceil \lg n\rceil-1$.

It's easy to see how to get any singleton $\{k\}$ from the $S_i$'s: look at the binary expansion of $k$; if the $i$-th bit of $k$ is $1$ then $k\in S_i$, otherwise $k\in \bar{S_i}$. Intersecting the appropriate sets for each $i$ leaves the singleton $k$.

The fact that this construction is optimal follows immediately from the fact that the free Boolean algebra generated by $m$ elements contains $2^{2^m}$ elements.

In a little more detail: the collection of all subsets of a given set forms a so-called Boolean algebra, under the correspondence $\wedge\leftrightarrow\cup$, $\vee\leftrightarrow\cap$, and $\neg\leftrightarrow\textrm{complement}$. Roughly, the free Boolean algebra $FA(m)$ on $m$ generators is the "largest" Boolean algebra that can be generated from the generators; the elements of $FA(m)$ are all of the non-equivalent Boolean expressions which can be formed from the given $m$ elements. It is a standard result that $|FA(m)|=2^{2^m}$. Any Boolean algebra $\mathcal{A}$ which can be generated by $m$ elements is a quotient of $FA(m)$, so in particular $\mathcal{A}$ can't have any more than $2^{2^m}$ elements.

To sum up, if $m$ subsets of $[n]$ can generate all subsets via set operations, then we must have $2^{2^m}\ge 2^n$, i.e. $m\ge \lceil\lg n\rceil$. The given construction achieves this bound.

You can turn this into a nice card trick. Have someone think of a card, deal the deck into two piles, ask them which pile the card is in, pick up the cards and repeat 5 more times. Then you can guess their card. The point is that, at the $i$-th stage, the two piles correspond to the sets $S_i$ and $\bar{S_i}$.

$\endgroup$
1
  • $\begingroup$ Very nice! This logarithmic behavior will be very important for me. In retrospect it now seems obvious, but doesn't it always :) $\endgroup$
    – Roland
    May 10, 2015 at 7:44
1
$\begingroup$

We may use Sperner's Theorem to show the bound $${n}\choose{\lfloor n/2\rfloor}$$

Related: https://mathoverflow.net/questions/88038/families-of-subsets-containing-every-singleton-as-an-intersection

$\endgroup$
1
  • $\begingroup$ Thanks! The related post on mathoverflow was very helpful. $\endgroup$
    – Roland
    May 10, 2015 at 7:45

You must log in to answer this question.

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