RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

Issue		Theoret. Informatics Appl. Volume 39, Number 1, January-March 2005 Imre Simon, the tropical computer scientist
Page(s)		49 - 65
DOI		10.1051/ita:2005003

Theoret. Informatics Appl. 39, 49-65 (2005)
DOI: 10.1051/ita:2005003

Hereditary properties of words

József Balogh¹ and Béla Bollobás²

¹ Department of Mathematical Sciences, The Ohio State University, Columbus, OH 43210, USA; jobal@math.ohio-state.edu
² Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, and Trinity College, Cambridge CB2 1TQ, England; bollobas@msci.memphis.edu

Abstract
Let ${\mathcal 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 ${\mathcal P}$ is also in ${\mathcal P}$ . Extending the classical Morse-Hedlund theorem, we show that either ${\mathcal 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 ${\mathcal P}$ has $m\le n$ words of length n then, for every $k\ge n+m$ , it contains at most $\lceil (m+1)/2\rceil \lfloor (m+1)/2 \rfloor$ words of length k.

Mathematics Subject Classification. 05C

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

© EDP Sciences 2005

What is OpenURL?