Spring 2017

Pseudorandomness Seminar

Tuesday, May 2nd, 2017, 4:30 pm5:30 pm

Add to Calendar

Parent Program: 

Calvin Lab Room 116

 Structure and Enumeration Theorems for Hereditary Properties of L-Structures

The study of structure and enumeration for hereditary graph properties has been a major area of research in extremal combinatorics.  Over the years such results have been extended to many combinatorial structures other than graphs.  This line of research has developed an informal strategy for how to prove these results in various settings. In this talk we use tools from model theory to formalize this strategy. In particular, we generalize certain definitions, tools, and theorems which appear commonly in approximate structure and enumeration theorems in extremal combinatorics. Our results apply to classes of finite L-structures which are closed under isomorphism and model-theoretic substructure, where L is any finite relational language.