Shatter Functions with Polynomial Growth Rates

DOI10.1137/17M1113680zbMATH Open1419.05209arXiv1701.06632OpenAlexW2963961425MaRDI QIDQ5232129FDOQ5232129

Xavier Goaoc, Boris Bukh

Publication date: 29 August 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We study how a single value of the shatter function of a set system restricts its asymptotic growth. Along the way, we refute a conjecture of Bondy and Hajnal which generalizes Sauer's Lemma.

Full work available at URL: https://arxiv.org/abs/1701.06632

zbMATH Keywords

extremal set theorySauer's lemmashatter function

Mathematics Subject Classification ID

Extremal set theory (05D05) Discrete geometry (52C99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Induced subsets
• On the density of sets of vectors
• On the trace of finite sets
• Defect Sauer results
• The number of partitions of a set of N points in k dimensions induced by hyperplanes
• Set systems and families of permutations with small traces
• Rational exponents in extremal graph theory

Cited In (2)

• Traces of hypergraphs
• Some remarks on the Zarankiewicz problem

This page was built for publication: Shatter Functions with Polynomial Growth Rates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232129)