Improved Bounds for Cross-Sperner Systems

• Published in: The Electronic journal of combinatorics 2024-04, Vol.31 (2)
• Main Authors: Behague, Natalie, Kuperus, Akina, Morrison, Natasha, Wright, Ashna
• Format: Article
• Language: English
• ISSN: 1077-8926; 1077-8926
• DOI: 10.37236/11860

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 \not= 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.