Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

$ VC_{\ell}$-dimension and the jump to the fastest speed of a hereditary $ \mathcal{L}$-property


Author: C. Terry
Journal: Proc. Amer. Math. Soc. 146 (2018), 3111-3126
MSC (2010): Primary 03C13, 03C45, 05C30, 05C65
DOI: https://doi.org/10.1090/proc/13976
Published electronically: February 16, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we investigate a connection between the growth rates of certain classes of finite structures and a generalization of $ \textnormal {VC}$-dimension called $ \textnormal {VC}_{\ell }$-dimension. Let $ \mathcal {L}$ be a finite relational language with maximum arity $ r$. A hereditary $ \mathcal {L}$-property is a class of finite $ \mathcal {L}$-structures closed under isomorphism and substructures. The speed of a hereditary $ \mathcal {L}$-property $ \mathcal {H}$ is the function which sends $ n$ to $ \vert\mathcal {H}_n\vert$, where $ \mathcal {H}_n$ is the set of elements of $ \mathcal {H}$ with universe $ \{1,\ldots , n\}$. It was previously known that there exists a gap between the fastest possible speed of a hereditary $ \mathcal {L}$-property and all lower speeds, namely between the speeds $ 2^{\Theta (n^r)}$ and $ 2^{o(n^r)}$. We strengthen this gap by showing that for any hereditary $ \mathcal {L}$-property $ \mathcal {H}$, either $ \vert\mathcal {H}_n\vert=2^{\Theta (n^r)}$ or there is $ \epsilon >0$ such that for all large enough $ n$, $ \vert\mathcal {H}_n\vert\leq 2^{n^{r-\epsilon }}$. This improves what was previously known about this gap when $ r\geq 3$. Further, we show this gap can be characterized in terms of $ \textnormal {VC}_{\ell }$-dimension, therefore drawing a connection between this finite counting problem and the model theoretic dividing line known as $ \ell $-dependence.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03C13, 03C45, 05C30, 05C65

Retrieve articles in all journals with MSC (2010): 03C13, 03C45, 05C30, 05C65


Additional Information

C. Terry
Affiliation: Department of Mathematics, University of Maryland, College Park, Maryland 20742-4015

DOI: https://doi.org/10.1090/proc/13976
Keywords: Finite structures, enumeration, VC-dimension
Received by editor(s): January 4, 2017
Received by editor(s) in revised form: September 18, 2017, and October 5, 2017
Published electronically: February 16, 2018
Communicated by: Heike Mildenberger
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society