Upper-Triangular Linear Relations on Multiplicities and the Stanley–Stembridge Conjecture

In 2015, Brosnan and Chow, and independently Guay-Paquet, proved the Shareshian–Wachs conjecture, which links the Stanley–Stembridge conjecture in combinatorics to the geometry of Hessenberg varieties. This link is made precise through Tymoczko’s permutation group action on the cohomology ring of regular semisimple Hessenberg varieties. In previous work, the authors exploited this con-nection to prove a graded version of the Stanley–Stembridge conjecture for a special case in which only irreducible representations of the permutation group indexed by partitions with at most two parts can appear. In this manuscript, we derive a new set of linear relations satisfied by the multiplicities of certain permutation representations in Tymoczko’s representation. We also show that these relations are upper-triangular in an appropriate sense and that they uniquely determine the multiplicities. As an application of these results, we prove an inductive formula for the multiplicity coefficients corresponding to partitions with a maximal number of parts.