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

https://hal.inria.fr/hal-02050524
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

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

33