A natural bijection for contiguous pattern avoidance in words

Abstract

Two words $p$ and $q$ are avoided by the same number of length-$n$ words, for all $n$, precisely when $p$ and $q$ have the same set of border lengths. Previous proofs of this theorem use generating functions but do not provide an explicit bijection. We give a bijective proof for all pairs $p,q$ that have the same set of proper borders, establishing a natural bijection from the set of words avoiding $p$ to the set of words avoiding $q$.

This version is our accepted manuscript. The most important changes from the previous version are as follows. The proof of the main theorem is streamlined, the introduction is updated, and section 4 is omitted. (12 pages, 8 figures)

Cited by in corpus (1)

• Shifts of Finite Type Obtained by Forbidding a Single Pattern