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$
  • $\begingroup$ Any "elementary" set operation would be allowed, I edited to clarify this. $\endgroup$ – Roland May 9 '15 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 '15 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 '15 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 '15 at 7:42
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$
  • $\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 '15 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$
  • $\begingroup$ Thanks! The related post on mathoverflow was very helpful. $\endgroup$ – Roland May 10 '15 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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