maximum size of a $k$-intersecting antichain of $[n]$

Question

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

Answer 1

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

Answer 2

Answer: ${n \choose \lceil (n+k)/2\rceil}$.

Here's the 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}$.

The upper bound for this result is Theorem 1 of this paper by Milner.