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

DOI10.1090/PROC/13976zbMATH Open1406.03049arXiv1701.00470OpenAlexW2567736634MaRDI QIDQ4636765FDOQ4636765

Caroline A. Terry

Publication date: 20 April 2018

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

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.

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

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

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)

Cites Work

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

Cited In (5)

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

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)