# maximum size of a $k$-intersecting antichain of $$What is the maximum size of an antichain of [n]:=\{1,2,3,\dots,n\} (say \mathcal{A}) such that \mid A\cap B\mid \ge k where A,B\in \mathcal{A} and 1\le k\le n-1? By antichain, I mean an antichain of the poset (2^{[n]},\subseteq) where 2^{[n]} is the power set of [n]. Related: 833011 #### Solutions Collecting From Web of "maximum size of a k-intersecting antichain of$$"

Here’s a lower bound. Let $F=\{B_1,\ldots, B_m\}$ be the set of all subsets $B_i\subset [n]$ with $|B_i|=\lceil (n+k)/2\rceil$. It is clear that this is an anti-chain. Moreover, if $i\ne j$ we have $|B_i\cap B_j|=|B_i|+|B_j|-|B_i\cup B_j|\ge 2\lceil (n+k)/2\rceil-n\ge k$, so this is a $k$-intersecting antichain of size ${n \choose \lceil (n+k)/2\rceil}$.

This bound is known to be sharp in several cases. For instance, if $k=0$ one has the usual Sperner upper bound of ${n \choose \lceil n/2\rceil}$. A paper by Katona concludes (Theorem 10) that this bound is sharp when $k=1$. I suspect that this is sharp in general, but I have not yet had the time to try and generalize Katona’s result.

Not sure how to answer fully, but this provides a decent lower-bound:

Set $k = \lfloor n/2 \rfloor$.
Split $[n]$ into $A = \{1,\dots,k\}$ and $B = \{k + 1,\dots,2k\}$. Label these elements $a_1,\dots,a_k$ and $b_1,\dots,b_k$ respectively.

Consider any $S \subset \{1,\dots,k\}$. Define the set $f(S)$ by stating

• $a_i \in f(S) \iff i \in S$ and
• $b_i \in f(S) \iff i \notin S$

It is clear that $f$ takes the power set of $\{1,\dots,k\}$ and produces an equinumerous antichain.

So, we can always find an antichain of size at least $2^{\lfloor n/2\rfloor}$.