Improved bounds for cross-Sperner systems

Abstract

A collection of families $({\mathcal{F}}_1,{\mathcal{F}}_2,\cdots ,{\mathcal{F}}_k)\in \mathcal{P}([n]{)}^k$ is cross-Sperner if there is no pair $i\ne j$ for which some $F_i\in {\mathcal{F}}_i$ is comparable to some $F_j\in {\mathcal{F}}_j$. Two natural measures of the `size' of such a family are the sum ${\sum }_{i=1}^k|{\mathcal{F}}_i|$ and the product ${\prod }_{i=1}^k|{\mathcal{F}}_i|$. We prove new upper and lower bounds on both of these measures for general $n$ and $k\ge 2$ which improve considerably on the previous best bounds. In particular, we construct a rich family of counterexamples to a conjecture of Gerbner, Lemons, Palmer, Patkós, and Szécsi from 2011.

15 pages