Shatter functions with polynomial growth rates

Boris Bukh 1 Xavier Goaoc 2
2 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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.
Document type :
Journal articles
Complete list of metadatas
Contributor : Xavier Goaoc <>
Submitted on : Wednesday, February 27, 2019 - 11:16:13 AM
Last modification on : Friday, April 19, 2019 - 11:12:03 AM

Links full text


  • HAL Id : hal-02050524, version 1
  • ARXIV : 1701.06632



Boris Bukh, Xavier Goaoc. Shatter functions with polynomial growth rates. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, In press. ⟨hal-02050524⟩



Record views