I have a lemma about antichains that I think should be already known, but I can't find it anywhere. I am looking for a reference to this result that I can use in my paper, so that I don't have to include the proof.


Let $\mathcal{F}$ be an antichain on finite universe $U$, such that there are no $m$ distinct subsets $S\_1, S\_2, \ldots, S\_m \in \mathcal{F}$ such that $|S\_1 \cap S\_2 \ldots \cap S\_m| \geq n$. Then $|\mathcal{F}| \leq 2m|U|^n$.


(The bound can actually be made a little bit sharper, but this is sufficient for my purposes.)


Here is a proof of why this claim is true. We count the number of sets in $\mathcal{F}$ in two steps.


1) Since $\mathcal{F}$ is an antichain, all sets in it are distinct. Hence there are less than $|U|^k$ sets in $F$ of size $k$. Hence the number of sets in $\mathcal{F}$ of size at most $n-1$ is less than $\sum \_{k=0}^{n-1} |U|^k = (U^n - 1)/(U - 1) \leq U^n$.


2) Now we count the number of sets with at least $n$ elements. For each set in $\mathcal{F}$ with at least $n$ elements, select $n$ of its elements arbitrarily and group the sets according to the chosen $n$ elements. If some group contains at least $m$ subsets of $\mathcal{F}$, then the $n$ elements that define the group are in the common intersection of these $m$ subsets, and this violates our assumption. Hence every group has less than $m$ subsets in it. Since there are less than $|U|^n$ different groups, and each group has less than $m$ subsets in it, there are less than $m|U|^n$ subsets in $\mathcal{F}$ of size at least $n$.


Adding the numbers from (1) and (2) yields that the total number of subsets in $\mathcal{F}$ is bounded by $2m|U|^n$.


Can anyone tell me if this is already known and under which name? A reference would be greatly appreciated. Thanks!



Maximum size of antichain if no m subsets have a common intersection of size n
Note that the interesting case is if $n \leq U/2$. Otherwise, your bound is worse than the bound $\binom{U}{\lfloor U/2 \rfloor}$ given by [Sperner's Theorem](http://en.wikipedia.org/wiki/Sperner_family), for the size of *any* antichain on the universe $U$. So assuming that $n \leq U/2$, we can improve the bound in (1) from $U^n$ to $\binom{U}{n-1}$, by the [LYM inequality](http://en.wikipedia.org/wiki/Lubell%E2%80%93Yamamoto%E2%80%93Meshalkin_inequality). And, as Robin noted, the bound in (2) can be improved to $(m-1) \binom{U}{n}$. Adding, (1) and (2) gives the bound $\binom{U}{n-1}+(m-1) \binom{U}{n}$.


