Patterns of Negative Shifts and Signed Shifts

Kassie Archer ; Sergi Elizalde ; Katherine Moore

Séminaire lotharingien de combinatoire, 78B (2017)

Résumé

Given a function f from a linearly ordered set X to itself, we say that a permutation π is an allowed pattern of f if the relative order of the first n iterates of f beginning at some x in X is given by π. We give a characterization of the allowed patterns of signed shifts in terms of monotone runs of a certain transformation of π, which completes and simplifies the original characterization given by Amigó. Signed shifts, which are generalizations of the shift map where some slopes are allowed to be negative, are particularly well-suited to a combinatorial analysis. In the special case where all the slopes are negative, we give an exact formula for the number of allowed patterns. Finally, we obtain a combinatorial derivation of the topological entropy of signed shifts.