Shatter functions with polynomial growth rates - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Discrete Mathematics Année : 2019

Shatter functions with polynomial growth rates

Boris Bukh
  • Fonction : Auteur
Department of Mathematical Sciences
Xavier Goaoc
Geometric Algorithms and Models Beyond the Linear and Euclidean realm
CV

Résumé

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.

Domaines

Informatique [cs] Mathématiques [math]

Xavier Goaoc  : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-02050524

Soumis le : mercredi 27 février 2019-11:16:13

Dernière modification le : lundi 15 avril 2024-18:02:42

Consulter le texte intégral

Dates et versions

hal-02050524 , version 1 (27-02-2019)

Identifiants

Citer

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

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS INRIA LABEX-BEZOUT UNIV-LORRAINE INRIA2 LORIA LORIA-ALGO ANR
67 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More