Abstract
Let $Tr(n, m, k)$ denote the largest number of distinct projections onto $k$ coordinates guaranteed in any family of $m$ binary vectors of length $n$. The classical Sauer–Perles–Shelah Lemma implies that $Tr(n, n^r, k) = 2^k$ for $k \le r$. While determining $Tr(n, m, k)$ precisely for general $k$ and $m$ is a long-standing challenge, it remains a central problem with deep connections to computer science and combinatorics. In this work, we prove that for $r, \alpha^{-1} \le n^{o(1)}$, $Tr(n, n^r, \alpha n) = n^{\mu(1+o(1))}$ where $\mu = \frac{r + 1 - \log(1 + \alpha)}{2 - \log(1 + \alpha)}$. This result essentially determines the trace function for linear $k$ and polynomial $m$. Our proof relies on a new "sparse" version of the Kruskal–Katona Theorem, which we show to be essentially optimal.
Introduction
In extremal combinatorics, a hypergraph (or set system) is defined as a collection of subsets of a ground set of $n$ elements. A fundamental operation on such systems is the trace: the projection of the hypergraph onto a subset of coordinates $I$. Formally, the trace of a hypergraph $\mathcal{F}$ on $I$ is the set $\mathcal{F}|_I = \{ A \cap I : A \in \mathcal{F} \}$.
The central object of this study is the function $Tr(n, m, k)$, defined as the maximum number of distinct projections onto $k$ coordinates that is guaranteed to exist in any hypergraph with $n$ vertices and $m$ edges. This function serves as a measure of the "shattering" capability of set systems, a concept vital to computational learning theory and discrete geometry.
The Problem: The Missing Middle Ground
The behavior of $Tr(n, m, k)$ has been well-understood in two extreme regimes:
- Small $k$: The Sauer-Perles-Shelah Lemma handles the case where $k$ is small relative to the number of edges, showing that if $m$ is large enough, one can always find a subset of size $k$ that is fully shattered (i.e., $2^k$ projections).
- Exponential $m$: Results such as those by Kahn, Kalai, and Linial (KKL) provide non-trivial bounds when the number of edges $m$ is a significant fraction of the total possible edges ($2^n$).
However, a significant gap existed in the "middle ground" where the number of edges $m$ is polynomial ($n^r$) and the projection size $k$ is a linear fraction of $n$ ($\alpha n$). Previous bounds by Bollobás and Radcliffe left this regime largely unresolved. This paper closes that gap by providing a near-exact determination of the growth rate in this polynomial-linear regime.
Methodology: The Sparse Kruskal-Katona Theorem
The authors' primary innovation is the development of a Sparse Kruskal-Katona Theorem.
From Global to Local Bounds
The classical Kruskal-Katona (KK) theorem provides a lower bound on the number of $i$-element subsets (shadows) contained within the edges of a $k$-uniform hypergraph. While fundamental, the classical KK bound is "global" and becomes loose when the hypergraph is sparse. The authors prove that if a hypergraph is "sparse"—meaning its induced sub-hypergraphs do not contain dense clusters of edges—one can guarantee a significantly larger number of $i$-subsets than the classical theorem predicts.
Hypergraph Regularization and Links
To prove this sparse version, the authors employ a decomposition method:
- Decomposition: They iteratively identify high-degree vertices to break the hypergraph into "links" (the set of edges containing a specific vertex).
- Cleaning: These links are "cleaned" by removing low-degree vertices, ensuring a degree of regularity that allows for more precise counting.
- Aggregation: By analyzing the structure of these links locally, the authors apply the classical KK theorem at a micro-level and aggregate the results globally, avoiding the overcounting that typically weakens global bounds.
Probabilistic Construction
To establish upper bounds and prove the tightness of their results, the authors utilize a randomized construction. They build a hypergraph by taking the union of many cliques on random subsets of vertices. They demonstrate that this construction is nearly edge-disjoint, proving that their Sparse KK bounds are essentially optimal (Theorem 1.7).
Key Results and Insights
The Trace Formula
The paper's most significant contribution is the precise determination of the trace function for $m = n^r$ and $k = \alpha n$. The growth rate is shown to be $n^{\mu(1+o(1))}$, where: $$\mu = \frac{r + 1 - \log(1 + \alpha)}{2 - \log(1 + \alpha)}$$ This formula provides the missing link between previously known extremal cases.
The Role of Local Density
A key insight of this work is that the bottleneck for the trace function is not the total number of edges, but their distribution. In many extremal problems, symmetric configurations (like a complete hypergraph) are the extremal cases. Here, the authors show that the extremal hypergraphs for traces are actually "spread out" and non-symmetric. By assuming a lack of dense local clusters (sparsity), they unlock much stronger lower bounds.
Geometric Applications
The authors provide a compelling application in discrete geometry. They show that if a set of $n$ points separates $n^r$ halfspaces in $\mathbb{R}^d$, there exists a remarkably small subset of points (of size $n^{1-\delta}$) that still separates a surprisingly large number of those halfspaces. This has potential implications for dimensionality reduction and range searching algorithms.
Conclusion
By establishing a Sparse Kruskal-Katona Theorem, Alon, Moshkovitz, and Solomon have provided a powerful new tool for extremal set theory. Their work not only solves a specific problem regarding hypergraph traces but also highlights the importance of local density constraints in determining global combinatorial properties. Future work may involve sharpening the logarithmic factors in these bounds or extending the Sparse KK framework to hypergraphs with even larger uniformity constraints.
Summary updated