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

preprint2017arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.