## 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 (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 = Θ(2^{n}). 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.

Original language | English (US) |
---|---|

Pages (from-to) | 498-517 |

Number of pages | 20 |

Journal | Journal of the London Mathematical Society |

Volume | 100 |

Issue number | 2 |

DOIs | |

State | Published - Oct 1 2019 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Keywords

- 05C69
- 05D05
- 52C99
- 68Q01 (secondary)
- 68R01 (primary)