# Minimum size of the union of sets

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

• 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. – François G. Dorais Aug 22 '15 at 14:44

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

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\}$

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