Penn Arts & Sciences Logo

Logic and Computation Seminar

Monday, January 27, 2020 - 3:30pm

Sam Braunfeld



University of Pennsylvania


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.