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, December 13, 2019 - 9:32:04 AM

Links full text

Identifiers

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, 33 (2), pp.784-794. ⟨10.1137/17M1113680⟩. ⟨hal-02050524⟩

Share

Metrics

Record views

49