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

Abstract:

In this paper we investigate a connection between the growth rates of certain classes of finite structures and a generalization of $\mathrm {VC}$-dimension called $\mathrm {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 $|\mathcal {H}_n|$, 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 $|\mathcal {H}_n|=2^{\Theta (n^r)}$ or there is $\epsilon >0$ such that for all large enough $n$, $|\mathcal {H}_n|\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 $\mathrm {VC}_{\ell }$-dimension, therefore drawing a connection between this finite counting problem and the model theoretic dividing line known as $\ell$-dependence.