Cross-free families have linear size

This paper proves that any family of subsets of an $n$-element ground set containing no $k$-pairwise crossing members has size $O_k(n)$, thereby confirming the long-standing Karzanov-Lomonosov conjecture regarding the linear growth rate of such cross-free families.

The Gist

Imagine you have a giant box of LEGO bricks. You want to build a collection of structures (let's call them "families") using these bricks. However, there's a strict rule you must follow: No two structures can be "too messy" with each other.

In the world of this paper, two structures are considered "messy" (or crossing) if they overlap in a very specific, complicated way. Imagine two structures:

1. They share some bricks (overlap).
2. Structure A has bricks that Structure B doesn't.
3. Structure B has bricks that Structure A doesn't.
4. There are also bricks in the box that neither structure uses.

If all four of these things are true at the same time, the structures are crossing.

The big question mathematicians have been asking for 50 years is: How big can your collection of structures get if you forbid having $k$ structures that are all messy with each other?

For example, if you say "I don't want any two structures to be messy" ($k=2$), you can only build a collection of a certain size (roughly twice the number of bricks you have). But what if you allow a little messiness, as long as you never have a group of 3, 4, or 100 structures that are all messy with each other?

The Old Guess

For decades, mathematicians Karzanov and Lomonosov guessed that the answer was simple: The size of your collection grows in a straight line.
If you have $n$ bricks, and you forbid $k$ messy structures, the maximum size of your collection is roughly $k \times n$.

• Think of it like this: If you have 100 bricks, and you forbid 3 messy structures, you can't build a million structures. You can only build a few thousand. The limit is "linear."

For a long time, people could prove this for small numbers of messy structures (like 2 or 3), but for larger numbers (4, 5, 100...), the best proof they had was much worse. It suggested the collection could be slightly bigger than a straight line—maybe $n \times \log(n)$ (which is like a straight line that gets a little bit wobbly and taller as you go).

The New Discovery

István Tomon (the author of this paper) has finally proven that the old guess was right. The collection size is indeed strictly linear. No matter how large $k$ is, the size of your collection is just a constant number times the number of bricks.

How Did He Do It? (The Analogy)

To prove this, Tomon had to show that if you try to build a collection that is too big, you are forced to create a "messy" group of $k$ structures, breaking your own rules.

Here is the step-by-step logic using a Tree House analogy:

1. The "Weak" Rule
First, Tomon relaxed the rules slightly. Instead of worrying about the most complicated messiness, he looked at a simpler version of "messy." He showed that if you can prove the limit for this simpler version, you automatically prove it for the real, complicated version.

2. Finding the "Chains"
He looked at his giant collection of structures and realized that if the collection is huge, it must contain many long, neat lines of structures.

• Imagine a Chain as a ladder: Structure A is inside Structure B, which is inside Structure C, and so on.
• He proved that a huge collection must have many of these "ladders" running parallel to each other.

3. Building the "Cross-Support Tree"
This is the magic part. Tomon took these ladders and started connecting them to build a giant, imaginary Tree House.

• The Rooms: Each room in the tree represents one of those neat ladders.
• The Hallways: The hallways connecting the rooms represent how the structures overlap.
• The Rules: He built the tree with very specific rules about how the rooms must be arranged (left to right, big to small).

4. The Trap
He proved that if your collection is too big, you can build a Tree House that is so tall and wide that it forces a contradiction.

• Imagine a tree with $k$ levels.
• If the tree is built correctly, you can pick one structure from each level of the tree.
• Tomon showed that these $k$ structures would inevitably be pairwise messy (crossing) with each other.
• But wait! Your original rule said "No $k$ messy structures allowed!"

5. The Conclusion
Since building a collection that is too big forces you to break your own rules, the collection cannot be that big. Therefore, the size of the collection must be limited to a simple straight line ($C \times n$).

Why Does This Matter?

You might wonder, "Who cares about messy LEGO structures?"

Actually, this math shows up everywhere:

• Traffic Flow: It helps engineers understand how to route traffic so that no two roads get stuck in a deadlock.
• Computer Networks: It helps design networks where data doesn't get tangled up.
• Evolutionary Trees: It helps biologists figure out how species are related without creating impossible family trees.
• Geometry: It solves a puzzle about drawing lines on a piece of paper without them crossing too many times.

The Bottom Line

For 50 years, mathematicians thought the limit of these "non-messy" collections was a bit fuzzy. István Tomon has cleaned up the picture. He proved that the limit is as clean and straight as a ruler: The bigger your ground set, the bigger your collection, but it grows at a steady, predictable, linear pace.

He didn't just find a new number; he closed a door that had been slightly ajar for half a century, finally confirming that nature (and math) prefers simple, linear growth over chaotic explosions.

Technical Summary

Here is a detailed technical summary of the paper "Cross-free families have linear size" by István Tomon.

1. Problem Statement

The paper addresses a long-standing conjecture in extremal set theory and combinatorial optimization proposed by Karzanov and Lomonosov (1978).

• Definitions:
  • Let $X$ be a ground set of size $n$. Two subsets $A, B \subseteq X$ are crossing if none of the four regions in their Venn diagram are empty: $A \setminus B$, $B \setminus A$, $A \cap B$, and $X \setminus (A \cup B)$.
  • A family $\mathcal{F} \subseteq 2^X$ is $k$-cross-free if it contains no $k$ pairwise crossing members.
• The Conjecture: Karzanov and Lomonosov conjectured that for any fixed $k$, the maximum size of a $k$-cross-free family on an $n$-element set is linear in $n$, specifically $O(kn)$.
• State of the Art:
  • For $k=2$, the problem is equivalent to laminar families (after accounting for complements), which have a maximum size of $2n$.
  • For $k=3$, linear bounds were established (e.g., $8n-20$).
  • For $k \ge 4$, the best known upper bound for decades was $O(kn \log n)$, derived by Lomonosov. A recent improvement by Kupavskii, Pach, and Tomon (2019) reduced this to $O(kn \log^* n)$, but the gap to full linearity remained open.

2. Methodology

The author proves the conjecture by establishing a linear bound for weakly-$k$-cross-free families, which implies the result for standard $k$-cross-free families.

Key Definitions and Relaxations

• Weakly-crossing: Two sets $A, B$ are weakly-crossing if $A \cap B$, $A \setminus B$, and $B \setminus A$ are all non-empty (ignoring the complement region).
• Reduction (Lemma 2.1): The author shows that if a family is $k$-cross-free, it contains a weakly-$k$-cross-free subfamily of size at least $|F|/2$. Thus, proving a linear bound for weakly-$k$-cross-free families suffices.

Core Proof Strategy

The proof proceeds by induction on $k$ and relies on a structural analysis of "extremal" families (families maximizing the ratio $|F|/|X|$). The methodology involves three main phases:

1. Extraction of Chains:

   • The author constructs an auxiliary directed graph where edges represent set inclusions ($A \to A \cup \{x\}$).
   • By analyzing "exceptional" sets (those with high out-degree) and using Turán's theorem, the author proves that an extremal family must contain a dense collection of pairwise disjoint continuous chains (sequences of sets $A \subset A \cup \{x_1\} \subset \dots$).
   • These chains are selected to satisfy specific comparability and ordering properties (Conditions C1–C4).

2. Construction of Cross-Support Trees:

   • The central innovation is the definition of a cross-support tree. This is a perfect rooted tree where:
     • Nodes represent chains from the family.
     • Edges are labeled by elements of the ground set $X$.
     • The tree structure encodes specific containment relationships between sets in different chains.
   • The tree satisfies properties (T1–T9) ensuring that sets associated with nodes in the tree have controlled intersections and containments. Specifically, the tree structure forces a hierarchy where "leftmost" branches relate to "rightmost" branches via subset inclusions.

3. Contradiction via Tree Height:

   • The author proves (Lemma 3.7) that if the family is large enough, one can construct a cross-support tree of height $k$ where every non-leaf node has at least $k$ children.
   • Lemma 3.6 demonstrates that the existence of such a tree implies the existence of $k$ pairwise weakly-crossing sets within the family.
   • Since the family is assumed to be weakly-$k$-cross-free, this is a contradiction. Therefore, the initial assumption that the family size is super-linear must be false.

3. Key Contributions

• Resolution of the Conjecture: The paper proves Theorem 1.1: For every $k$, there exists a constant $c_k$ such that any $k$-cross-free family on an $n$-element set has size at most $c_k n$. This settles the main open problem regarding the growth rate of these families.
• New Structural Tool: The introduction of cross-support trees provides a novel combinatorial framework for analyzing set systems with crossing constraints. This tool effectively translates set-theoretic properties into tree-topological properties.
• Generalization: The result extends previous linearity results known only for specific cases (like $k=3$ or intervals in convex position) to arbitrary families of subsets.

4. Results

• Main Theorem: $|F| \le c_k n$ for any $k$-cross-free family $F \subseteq 2^X$.
• Implications for Geometry: The result connects to geometric graph theory. While geometric crossing (edges crossing in a drawing) differs from set-theoretic crossing, they coincide for vertices in convex position. The paper notes that the geometric problem of bounding edges in graphs with no $k$ pairwise crossing edges remains open for $k \ge 5$ (currently $O(n \log n)$), but this set-theoretic result provides a strong theoretical foundation and suggests the geometric bound might also be linear.
• Phylogenetics: The result reinforces structural bounds in phylogenetic combinatorics, specifically regarding split systems and circular networks.

5. Significance

• Theoretical Closure: This work closes a nearly 50-year-old gap in extremal set theory, moving the bound from $O(kn \log^* n)$ to $O(kn)$.
• Multiflow Theory: The result validates the theoretical underpinnings of the "locking theorem" by Karzanov and Lomonosov, which characterizes families of cuts lockable by multiflows. It confirms that the structural complexity of such families is strictly linear.
• Methodological Impact: The "cross-support tree" technique offers a powerful new method for tackling problems involving intersection patterns and crossing constraints in discrete geometry and combinatorics. It demonstrates how complex set-theoretic constraints can be managed through hierarchical tree structures.

In summary, István Tomon's paper provides a definitive proof that families of subsets avoiding $k$ pairwise crossings cannot grow faster than linearly with the size of the ground set, resolving a major conjecture in combinatorial optimization and discrete geometry.