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^{ *} n)$ holds, where $\log^{ *}$ denotes the iterated logarithm function.
Categories: math.CO