2020/03/26 by Dongkwan Kim, Kim, Dongkwan, Pavlo Pylyavskyy +1 · 1 citation
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2003.12123
openalex publication_date 2020/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.