Séminaire Lotharingien de Combinatoire, 89B.82 (2023), 12 pp.

Kyle Celano

RSK for 3-Free Posets

Abstract. A long-standing open problem is to find an RSK-like correspondence between permutations and pairs of tableaux coming from Gasharov’s decomposition of Stanley’s chromatic symmetric functions into Schur functions. In this, we present such a correspondence RSK_P for incomparability graphs of 3-free posets P that moreover preserve the descent and inversion statistics. We then extend RSK_P to bijections from proper colorings and multicolorings providing new combinatorial proofs for the Schur expansions of Gasharov for the chromatic symmetric function, of Shareshian--Wachs for the chromatic quasisymmetric function, and of Hwang for the multichromatic quasisymmetric function, and its refinement to equivalence classes of acyclic orientations in the case that P is 3-free.

Received: November 15, 2022. Accepted: February 20, 2023. Final version: April 1, 2023.

The following versions are available:

PDF (211 K)
TeX version