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



Minimum size of the union of sets
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}}.
$$


