September 27
Sam Braunfeld,
University of Maryland
Monadic stability and growth rates of omega-categorical structures
Generalizing the classical combinatorial problem of counting the orbits of a group acting on a finite set, we consider the growth rate of an omega-categorical structure M, which counts the orbits of Aut(M) acting on n-sets. We show that for stable M, there is a gap from subexponential to superexponential growth, corresponding to whether M is monadically stable. This allows us to confirm some longstanding conjectures of Macpherson about the spectrum of possible growth rates.