Toward Lower Bounds for Chromatic Symmetric Functions in the Elementary Basis

Abstract

Tatsuyuki Hikita recently proved the Stanley--Stembridge conjecture using probabilistic methods, showing that the chromatic symmetric functions of unit interval graphs are $e$-positive. Finding a combinatorial interpretation for these $e$-coefficients remains a major open problem. One approach is to look for combinatorial interpretations which are subsets of Gasharov's $P$-tableaux. Towards this goal, we introduce sets of strong and powerful $P$-tableaux, and use them to find combinatorial interpretations for various $e$-coefficients of the chromatic symmetric function $X_{inc(P)}(\mathbf{x},q)$. We conjecture that the set of strong $P$-tableaux gives a lower bound for the $e$-coefficients of $X_{inc(P)}(\mathbf{x},q)$. Additionally, we show that strong $P$-tableaux and the Shareshian--Wachs inversion statistic appear naturally in the proof of Hikita's result.

In a previous version, we conjectured that powerful $P$-tableaux give an upper bound for the $e$-coefficients of chromatic symmetric functions of incomparability graphs of natural unit interval orders. An anonymous reviewer showed that the poset corresponding to the reverse Hessenberg function (0,0,1,1,2,3,4,6) gives a counterexample to this conjecture