## Hereditary properties of words

^{1}
Department of Mathematical Sciences, The Ohio State University,
Columbus, OH 43210, USA; jobal@math.ohio-state.edu

^{2}
Department of Mathematical Sciences, The University of Memphis,
Memphis, TN 38152, and Trinity College, Cambridge CB2 1TQ,
England; bollobas@msci.memphis.edu

Let *P* be a hereditary property of words, *i.e.*, an
infinite class of finite words such that every subword (block) of
a word belonging to *P* is also in *P*.
Extending the classical Morse-Hedlund theorem, we show that
either *P* contains at least *n+1* words of length
*n* for every *n* or, for some *N*, it contains at most *N* words of length
*n* for every *n*. More importantly, we prove the following quantitative
extension of this result: if *P*
has *m ≤ n* words of length *n* then, for every *k ≥ n + m*, it contains
at most ⌈(*m* + 1)/2⌉⌈(*m* + 1)/2⌈ words of length *k*.

Mathematics Subject Classification: 05C

Key words: Graph properties / monotone / hereditary / speed / size.

*© EDP Sciences, 2005*