9
$\begingroup$

I came accross this combinatorial problem in my computer science research.

You are given a collection of k sets $S_1,...,S_k$ such that for any $i \neq j$, $ \vert S_i \setminus S_j \vert \geq p$ for some fixed integer $p$.

Then what is the minimum size of the union of the sets $S_i$?

$\endgroup$
  • 4
    $\begingroup$ When $p=1$, the requirement says that $\{S_1,\ldots,S_k\}$ is a Sperner Family. Sperner's Theorem then says that if $n = |S_1 \cup \cdots \cup S_k|$ then $k \leq \binom{n}{\lfloor n/2 \rfloor}$, which is optimal. Asymptotically $\binom{n}{\lfloor n/2 \rfloor}$ is $2^n\sqrt{2/\pi n}$, which can be used to get bounds. $\endgroup$ – François G. Dorais Aug 22 '15 at 14:44
3
$\begingroup$

This is lower estimate on the size $n$ of the union proven on the way of standard proof of Sperner's lemma. Or, better to say, it gives an upper bound for $k$ with given $n$. In full generality it is the same problem, of course.

Let $U$ be union of our $k$ sets, $|U|=n$. Consider random permutation $(x_1,\dots,x_n)$ of $U$. Clearly $|S_i|\leq n-p$ for any $i$, else $k\leq 1$. For any $i$ consider the following random event: there exists $T$, $|T|\leq p-1$, sich that $S_i\sqcup T=\{x_1,\dots,x_k\}$ for $k=|S_i|+(p-1)$ and some set $T\subset U\setminus S_i$. Note that no two events may hold simultaneously. Hence sum of probabilities of our events does not exceed $1$. Denote $|S_i|=a$ for a moment (to calculate probability). Then $T$ may be chosen by $\binom{n-a}{p-1}$ ways, hence probability equals $$\binom{n-a}{p-1}/\binom{n}{a+p-1}=\binom{n+p-1}{p-1}/\binom{n+p-1}{a+p-1}.$$ Maximizing by $a$ we see that it is not less than $\binom{n+p-1}{p-1}/\binom{n+p-1} {\lfloor\frac{n+p-1}2\rfloor}$, therefore $$ k\leqslant \frac{\binom{n+p-1} {\lfloor\frac{n+p-1}2\rfloor}}{\binom{n+p-1}{p-1}}. $$

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

This is expanding on my earlier comment. Though it's not a full answer, it does say something about the case $p > 1$.

Given sets $S_1,\ldots,S_k$ which satisfy the condition for a given $p \geq 1$. Let $T_1,\ldots,T_\ell$ list all the sets that can be obtained by deleting exactly $p-1$ elements from one of the sets $S_i$. Thus $$\ell = \binom{|S_1|}{p-1} + \cdots + \binom{|S_k|}{p-1}$$ and observe that $\{T_1,\ldots,T_\ell\}$ is a Sperner family. It follows from Sperner's Theorem that $$\ell \leq \binom{n}{\lfloor n/2 \rfloor},$$ which gives a lower bound on the cardinality $n$ of the union $S_1 \cup \cdots \cup S_k = T_1 \cup \cdots \cup T_\ell$ in terms of $\ell$.

When $p = 1$, this is optimal since the collection of all subsets of $\{1,\ldots,n\}$ with size exactly $\lfloor n/2 \rfloor$ reaches the exact bound given above. When $p > 1$, we get something more crude by observing that we obviously have $|S_i| \geq p$ for every $i$ and thus $$kp \leq \binom{n}{\lfloor n/2 \rfloor}.$$

Finally, here is a simple construction of a large family of subsets of $\{1,\ldots,n\}$ that has the property with $p = 2$. For $z = 0,\ldots,n-1$, consider $$\mathcal{S}_z = \{S \subseteq \{1,\ldots,n\} : |S| = \lfloor n/2 \rfloor, {\textstyle\sum_{x \in S} x \equiv z \pmod{n}}\}.$$ All of these families have the given property for $p = 2$. Since $$|\mathcal{S}_0| + \cdots + |\mathcal{S}_{n-1}| = \binom{n}{\lfloor n/2 \rfloor},$$ at least one of these families satisfies $$|\mathcal{S}_z| \geq \frac{1}{n}\binom{n}{\lfloor n/2 \rfloor} = \binom{n-1}{\lceil (n-1)/2 \rceil}.$$

To summarize, if $\nu(k,p)$ denotes the minimum size of the union of a family of $k$ sets with the given property for a given $p$, then:

  • $\nu(k,1) = \min\left\{n : k \leq \binom{n}{\lfloor n/2 \rfloor}\right\}$
  • $\nu(k,p) \geq \min\left\{n : kp \leq \binom{n}{\lfloor n/2 \rfloor}\right\}$
  • $\nu(k,2) \leq \min\left\{n+1 : k \leq \binom{n}{\lfloor n/2 \rfloor}\right\}$
| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

When all sets have the same cardinality, this is the subject of Corradi's lemma

https://books.google.co.il/books?id=OyrOOrTmlvwC&pg=PA24&lpg=PA24&dq=corradi%2527s+lemma&source=bl&ots=6GViNzUn4c&sig=Oqfl27w5eal8p1P405PnpAi1Oc4&hl=en&sa=X&ei=ZEiBUavOFMnWPPiJgZAD#v=onepage&q=corradi%2527s%2520lemma&f=false

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ But it is far from being optimal in many interesting cases. $\endgroup$ – Fedor Petrov Aug 22 '15 at 18:43

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.