Strictly increasing and decreasing sequences in subintervals of words

Graph Theory Seminar
Tuesday, March 14, 2023 - 3:45pm for 1 hour (actually 50 minutes)
Skiles 005
Jonathan Bloom – Lafayette College – bloomjs@lafayette.edu
Tom Kelly

In this talk we discuss our proof of a recent conjecture of Guo and Poznanovi\'{c} 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$.  (It will be noted that similar and well-studied correspondences like RSK insertion and Hecke insertion fail in this regard.) To define our correspondence we make use of Thomas and Yong's K-infusion operator and then use it to obtain the bijections that prove the conjecture of Guo and Poznanovi\'{c}.    (Joint work with D. Saracino.)