Cross-free families have linear size

István Tomon · 2026

Read Cross-free families have linear size by István Tomon (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05443.txt.

Introduction

István Tomon proves the Karzanov-Lomonosov conjecture. Two subsets A and B of X cross if A minus B, B minus A, A intersect B, and X minus A union B are nonempty. Karzanov and Lomonosov conjectured almost fifty years ago that every subset family of an n-element set with no k-pairwise crossings is O(kn). The author proves O_k(n), settling the main problem. The author proves every k-wise laminar family is linear. K-wise laminar means no k-antichain with nonempty common intersection.

Catalog record

CREATORIstván Tomon
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31468
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.05443

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cross-free families have linear size István Tomon Abstract Two subsets A A and B B of a ground set X X are crossing if none of the four sets A ∖ B , B ∖ A , A ∩ B , X ∖ ( A ∪ B ) A\setminus B,B\setminus A,A\cap B,X\setminus(A\cup B) are empty. Almost fifty years ago, Karzanov and Lomonosov conjectured that every family of subsets of an n n -element ground set with no k k -pairwise crossing members has size O ⁡ ( k ​ n ) O(kn) . We prove the bound O k ​ ( n ) O_{k}(n) , settling (arguably) the main problem about the growth rate of such families. 1 Introduction Let X be an n -element ground set. Two sets A,B\subset X are crossing if none of the four sets A\setminus B,B\setminus A,A\cap B, and X\setminus(A\cup B) are empty. Equivalently, A and B are crossing if their Venn diagram has no empty regions. In this paper, we address a long-standing conjecture of Karzanov and Lomonosov [ 13 ] regarding the maximum size of families containing no k pairwise-crossing members, referred to as k -cross-free families. Note that the definition of crossing is invariant under complementation of its arguments; if \mathcal{F}\subset 2^{X} is k -cross-free and A\in\mathcal{F} , one may include X\setminus A without violating the k -cross-free property. A 2-cross-free family is equivalent to a laminar family (after accounting for complements), where a family is laminar if any two members are either disjoint, or one contains the other. A classical result of Edmonds and Giles [ 9 ] states that the maximum size of a laminar family is 2n , implying the bound of 4n-2 for 2-cross-free families. The importance of 3-cross-free families stems from the locking theorem of Karzanov and Lomonosov [ 13 ] (1978), which characterizes the families of subsets \mathcal{F}\subset X that can be simultaneously ”locked” by a multiflow — meaning the flow value across each cut (A,X\setminus A) for A\in\mathcal{F} achieves the cut’s minimum capacity. They proved that a family is lockable in every graph if and only if it is 3-cross-free, providing a powerful multiflow generalization of the Max-flow min-cut theorem. This motivated the search for a general bound for the size of k -cross-free families. Karzanov and Lomonosov [ 12 , 13 ] , and Pevzner [ 16 ] conjectured that the maximum size of a k -cross-free family on an n -element ground set is O(kn) . Early progress by Lomonosov provided an elegant O(kn\log n) upper bound, derived from the observation that any element x\in X can be contained in at most k-1 sets of a fixed size \ell<n/2 . For the case k=3 , Pevzner [ 16 ] proved a linear bound, and a very short argument for the bound 10n was given by Fleiner [ 10 ] . This was subsequently sharpened to the optimal 8n-20 by Dress, Koolen, and Moulton [ 8 ] . The existence of a linear bound for k\geq 4 remained open. Grünewald, Koolen, Moulton and Wu [ 11 ] proved linearity for specific subclasses of 4-cross-free families, but the general O(kn\log n) bound persisted as the state-of-the-art for decades. In 2019, Kupavskii, Pach, and Tomon [ 14 ] achieved the first general improvement O_{k}(n\log^{*}n) , coming tantalizingly close to linearity. In this work, we close the gap. Theorem 1.1 . For every k , there exists c_{k}>0 such that the following holds. Let X be a set of size n , and let \mathcal{F}\subset 2^{X} be a k -cross-free family. Then |\mathcal{F}|\leq c_{k}n . In their survey of research problems in discrete geometry, Brass, Moser, and Pach [ 4 ] highlight interesting connections between the Karzanov-Lomonosov conjecture and geometric crossing problems. A fundamental question in the theory of graph drawings is whether there exists a constant c_{k} such that every geometric graph (i.e. graph drawn in the plane with straight line edges) on n vertices with at least c_{k}n edges contains k pairwise crossing edges, where crossing is meant in the usual geometric sense. By Euler’s polyhedral formula, a geometric graph with no 2 crossing edges has at most 3n-6 edges. The existence of c_{3} was proved by Agarwal, Aronov, Pach, Pollack, and Sharir [ 2 ] (see also [ 3 , 15 ] ), and the existence of c_{4} was confirmed by Ackerman [ 1 ] . However, for k\geq 5 , the problem remains open with the best known general bound being O_{k}(n\log n) due to Valtr [ 18 ] . Although ”crossing” in the geometric sense differs from the set-theoretic definition, the two concepts coincide in case the vertices are in convex position. Capoyleas and Pach [ 5 ] proved that a geometric graph on n vertices in convex position with no k pairwise crossing edges has at most 2(k-1)n-\binom{2k-1}{2} edges, and this bound is optimal for n\geq 2k . This result is equivalent to stating that if X is a cyclically ordered set and \mathcal{F}\subset 2^{X} is a k -cross-free family of intervals, then |\mathcal{F}|\leq 4(k-1)n-2\binom{2k-1}{2} . Our main result extends this linearity from the restricted case of intervals to arbitrary families of subsets. Beyond geometry and optimization, k -cross-free families play a structural role in phylogenetic combinatorics, particularly in the study of split systems and circular networks [ 7 ] . The remainder of the paper is devoted to the proof of Theorem 1.1 . 2 Preliminaries In this section, we collect a few simple results and introduce our notation. First, we show that the notion of crossing can be slightly relaxed. Two sets A and B are weakly-crossing if none of the three sets A\cap B,A\setminus B,B\setminus A are empty. A family \mathcal{F}\subset 2^{X} is weakly- k -cross-free if it does not contain k sets that are pairwise weakly-crossing. The next simple lemma shows that in order to prove Theorem 3.1 , it is enough to consider weakly- k -cross-free families. Lemma 2.1 . Let \mathcal{F}\subset 2^{X} be a k -cross-free family. Then there exists a weakly- k -cross-free family \mathcal{F}^{\prime}\subset 2^{X} of size at least |\mathcal{F}|/2 . Proof. Let x\in X be arbitrary and let \mathcal{F}_{0}=\{A\in\mathcal{F}:x\not\in A\} . Note that the union of no two sets in \mathcal{F}_{0} is X , so \mathcal{F}_{0} is weakly- k -cross-free. If |\mathcal{F}_{0}|\geq|\mathcal{F}|/2 , then \mathcal{F}^{\prime}=\mathcal{F}_{0} suffices. Otherwise, let \mathcal{F}^{\prime}=\{X\setminus A:A\in\mathcal{F}\setminus\mathcal{F}_{0}\} . Then \mathcal{F}^{\prime} is also k -cross-free and no element of \mathcal{F}^{\prime} contains x , so it is also weakly k -cross-free, and has size at least |\mathcal{F}|/2 . ∎ We recall some standard terminology about set-systems. Let \mathcal{F}\subset 2^{X} . • Two sets A,B\subset X are comparable if A\subset B or B\subset A , otherwise incomparable. • \mathcal{F} is a chain if any two if its members are comparable. Equivalently, \mathcal{F} is a chain if there is an enumeration A_{1}\subset\dots\subset A_{s} of the elements of \mathcal{F} . Also, \mathcal{F} is a continuous chain if |A_{i+1}|=|A_{i}|+1 for i=1,\dots,s-1 . • \mathcal{F} is an antichain if any two elements of \mathcal{F} are incomparable. • \mathcal{F} is intersecting if A\cap B\neq\emptyset for every A,B\in\mathcal{F} . Dilworth’s theorem [ 6 ] states that any partially ordered set (such as a set-system ordered by the subset

Read the complete text