Balister, Paul, Bollobás, Béla and Gerke, Stefanie (2008) Sequences with changing dependencies. SIAM Journal on Discrete Mathematics, 22 (3).
Full text access: Open
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.
This is a Approved version This version's date is: 2008 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/d0386152-3c8d-b105-62c0-dd80f347ae86/4/
Deposited by Research Information System (atira) on 27-Jan-2013 in Royal Holloway Research Online.Last modified on 27-Jan-2013