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 (Formula presented.) for (Formula presented.). Although determining Tr(n, m, k) precisely for general k and m seems hopeless, estimating it remains a widely open problem with connections to important questions in computer science and combinatorics. For example, an influential result of Kahn–Kalai–Linial gives non-trivial bounds on Tr(n, m, k) for k = Θ(n) and m = Θ(2n). Here, we prove that, for (Formula presented.), it holds that Tr(n, nr, αn) = nμ(1+o(1)) with (Formula presented.) Thus, we (essentially) determine (Formula presented.) for (Formula presented.) and all (Formula presented.) up to (Formula presented.). For the proof, we establish a ‘sparse’ version of another classical result, the Kruskal–Katona Theorem, which gives a stronger guarantee when the hypergraph does not induce dense sub-hypergraphs. Furthermore, we prove that the parameters in our sparse Kruskal–Katona theorem are essentially best possible. Finally, we mention two simple applications which may be of independent interest.
All Science Journal Classification (ASJC) codes
- 68Q01 (secondary)
- 68R01 (primary)