Monadic stability and growth rates of $\omega$-categorical structures

Abstract

For $M$ $\omega$-categorical and stable, we investigate the growth rate of $M$, i.e. the number of orbits of $Aut(M)$ on $n$-sets, or equivalently the number of $n$-substructures of $M$ after performing quantifier elimination. We show that monadic stability corresponds to a gap in the spectrum of growth rates, from slower than exponential to faster than exponential. This allows us to give a nearly complete description of the spectrum of slower than exponential growth rates (without the assumption of stability), confirming some longstanding conjectures of Cameron and Macpherson and proving the existence of gaps not previously recognized.

13 pages; to appear in Proceedings of the London Mathematical Society

References in corpus (5)

• Overview of some general results in combinatorial enumeration
• Characterizations of monadic NIP
• Structures with Small Orbit Growth
• Classification of P-oligomorphic groups, conjectures of Cameron and Macpherson
• Jumps in speeds of hereditary properties in finite relational languages

Cited by in corpus (1)

• Existential characterizations of monadic NIP