Robinson-Schensted correspondence for unit interval orders

Abstract

The Stanley-Stembridge conjecture associates a symmetric function to each natural unit interval order $\mathcal{P}$. In this paper, we define relations à la Knuth on the symmetric group for each $\mathcal{P}$ and conjecture that the associated $\mathcal{P}$-Knuth equivalence classes are Schur-positive, refining theorems of Gasharov, Brosnan-Chow, and Guay-Paquet. The resulting equivalence graphs fit into the framework of D graphs studied by Assaf. Furthermore, we conjecture that the Schur expansion is given by column-readings of $\mathcal{P}$-tableaux that occur in the equivalence class. We prove these conjectures for $\mathcal{P}$ avoiding two specific suborders by introducing $\mathcal{P}$-analog of Robinson-Schensted insertion, giving an answer to a long standing question of Chow.

56 pages, 53 figures. v2: added Proposition 4.10 and Theorem 6.1(D) about genuine P-heights