Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 1407

Preprint Number 1407

Previous Next Preprint server

1407. Michael C. Laskowski and Caroline A. Terry
Jumps in speeds of hereditary properties in finite relational languages

Submission date: 28 March 2018


Given a finite relational language L, a hereditary L-property is a class of L-structures closed under isomorphism and substructure. The speed of H is the function which sends an integer n ≥ 1 to the number of distinct elements in H with underlying set { 1, . . . , n }. In this paper we give a description of many new jumps in the possible speeds of a hereditary L-property, where L 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ás, and Weinreich, we show that for all k ≥ 2, 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:

Keywords and phrases:

Full text arXiv 1803.10575: pdf, ps.

Last updated: April 18 2018 07:09 Please send your corrections to: