Robinson–Schensted correspondence for unit interval orders

Dongkwan Kim, Pavlo Pylyavskyy

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish (US)
Article number97
JournalSelecta Mathematica, New Series
Issue number5
StatePublished - Nov 2021

Bibliographical note

Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Nature Switzerland AG.


Dive into the research topics of 'Robinson–Schensted correspondence for unit interval orders'. Together they form a unique fingerprint.

Cite this