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

Question

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!

Answer 1

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

Answer 2

I think that this follows from the "Sauer-Shelah Lemma". You can see this for an introduction: http://ljsavage.wharton.upenn.edu/~steele/Rants/ShatteredSets.html or rather the first page here and Theorem 1 is the lemma I am referring to.

From your condition it follows that the VC dimension is bounded by n+log m which gives an upper bound of approximately U^{n+log m}, close to yours (without using the antichain property whose redundancy was already noted by Tony).