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$?
 A: 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
A: 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\}$

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