Abstract
In 1995, Stanley introduced the chromatic symmetric function of a graph, a symmetric function analog of the classical chromatic polynomial of a graph. The Stanley-Stembridge e-positivity conjecture is a long-standing conjecture that states that the chromatic symmetric function of a certain class of graphs, called incomparability graphs of (3+1)-free posets, has nonnegative coefficients when expanded in the elementary symmetric function basis. In 1996, Gasharov described Schur expansion of the chromatic symmetric function for this class of graphs in terms of P-tableau, a generalization of a standard Young tableau. An open problem is to find a bijective proof of this expansion for all (3+1)-free posets.
In the first part of the dissertation, we consider the problem of finding a bijection that looks like the classical RSK algorithm. The RSK algorithm takes (generalized) permutations and produces a pair of tableaux. Our approach is to view proper colorings as generalized permutations. This allows us to construct an algorithm that takes proper colorings and produce a pair of tableaux for certain classes of posets (3-free posets and beastly posets). This then provides a combinatorial proof of Gasharov's Schur expansion of the chromatic symmetric function as well as the Shareshian--Wachs Schur expansion of the chromatic quasisymmetric function for these classes of posets. We also consider proper set colorings as well as dual algorithms. In fact, we show that any RSK-like algorithm on permutations that preserves descents and inversions can be extended to a bijection on colorings using our general framework of viewing proper colorings as generalized permutations.
In the second part of the dissertation, we provide new proofs of results surrounding the Shareshian--Wachs chromatic quasisymmetric function. These include a new proof of a Harada--Precup recurrence relation for the e-coefficients through speicial rim hook tableaux as well as a simplified approach to Hwang's refinement of the chromatic quasisymmetric functions through local flips of acyclic orientations.