Penn Arts & Sciences Logo

Logic and Computation Seminar

Monday, January 27, 2020 - 3:30pm

Sam Braunfeld

UMD

Location

University of Pennsylvania

DRL 4C8

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.