On Cross-intersecting Sperner Families

Abstract

Two sets $\mathcal{A}$ and $\mathcal{B}$ are said to be cross-intersecting if $X\cap Y\ne \varnothing$ for all $X\in \mathcal{A}$ and $Y\in \mathcal{B}$. Given two cross-intersecting Sperner families (or antichains) $\mathcal{A}$ and $\mathcal{B}$ of ${\mathbb{N}}_n$, we prove that $|\mathcal{A}|+|\mathcal{B}|\le 2\left(\genfrac{}{}{0ex}{}{n}{\lceil n/2\rceil }\right)$ if $n$ is odd, and $|\mathcal{A}|+|\mathcal{B}|\le \left(\genfrac{}{}{0ex}{}{n}{n/2}\right)+\left(\genfrac{}{}{0ex}{}{n}{(n/2)+1}\right)$ if $n$ is even. Furthermore, all extremal and almost-extremal families for $\mathcal{A}$ and $\mathcal{B}$ are determined.

14 pages

Cited by in corpus (1)

• Application of some techniques in Sperner Theory: Optimal orientations of vertex-multiplications of trees with diameter 4