Submission date: 2 January 2017

Abstract:

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

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 1701.00470: pdf, ps.