# Maximum size of antichain if no m subsets have a common intersection of size n

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!

• With no extra effort, you could reduce your bound to $m|U|^n$. The argument in 2) gives an upper bound of $(m-1)|U|^n$ which you add to the $|U|^n$ from 1). – Robin Chapman Apr 7 '10 at 12:27
• It seems to me that you are not using the fact that F is an antichain, just that it is not a multi-set. – Tony Huynh Apr 7 '10 at 17:22

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, 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. 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}$.
• Thanks for suggesting the connection to VC dimension; however for my application it's important I get a bound of the form $O(m|U|^n)$ instead of $O(U^{n + \log m}$. – Bart Jansen Apr 12 '10 at 12:15