Thicket Density
Research output: Contribution to journal › Journal article › Research › peer-review
Documents
- Thicket Density
Accepted author manuscript, 241 KB, PDF document
We define a new type of shatter function for set systems that satisfies a Sauer-Shelah type dichotomy, but whose polynomial-growth case is governed by Shelah's two-rank instead of VC dimension. We identify the least exponent bounding the rate of growth of the shatter function, the quantity analogous to VC density, with Shelah's -rank.
Original language | English |
---|---|
Journal | Journal of Symbolic Logic |
Volume | 86 |
Issue number | 1 |
Pages (from-to) | 110-127 |
Number of pages | 18 |
ISSN | 0022-4812 |
DOIs | |
Publication status | Published - 2021 |
Bibliographical note
Publisher Copyright:
©
ID: 306677543