English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we investigate a connection between the growth rates of certainclasses of finite structures and a generalization of $\text{VC}$-dimensioncalled $\text{VC}_{\ell}$-dimension. Let $\mathcal{L}$ be a finite relationallanguage with maximum arity $r$. A hereditary $\mathcal{L}$-property is a classof finite $\mathcal{L}$-structures closed under isomorphism and substructures.The \emph{speed} of a hereditary $\mathcal{L}$-property $\mathcal{H}$ is thefunction which sends $n$ to $|\mathcal{H}_n|$, where $\mathcal{H}_n$ is the setof elements of $\mathcal{H}$ with universe $\{1,\ldots, n\}$. It was previouslyknown 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 forany hereditary $\mathcal{L}$-property $\mathcal{H}$, either$|\mathcal{H}_n|=2^{\Theta(n^r)}$ or there is $\epsilon>0$ such that for alllarge enough $n$, $|\mathcal{H}_n|\leq 2^{n^{r-\epsilon}}$. This improves whatwas previously known about this gap when $r\geq 3$. Further, we show this gapcan be characterized in terms of $\text{VC}_{\ell}$-dimension, thereforedrawing a connection between this finite counting problem and the modeltheoretic dividing line known as $\ell$-dependence.

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