On the size of $k$-cross-free families

Abstract

Two subsets $A,B$ of an $n$-element ground set $X$ are said to be \emph{crossing}, if none of the four sets $A\cap B$, $A\setminus B$, $B\setminus A$ and $X\setminus (A\cup B)$ are empty. It was conjectured by Karzanov and Lomonosov forty years ago that if a family $\mathcal{F}$ of subsets of $X$ does not contain $k$ pairwise crossing elements, then $|\mathcal{F}|=O_k(n)$. For $k=2$ and $3$, the conjecture is true, but for larger values of $k$ the best known upper bound, due to Lomonosov, is $|\mathcal{F}|=O_k(n\log n)$. In this paper, we improve this bound by showing that $|\mathcal{F}|=O_k(n{\log }^{\ast }n)$ holds, where ${\log }^{\ast }$ denotes the iterated logarithm function.

arXiv comment7 pages