𝑉𝐶_{ℓ}-dimension and the jump to the fastest speed of a hereditary ℒ-property

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