Traces of hypergraphs

Noga Mordechai Alon, Guy Moshkovitz, Noam Solomon

Research output: Contribution to journalArticle

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 languageEnglish (US)
JournalJournal of the London Mathematical Society
DOIs
StatePublished - Jan 1 2019

Fingerprint

Hypergraph
Trace
Combinatorics
Theorem
Lemma
Open Problems
Computer Science
Projection
Binary
Denote
Distinct
Imply

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Cite this

@article{87bee7970e684febbbb9862313468aa1,
title = "Traces of hypergraphs",
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.",
author = "Alon, {Noga Mordechai} and Guy Moshkovitz and Noam Solomon",
year = "2019",
month = "1",
day = "1",
doi = "https://doi.org/10.1112/jlms.12233",
language = "English (US)",
journal = "Journal of the London Mathematical Society",
issn = "0024-6107",
publisher = "John Wiley and Sons Ltd",

}

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

In: Journal of the London Mathematical Society, 01.01.2019.

Research output: Contribution to journalArticle

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 -