Thicket Density

Abstract

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 2-rank instead of VC dimension. We identify the rate of growth of this shatter function, the quantity analogous to VC density, with Shelah's $\omega$-rank.

15 pages, 7 figures

References in corpus (2)

• Model Theory and Machine Learning
• Model theory and combinatorics of banned sequences