Hereditary properties of words
Department of Mathematical Sciences, The Ohio State University,
Columbus, OH 43210, USA; email@example.com
2 Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, and Trinity College, Cambridge CB2 1TQ, England; firstname.lastname@example.org
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