Weakly Self-Avoiding Words and a Construction of Friedman

Abstract

H. Friedman obtained remarkable results about the longest finite sequence $x$ over a finite alphabet such that for all $i \ne j$ the word $x[i..2i]$ is not a subsequence of $x[j..2j]$. In this note we consider what happens when "subsequence" is replaced by "subword"; we call such a sequence a "weakly self-avoiding word". We prove that over an alphabet of size $1$ or $2$, there is an upper bound on the length of weakly self-avoiding words, while if the alphabet is of size $3$ or more, there exists an infinite weakly self-avoiding word.