Beating the Ahlswede--Khachatrian bound for the Erd\H{o}s--Frankl--Pach problem

This paper disproves the long-standing Mubayi-Zhao conjecture that the Ahlswede-Khachatrian bound is optimal for the Erdős-Frankl-Pach problem by constructing $(d+1)$-uniform families with VC-dimension $d$ that exceed this bound for all $d \ge 3$.

The Gist

Imagine you are organizing a massive library of books. In this library, every book is a collection of pages, and every page is a unique number from 1 to $n$.

For decades, mathematicians have been trying to answer a very specific question about these book collections: How many books can you have in your library if you follow two strict rules?

1. The Size Rule: Every book must have exactly the same number of pages (let's say $d+1$ pages).
2. The Complexity Rule: The library cannot be too "chaotic." Specifically, if you pick any group of pages, the library shouldn't be able to create every possible combination of those pages using different books. Mathematicians call this limit the "VC-dimension."

The Old Belief: The "Star" Library

In the 1980s, famous mathematicians Erdős, Frankl, and Pach made a guess. They thought the biggest possible library would look like a Star.

Imagine a star where every book shares one specific page (say, page #1). If you fix page #1, you can mix and match the other pages freely, but you can't go beyond a certain size. They believed this "Star" arrangement was the absolute maximum size you could ever reach.

The First Challenge: The "Ahlswede–Khachatrian" Library

In 1997, two other mathematicians, Ahlswede and Khachatrian, proved the "Star" guess was wrong. They built a library that was slightly bigger than the Star.

Think of their library as a Star with a Secret Extension.

• They kept the main Star (all books with page #1).
• But they added a special "extension wing." This wing contained books that didn't have page #1, but followed a very specific, tricky pattern involving pages 2, 3, and 4.
• This new library was bigger than the Star, but only by a small amount.

For a long time, everyone believed this "Star + Extension" library was the final answer. In 2007, Mubayi and Zhao explicitly guessed that you could never build a library bigger than this.

The New Discovery: Breaking the Limit

This paper, by Tuan Tran and Zixiang Xu, says: "Not so fast."

They discovered that for libraries with 3 or more pages per book (mathematically, $d \ge 3$), you can actually build a library that is even bigger than the "Star + Extension" limit.

How did they do it? The "Recursive Puzzle" Analogy

Imagine the "Star + Extension" library left some empty space in the corners. For small libraries (2 pages per book), those corners were perfectly sealed; there was no room to add more books without breaking the rules.

But for larger libraries (3+ pages), the authors found a way to fill those empty corners recursively.

1. The Core: They built a tiny, special "core" library using just 6 specific pages. They designed this core so that it had two specific "missing patterns" (like two empty slots in a puzzle).
2. The Recursive Fill: Instead of leaving those slots empty, they filled them with smaller versions of the same problem. They took the "Star + Extension" logic, shrank it down, and plugged it into those empty slots.
3. The Result: By nesting these smaller libraries inside the empty spots of the core, they created a massive structure that is strictly larger than the previous record holders.

Why Does This Matter?

The authors show that the answer to this math problem isn't a single, simple formula that works for all sizes.

• For small libraries (2 pages), the "Star + Extension" is the best you can do.
• For larger libraries (3+ pages), the rules change. You can keep finding clever ways to pack more books in by using these recursive "fill-in-the-blank" tricks.

The Bottom Line

The paper proves that the long-held belief about the maximum size of these mathematical libraries was wrong for almost all cases. The "best possible" size is actually larger than we thought, and the way to find it involves a clever, multi-layered construction that gets more complex as the libraries get bigger.

In short: They found a way to pack more books into the library than anyone thought possible, by realizing that the "empty spaces" in the old designs could be filled with smaller, cleverer versions of the library itself.

Technical Summary

Technical Summary: Beating the Ahlswede–Khachatrian Bound for the Erdős–Frankl–Pach Problem

Problem Statement
The paper addresses the Erdős–Frankl–Pach problem, which seeks to determine $M_d(n)$, the maximum size of a $(d+1)$-uniform family $\mathcal{F} \subseteq \binom{[n]}{d+1}$ with VC-dimension at most $d$. Historically, Erdős and, independently, Frankl and Pach conjectured that for sufficiently large $n$, the optimal construction is a "star" (all sets containing a fixed element), yielding a size of $\binom{n-1}{d}$.

This conjecture was disproven in 1997 by Ahlswede and Khachatrian, who constructed a family of size:
$$AK_d(n) := \binom{n-1}{d} + \binom{n-4}{d-2}$$
which maintains VC-dimension at most $d$. Subsequently, Mubayi and Zhao (2007) conjectured that $AK_d(n)$ is the exact maximum ($M_d(n) = AK_d(n)$) for all sufficiently large $n$. This belief was reinforced by Wang, Xu, and Zhang (2024), who proved the conjecture holds for the specific case $d=2$ and $n \ge 7$.

Methodology and Construction
The authors construct a new family $\mathcal{F}_6$ that exceeds the Ahlswede–Khachatrian bound for all $d \ge 3$. The construction relies on a recursive strategy using a specific "core" set $C = \{1, 2, 3, 4, 5, 6\}$ and a remainder set $U = [n] \setminus C$.

1. Core Structure: The authors define a collection of subsets $\mathcal{B} = \bigcup_{i=1}^6 \mathcal{B}_i$ within the power set of $C$. The sizes of these levels are $(1, 5, 11, 13, 6, 1)$. Crucially, two specific 4-element patterns, $R_1 = \{1, 2, 4, 5\}$ and $R_2 = \{2, 3, 5, 6\}$, are explicitly excluded from $\mathcal{B}$.
2. Recursive Extension: The family $\mathcal{F}_6$ is formed by three disjoint parts:
   • The $\mathcal{B}$-part: Sets formed by $P \cup B$ where $P \in \mathcal{B}$ and $B$ is a subset of $U$ of appropriate size.
   • The $R_1$-recursive part: Sets formed by $R_1 \cup H$ where $H$ belongs to a family $\mathcal{H}_1 \subseteq \binom{U}{d-3}$ with VC-dimension $\le d-4$.
   • The $R_2$-recursive part: Sets formed by $R_2 \cup H$ where $H$ belongs to a family $\mathcal{H}_2 \subseteq \binom{U}{d-3}$ with VC-dimension $\le d-4$.
3. VC-Dimension Verification: To prove $\text{VC}(\mathcal{F}_6) \le d$, the authors employ a "missing trace" argument (Fact 2.1). They demonstrate that for every set $F \in \mathcal{F}_6$, there exists a subset $T_F \subseteq F$ such that $T_F$ is not realized as a trace of $F$ by any other set in the family.
   • For most patterns in $\mathcal{B}$, a specific "certificate" $\sigma(P)$ is defined such that no set in the family can intersect $P$ exactly at $\sigma(P)$.
   • For the exceptional patterns involving $R_1$ and $R_2$, the proof relies on the fact that the recursive subfamilies $\mathcal{H}_1$ and $\mathcal{H}_2$ do not shatter their respective bases, ensuring that specific traces (e.g., $\{3, 5\}$ or $\{4, 5\}$ combined with missing subsets of the base) cannot be formed.

Key Results
The paper establishes the following lower bounds, disproving the Mubayi–Zhao conjecture for $d \ge 3$:

1. For $d=3$: For all $n \ge 6$,
   $$M_3(n) \ge \binom{n-1}{3} + n - 3$$
   This exceeds the Ahlswede–Khachatrian bound $\binom{n-1}{3} + \binom{n-4}{1} = \binom{n-1}{3} + n - 4$.

2. For $d \ge 4$: For all $n \ge 2d$,
   $$M_d(n) \ge \binom{n-1}{d} + \binom{n-4}{d-2} + \binom{n-6}{d-3} + 2M_{d-4}(n-6)$$
   This improves the previous bound by at least $\binom{n-6}{d-3}$.

The authors note that the $d=2$ result ($M_2(n) = AK_2(n)$) can serve as a base case for the recursive term in higher dimensions (e.g., for $d=6$).

Significance and Claims
The paper claims that the Mubayi–Zhao conjecture is false for every $d \ge 3$. The primary significance lies in demonstrating that the solution to the Erdős–Frankl–Pach problem is not uniform across dimensions. While the $d=2$ case is rigid and governed by the Ahlswede–Khachatrian bound, higher dimensions allow for "missing patterns" to be filled recursively, leading to larger families.

The authors suggest that the optimal formula for $M_d(n)$ likely changes genuinely with $d$. They propose that for $d=3$, the bound $\binom{n-1}{3} + n - 3$ is sharp for sufficiently large $n$ (Conjecture 3.1), though they acknowledge the complexity increases sharply as $d$ grows. The construction implies that finding the exact maximum size is a finite but rapidly becoming complicated problem, as missing patterns usable at one level may be destroyed by traces from higher levels.

The paper concludes by noting that the authors were informed of an independent, similar result by Gennian Ge and Xiaochen Zhao prior to submission.