Set system containing no chain of length $3$

108 Views Asked by At

Let $n$ be even and let $\mathcal{A}\subset\mathcal{P}(n)$ be a set system that contains no chain of length three. Prove that \begin{equation}|\mathcal{A}|\le{n\choose{n/2}}+{n\choose{n/2-1}}.\end{equation}

My thoughts are that this reminds me of Sperner's Lemma, but this is a larger number than Sperner would give. I suppose we could try and use induction. For $n=2$ this is immediate. But actually applying an induction seems tricky. I don't know how to apply the condition that there is no chain of length three.

1

There are 1 best solutions below

0
On

Proving that the maximum is attained is easy: choose the subsets of $n/2$ and $n/2-1$ elements, they cannot contain a length $3$ chain, as in a chain the size increases by at least $1$ on each set.

But proving this is the maximum is not easy. It looks true, because the subsets of $n/2$ and $n/2-1$ elements, in the inclusion lattice with $n$ even, are actually the $2$ largest ranks, for ranks being defined upon the number of elements. (It could also be $n/2$ and $n/2+1$, the result is the same). But not all lattices have the property that no union of $k$ antichains is larger than the union of the $k$ largest rank levels: it is called the $k$-Sperner property, see Wikipedia's page on Sperner property of graded posets.

In fact the inclusion lattice is a graded poset (for rank being the number of elements), and it has the $k$-Sperner property for any $k$, which is called the strong Sperner property. I.e. the OP can be extended further, stating that if $\mathcal{A}\subset\mathcal{P}(n)$ contains no chain of length $k+1$, then $|\mathcal A| \le$ the sum of the $k$ largest $n\choose i$. And this is true for $k$ odd as well as even.

This was proven by Erdös in 1945, in the following paper, "On a lemma of Littlewood and Offord", see theorem 5:
https://projecteuclid.org/journalArticle/Download?urlId=bams%2F1183507531.