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!

  • $\begingroup$ 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). $\endgroup$ – Robin Chapman Apr 7 '10 at 12:27
  • $\begingroup$ It seems to me that you are not using the fact that F is an antichain, just that it is not a multi-set. $\endgroup$ – 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}$.

  • $\begingroup$ 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. $\endgroup$ – Bart Jansen Apr 12 '10 at 12:17
  • $\begingroup$ No problem. I think the proof is nice and short, so yes, there should be no problem to just include it. Cheers. $\endgroup$ – 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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.