Kruskal-Katona's function and a variation of cross-intersecting antichains

Abstract

We prove some properties of the Kruskal-Katona function, and apply to the following variation of cross-intersecting antichains. Let $n\ge 4$ be an even integer and $\mathcal{A}$ and $\mathcal{B}$ be two cross-intersecting antichains of ${\mathbb{N}}_n$ with at most $k$ disjoint pairs, i.e. for all $A_i\in \mathcal{A}$, $B_j\in \mathcal{B}$, $A_i\cap B_j=\varnothing$ only if $i=j\le k$. We prove a best possible upper bound on $|\mathcal{A}|+|\mathcal{B}|$. Furthermore, we show that the extremal families contain only $\frac{n}{2}$ and $(\frac{n}{2}+1)$-sets.

20 pages. arXiv admin note: text overlap with arXiv:2001.01910