Sequences with changing dependencies

Abstract

Consider words over an alphabet with n letters. Fisher [Amer. Math. Monthly, 96 (1989), pp. 610 - 614] calculated the number of distinct words of length l assuming certain pairs of letters commute. In this paper we are interested in a more general setting where the pairs of letters that commute at a certain position of a word depend on the initial segment of the word. In particular, we show that if for each word at each position any letter fails to commute with at most a constant number of other letters, then the number of distinct words of length l is at most Cn+l for some constant C. We use this result to obtain a lower bound on the number of diagonal flips required in the worst case to transform one n-vertex labeled triangulated planar graph into some other one.