Publication Date

2018-05-04

Availability

Open access

Embargo Period

2018-05-04

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PHD)

Department

Mathematics (Arts and Sciences)

Date of Defense

2018-03-27

First Committee Member

Michelle L. Wachs

Second Committee Member

Richard P. Stanley

Third Committee Member

Bruno Benedetti

Fourth Committee Member

Rafael Nepomechie

Abstract

In 1912, Birkhoff introduced the chromatic polynomial of a graph, which counts the number of proper colorings of a graph. In 1995, Stanley introduced the chromatic symmetric function of a graph, a symmetric function analog of the chromatic polynomial of a graph. The Stanley-Stembridge e-positivity conjecture is a longstanding conjecture that states that the chromatic symmetric function of a certain class of graphs has nonnegative coefficients when expanded in the elementary symmetric function basis. In 2012, Shareshian and Wachs introduced the chromatic quasisymmetric function of a labeled graph, a refinement of the chromatic symmetric function. Shareshian and Wachs described their own e-positivity conjecture for chromatic quasisymmetric functions which generalizes the Stanley-Stembridge conjecture. There is ample support for these e-positivity conjectures, including weaker positivity results in other symmetric function bases. In the first part of this thesis, we extend the work of Shareshian and Wachs from labeled graphs to a wider class of graphs, namely directed graphs. We introduce the notion of chromatic quasisymmetric function of a directed graph. For acyclic digraphs, our definition is equivalent to that of Shareshian and Wachs. We give an expansion in terms of Gessel’s fundamental quasisymmetric function basis for the chromatic quasisymmetric function of all digraphs, which shows that all the coefficients are nonnegative. We use this expansion to derive a power sum symmetric function basis expansion with positive coefficients for the chromatic quasisymmetric function of all digraphs whose chromatic quasisymmetric function has symmetric function coefficients. We describe a class of digraphs, which we call circular indifference digraphs, and show that their chromatic quasisymmetric functions are symmetric. These circular indifference digraphs include the directed cycle, for which we provide an e-basis generating function formula that shows that its chromatic quasisymmetric function is e-positive. We generalize the e-positivity conjecture of Shareshian and Wachs to the class of circular indifference digraphs. Our positivity results and computer calculations provide evidence for this conjecture. A Smirnov word is a word over the positive integers such that consecutive letters are distinct. The descent enumerator of Smirnov words is equivalent to the chromatic quasisymmetric function of the path graph. Shareshian and Wachs found a nice ebasis generating function expansion of this descent enumerator that shows that it is e-positive. Specializing this result gave them a q-analog of Euler’s exponential generating function of the classical Eulerian polynomials. In the second part of this thesis, we consider descent enumerators for restricted Smirnov words, where we put restrictions on the relationship between the first and last letter. We also consider cyclic descent enumerators for Smirnov words. Our work on these descent enumerators refines our work on the chromatic quasisymmetric function of the directed cycle. We obtain nice e-basis generating function formulas that show that some of these descent enumerators are e-positive. We also provide expansions for the various descent enumerators in Gessel’s fundamental quasisymmetric function basis. By specializing our fundamental and e-basis expansions, we obtain formulas for polynomials that are variations on the q-Eulerian polynomials studied by Shareshian and Wachs. We give a factorization of the expansion coefficients of the various descent enumerators in the power sum symmetric function basis involving the Eulerian polynomials. In addition, this work with Smirnov word descent enumerators enables us to derive an e-basis expansion formula for the chromatic quasisymmetric function of the labeled cycle, which shows that it is e-positive. This is notable, because the labeled cycle is not a graph that is covered by any of the current e-positivity conjectures.

Keywords

symmetric function; graph coloring; chromatic polynomial; directed graphs

Share

COinS