Thicket Density

DOI10.1017/JSL.2020.55arXiv1702.03956MaRDI QIDQ6283129

Siddharth Bhaskar

Publication date: 13 February 2017

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.

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45)

This page was built for publication: Thicket Density

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6283129)