VC_ -dimension and the jump to the fastest speed of a hereditary L-property

DOI10.1090/PROC/13976MaRDI QIDQ4636765zbMATH OpenOpenAlexFDO

Authors Caroline A. Terry

Publication date 20 April 2018

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.00470

zbMATH Keywords

enumerationfinite structuresVC-dimension

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Classification theory, stability, and related concepts in model theory (03C45) Enumeration in graph theory (05C30) Hypergraphs (05C65) Models of other mathematical theories (03C65)

Abstract: In this paper we investigate a connection between the growth rates of certain classes of finite structures and a generalization of $extVC$-dimension called $ext{VC}_{ell}$-dimension. Let $mathcalL$ be a finite relational language with maximum arity $r$. A hereditary $mathcalL$-property is a class of finite $mathcalL$-structures closed under isomorphism and substructures. The emph{speed} of a hereditary $mathcalL$-property $mathcalH$ is the function which sends $n$ to $|mathcal{H}_n|$, where $mathcal{H}_n$ is the set of elements of $mathcalH$ with universe $1,ldots,n$. It was previously known there exists a gap between the fastest possible speed of a hereditary $mathcalL$-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 for any hereditary $mathcalL$-property $mathcalH$, either $|mathcal{H}_n|=2^{Theta(n^r)}$ or there is $epsilon>0$ such that for all large enough $n$, $|mathcal{H}_n|leq{2}^{n^{r-epsilon}}$. This improves what was previously known about this gap when $rgeq3$. Further, we show this gap can be characterized in terms of $ext{VC}_{ell}$-dimension, therefore drawing a connection between this finite counting problem and the model theoretic dividing line known as $ell$-dependence.

Recommendations

• The speed of hereditary properties of graphs
• A note on the speed of hereditary graph properties
• The unlabelled speed of a hereditary graph property
• A jump to the Bell number for hereditary graph properties
• Hereditary and monotone properties of combinatorial structure

Cites work

• scientific article; zbMATH DE number 3825706 (Why is no real title available?)
• scientific article; zbMATH DE number 970795 (Why is no real title available?)
• A Guide to NIP Theories
• A jump to the Bell number for hereditary graph properties
• Classification theory and the number of non-isomorphic models.
• Definable groups for dependent and 2-dependent theories
• On \(n\)-dependent groups and fields
• Projections of Bodies and Hereditary Properties of Hypergraphs
• Random hypergraphs in pseudofinite fields
• Some Remarks on the Triple Systems of Steiner.
• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• Strongly dependent theories
• The age of a relational structure
• The penultimate rate of growth for graph properties
• The speed of hereditary properties of graphs
• The structure of almost all graphs in a hereditary property

Cited in

(6)

• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
• Jumps in speeds of hereditary properties in finite relational languages
• Counting \(r\)-graphs without forbidden configurations
• Onn-dependent groups and fields II
• DISTALITY RANK
• An improved bound for regular decompositions of 3-uniform hypergraphs of bounded \(\mathrm{VC}_2\)-dimension

This page was built for publication: \(\mathrm{VC}_{\ell }\)-dimension and the jump to the fastest speed of a hereditary \(\mathcal {L}\)-property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636765)