MIT Combinatorics Seminar
Growth of Families of Hereditary Structures
Joszef Balogh (University of Illinois at UrbanaChampaign)
Friday, April 7, 2006 4:30 pm Room 2105
ABSTRACT

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
(nonisomorphic) 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 exStanleyWilf conjecture, now KlazarMarcusTardos 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.


