MIT Combinatorics Seminar

Growth of Families of Hereditary Structures

Joszef Balogh (University of Illinois at Urbana-Champaign)

Friday, April 7, 2006   4:30 pm    Room 2-105


A hereditary property of combinatorial structures is a collection of structures (e.g. graphs, words, permutations) which is closed under isomorphism and under taking induced substructures (like induced subgraphs), and contains arbitrarily large structures. Given a property $\mathcal{P}$, we write $\mathcal{P}_n$ for the number of distinct (non-isomorphic) structures in $\mathcal{P}$ with $n$ elements, and the sequence $|\mathcal{P}_n|$ is the {\it speed} of $\mathcal{P}$. The speed of words was studied first by Morse and Hedlund in 1938. In the last few years, the ex-Stanley-Wilf conjecture, now Klazar-Marcus-Tardos Theorem was known on the speed of permutations. In this talk I survey that area, pointing out generalizations toward ordered graphs, including few short proofs as well.