Thicket Density
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Thicket Density. / Bhaskar, Siddharth.
In: Journal of Symbolic Logic, Vol. 86, No. 1, 2021, p. 110-127.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Thicket Density
AU - Bhaskar, Siddharth
N1 - Publisher Copyright: ©
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
U2 - 10.1017/jsl.2020.55
DO - 10.1017/jsl.2020.55
M3 - Journal article
AN - SCOPUS:85109572385
VL - 86
SP - 110
EP - 127
JO - Journal of Symbolic Logic
JF - Journal of Symbolic Logic
SN - 0022-4812
IS - 1
ER -
ID: 306677543