Abstract
In this paper we investigate a connection between the growth rates of certain classes of finite structures and a generalization of -dimension called -dimension. Let be a finite relational language with maximum arity . A hereditary -property is a class of finite -structures closed under isomorphism and substructures. The \emph{speed} of a hereditary -property is the function which sends to , where is the set of elements of with universe . It was previously known there exists a gap between the fastest possible speed of a hereditary -property and all lower speeds, namely between the speeds and . We strengthen this gap by showing that for any hereditary -property , either or there is such that for all large enough , . This improves what was previously known about this gap when . Further, we show this gap can be characterized in terms of -dimension, therefore drawing a connection between this finite counting problem and the model theoretic dividing line known as -dependence.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.