Robinson–Schensted correspondence for unit interval orders

The Stanley–Stembridge conjecture associates a symmetric function to each natural unit interval order P. In this paper, we define relations à la Knuth on the symmetric group for each P and conjecture that the associated P-Knuth equivalence classes are Schur-positive, refining theorems of Gasharov, Brosnan-Chow, Guay-Paquet, and Shareshian-Wachs. 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 P-tableaux that occur in the equivalence class. We prove these conjectures for P avoiding two specific suborders by introducing P-analog of Robinson–Schensted insertion, giving an answer to a long standing question of Chow.