Skip to Main content Skip to Navigation
Journal articles

Shatter functions with polynomial growth rates

Boris Bukh 1 Xavier Goaoc 2
2 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, Inria Nancy - Grand Est
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 metadata
Contributor : Xavier Goaoc Connect in order to contact the contributor
Submitted on : Wednesday, February 27, 2019 - 11:16:13 AM
Last modification on : Saturday, October 16, 2021 - 11:26:10 AM

Links full text




Boris Bukh, Xavier Goaoc. Shatter functions with polynomial growth rates. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2019, 33 (2), pp.784-794. ⟨10.1137/17M1113680⟩. ⟨hal-02050524⟩



Record views