# 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 showing how the LYM inequality simplifies some of the proof and sharpens the bound. I wasn't looking for a sharper bound but for a reference of the original claim (or sharper) but from the absence of references to such a bound I presume there is no well-known theorem from which this directly follows; I will simply have to include the short proof in my paper. – Bart Jansen Apr 12 '10 at 12:17
No problem. I think the proof is nice and short, so yes, there should be no problem to just include it. Cheers. – Tony Huynh Apr 12 '10 at 13:57

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).

-
The link doesn't appear to state the Sauer-Shelah Lemma nor does it appear to define Vapnik-Chervonenkis dimension. – François G. Dorais Apr 7 '10 at 23:45
I added another link, which was available from the first one, but it is more direct and gives less history. – domotorp Apr 8 '10 at 6:30
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