Strictly increasing and decreasing sequences in subintervals of words and a conjecture of Guo and Poznanović

Abstract

We prove a conjecture of Guo and Poznanović concerning chains in certain 01-fillings of moon polyominoes. A key ingredient of our proof is a correspondence between words $w$ and pairs $(\mathcal{W}(w),\mathcal{M}(w))$ of increasing tableaux such that $\mathcal{M}(w)$ determines the lengths of the longest strictly increasing and strictly decreasing sequences in every subinterval of $w$. We define this correspondence by using Thomas and Yong's K-infusion operator and then use it to obtain the bijections that prove the conjecture of Guo and Poznanović. In constructing our bijections we introduce new variants of the RSK correspondence and Knuth equivalence.

36 pages