Jumps in speeds of hereditary properties in finite relational languages

DOI10.1016/J.JCTB.2021.12.004arXiv1803.10575MaRDI QIDQ6299689FDOQ6299689

Authors: M. C. Laskowski, Caroline A. Terry 

Publication date: 28 March 2018

Abstract: Given a finite relational language $mathcalL$, a hereditary $mathcalL$-property is a class of finite $mathcalL$-structures closed under isomorphism and substructure. The speed of $mathcalH$ is the function which sends an integer $ngeq1$ to the number of distinct elements in $mathcalH$ with underlying set $1,\mathrm{...},n$. In this paper we give a description of many new jumps in the possible speeds of a hereditary $mathcalL$-property, where $mathcalL$ is any finite relational language. In particular, we characterize the jumps in the polynomial and factorial ranges, and show they are essentially the same as in the case of graphs. The results in the factorial range are new for all examples requiring a language of arity greater than two, including the setting of hereditary properties of $k$-uniform hypergraphs for $k>2$. Further, adapting an example of Balogh, Bollob'{a}s, and Weinreich, we show that for all $kgeq2$, there are hereditary properties of $k$-uniform hypergraphs whose speeds oscillate between functions near the upper and lower bounds of the penultimate range, ruling out many natural functions as jumps in that range. Our theorems about the factorial range use model theoretic tools related to the notion of mutual algebricity.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Classification theory, stability, and related concepts in model theory (03C45) Enumeration in graph theory (05C30) Hypergraphs (05C65)

This page was built for publication: Jumps in speeds of hereditary properties in finite relational languages

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