Thicket Density

Research output: Contribution to journalJournal articleResearchpeer-review

Documents

  • Siddharth Bhaskar

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 languageEnglish
JournalJournal of Symbolic Logic
Volume86
Issue number1
Pages (from-to)110-127
Number of pages18
ISSN0022-4812
DOIs
Publication statusPublished - 2021

Bibliographical note

Publisher Copyright:
©

ID: 306677543