Back to Search
Start Over
Shatter functions with polynomial growth rates
- Publication Year :
- 2017
-
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.<br />Comment: 9 pages, 3 figures
- Subjects :
- Mathematics - Combinatorics
Computer Science - Discrete Mathematics
05D05, 52C99
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1701.06632
- Document Type :
- Working Paper