### 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 = Θ(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 Tr(n, m, k) for k = Θ(n) and all m up to 2no(1). 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) |
---|---|

Journal | Journal of the London Mathematical Society |

DOIs | |

State | Published - Jan 1 2019 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Mathematics(all)

### Cite this

*Journal of the London Mathematical Society*. https://doi.org/10.1112/jlms.12233

}

*Journal of the London Mathematical Society*. https://doi.org/10.1112/jlms.12233

**Traces of hypergraphs.** / Alon, Noga Mordechai; Moshkovitz, Guy; Solomon, Noam.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Traces of hypergraphs

AU - Alon, Noga Mordechai

AU - Moshkovitz, Guy

AU - Solomon, Noam

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 Tr(n, m, k) for k = Θ(n) and all m up to 2no(1). 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.

AB - 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 Tr(n, m, k) for k = Θ(n) and all m up to 2no(1). 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.

UR - http://www.scopus.com/inward/record.url?scp=85065778211&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065778211&partnerID=8YFLogxK

U2 - https://doi.org/10.1112/jlms.12233

DO - https://doi.org/10.1112/jlms.12233

M3 - Article

JO - Journal of the London Mathematical Society

JF - Journal of the London Mathematical Society

SN - 0024-6107

ER -