Logic Seminar
Caroline Terry
University of Maryland
Jumps in speeds of hereditary properties.
Abstract: A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs. Given a hereditary graph property $\mathcal{H}$, the speed of $\mathcal{H}$ is the function which sends $n$ to the number of distinct elements in $\mathcal{H}$ with underlying set $\{1,\ldots, n\}$. Not just any function can occur as the speed of hereditary graph property. Specifically, there are discrete ``jumps" in the possible speeds. Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollob\'{a}s, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized. In contrast to this, many aspects of this problem in the hypergraph setting have remained unknown. In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds. The jumps in the factorial range turned out to have surprising connections to model theory, which we also discuss. This is joint work with Chris Laskowski.
Tuesday March 6, 2018 at 3:30 PM in SEO 427