TY - JOUR
T1 - Traces of hypergraphs
AU - Alon, Noga
AU - Moshkovitz, Guy
AU - Solomon, Noam
N1 - Publisher Copyright:
© 2019 London Mathematical Society
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2019/10/1
Y1 - 2019/10/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 (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.
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 (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.
KW - 05C69
KW - 05D05
KW - 52C99
KW - 68Q01 (secondary)
KW - 68R01 (primary)
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 - 10.1112/jlms.12233
DO - 10.1112/jlms.12233
M3 - Article
AN - SCOPUS:85065778211
VL - 100
SP - 498
EP - 517
JO - Journal of the London Mathematical Society
JF - Journal of the London Mathematical Society
SN - 0024-6107
IS - 2
ER -