A composition method for neat formulas of chromatic symmetric functions

We use terminology from Stanley [25]. Let $n$ be a positive integer. A composition of $n$ is a sequence of positive integers with sum $n$, commonly denoted $I=i_{1}\dotsm i_{s}\vDash n$. It has size $\abs{I}=n$, length $\ell(I)=s$, and reversal $\overline{I}=i_{s}i_{s-1}\dotsm i_{1}$. The integers $i_{k}$ are called parts of $I$. For notational convenience, we write $I=v^{s}$ if all parts have the same value $v$, and denote the $k$th last part as $i_{-k}$; thus $i_{-1}=i_{s}$. We consider the number $0$ to have a unique composition, denoted $\epsilon$. Whenever a capital letter such like $I$ and $J$ is adopted to denote a composition, we use the small letter counterparts such as $i$ and $j$ respectively with integer subscripts to denote the parts. A factor of $I$ is a subsequence that consists of consecutive parts. A prefix (resp., suffix) of $I$ is a factor that starts from $i_{1}$ (resp., ends at $i_{s}$). Denote by $m_{k}(I)$ the the number of parts $k$ in $I$, namely,

A partition of $n$ is a multiset of positive integers with sum $n$, commonly denoted as

where $\lambda_{1}\geq\lambda_{2}\geq\dotsm\geq 1$. For any composition $I$, there is a unique partition $\rho(I)$ satisfying Eq. 1.3, i.e., the partition obtained by rearranging the parts of $I$. As partitions have Young diagrams as graphic representation, one uses the terminology ribbons to illustrate compositions. In French notation, the ribbon for a composition $I$ is the collection of boxes such that

• •

  Row $k$ consists of $i_{k}$ consecutive boxes, and

• •

  the last box on Row $k$ and the first box on Row $k+1$ are in the same column.

In the theory of integer partitions, by saying a Young diagram $\lambda$ one emphasizes the geometric shape of the partition $\lambda$. Being analogous in our composition calculus, we phrase the wording “a ribbon $I$” to call attention to the illustration of the composition $I$.

Following MacMahon [16], the conjugate $I^{\sim}$ of a composition $I$ is the ribbon consisting of the column lengths of $I$ from right to left. This is different to the conjugate $\lambda^{\prime}$ of a partition $\lambda$, whose Young diagram is obtained by turning rows into columns. For example, $32^{\sim}=121^{2}$ and $32^{\prime}=221$. A refinement of $I$ is a composition $J=j_{1}\dotsm j_{t}$ such that

for some integers $k_{0}<\dots<k_{s}$, where $k_{0}=0$ and $k_{s}=t$. We say that $I$ is a coarsement of $J$ if $J$ is a refinement of $I$. The reverse refinement order $\preceq$ for compositions is the partial order defined by

The first parts of blocks of $J$ with respect to $I$ are the numbers $j_{k_{0}+1},\dots,j_{k_{s-1}+1}$, with product

The last parts of blocks of $J$ with respect to $I$ are the numbers $j_{k_{1}},\dots,j_{k_{s}}$, with product

By definition, one may derive directly that

For any compositions $I=i_{1}\dotsm i_{s}$ and $J=j_{1}\dotsm j_{t}$, the concatenation of $I$ and $J$ is the composition $I\!J=i_{1}\dotsm i_{s}j_{1}\dotsm j_{t}$, and the near concatenation of $I$ and $J$ is the composition

In French notation, the ribbon $I\!J$ (resp., $I\triangleright J$) is obtained by attaching the first box of $J$ immediately below (resp., to the immediate right of) the last box of $I$.

The decomposition of a ribbon $J$ relatively to a composition $I$ is the unique expression

where $s=\ell(I)$, each $J_{k}$ is a ribbon of size $i_{k}$, and each symbol $\bullet_{k}$ stands for either the concatenation or the near concatenation. For instance,

We call the ribbons $J_{k}$ blocks of $\nabla_{I}(J)$. In the language of ribbons, the block $J_{k}$ consists of the first $i_{k}$ boxes of the ribbon that is obtained from $J$ by removing the previous blocks $J_{1},\dots,J_{k-1}$.

A hook is a ribbon of the form $1^{s}t$ for some $s\geq 0$ and $t\geq 1$. Every hook appears as the English letter L or a degenerate one, that is, a horizontal ribbon $t$ or a vertical ribbon $1^{s}$. Here we recognize the ribbon $1$ as horizontal. Denote by $\mathcal{H}_{I}$ the set of ribbons $J$ such that every block in the decomposition $\nabla_{I}(J)$ is a hook. Then

is the set of hooks of the composition $n$ consisting of a single part. Moreover, since every factor of a hook is still a hook, we have $\mathcal{H}_{n}\subseteq\mathcal{H}_{I}$ for all $I\vDash n$. For example, $\mathcal{H}_{4}=\{4,\ 13,\ 1^{2}2,\ 1^{4}\}$, $\mathcal{H}_{31}=\mathcal{H}_{4}\cup\{31,\ 121\}$, and $\mathcal{H}_{13}=\mathcal{H}_{4}\cup\{22,\ 21^{2}\}$. Let $I=i_{1}\dotsm i_{s}$. By definition, the set $\mathcal{H}_{I}$ is in a bijection with the set

where the symbol $\triangleleft$ stands for the concatenation operation. As a consequence, one may calculate $\abs{\mathcal{H}_{I}}=2^{s-1}i_{1}\dotsm i_{s}$.

We give an overview of necessary notion and notation for the theory of commutative symmetric functions. For comprehensive references, one may refer to Stanley [26] and Mendes and Remmel [18]. Let $R$ be a commutative ring with identity. A symmetric function of homogeneous degree $n$ over $R$ is a formal power series

such that $f(x_{1},x_{2},\dots)=f(x_{\pi(1)},x_{\pi(2)},\dots)$ for any permutation $\pi$. Denote by $\mathbb{Q}$ the field of rational numbers. Define $\operatorname{Sym}^{0}=\mathbb{Q}$, and define $\operatorname{Sym}^{n}$ to be the vector space of homogeneous symmetric functions of degree $n$ over $\mathbb{Q}$. Common bases of $\mathrm{Sym}^{n}$ include the elementary symmetric functions $e_{\lambda}$, the complete homogeneous symmetric functions $h_{\lambda}$, the power sum symmetric functions $p_{\lambda}$, and the Schur symmetric functions $s_{\lambda}$. The first three ones are multiplicatively defined by

where

The Schur symmetric function $s_{\lambda}$ can be defined combinatorially by $s_{\lambda}=\sum_{T\in\mathrm{CS}_{\lambda}}w(T)$, where $\mathrm{CS}_{\lambda}$ is the set of column strict tableaux of shape $\lambda$, and the weight $w(T)$ is the product of $x_{i}$ for all entries $i$ in $T$. Here a tableau of shape $\lambda$ is said to be column strict if

• •

  the entries in each row weakly increase, and

• •

  the entries in each column strictly increase starting from the longest row; this is to say from bottom to top in French notation.

The Schur symmetric functions are said to be “the most important basis for $\mathrm{Sym}$ with respect to its relationship to other areas of mathematics” and “crucial in understanding the representation theory of the symmetric group,” see [18, Page 37].

For any basis $\{b_{\lambda}\}$ of $\mathrm{Sym}^{n}$ and any symmetric function $f\in\mathrm{Sym}^{n}$, the $b_{\lambda}$-coefficient of $f$ is the unique number $c_{\lambda}$ such that $f=\sum_{\lambda\vdash n}c_{\lambda}b_{\lambda}$, denoted $[b_{\lambda}]f=c_{\lambda}$. The symmetric function $f$ is said to be $b$-positive if every $b$-coefficient of $f$ is nonnegative. For instance, every elementary symmetric function is Schur positive since $e_{\lambda}=\sum_{\mu\vdash\abs{\lambda}}K_{\mu^{\prime}\lambda}s_{\mu}$, where $K_{\mu^{\prime}\lambda}$ are Kostka numbers, see [18, Exercise 2.12].

With the aid of the function $\rho$ defined by Eq. 1.3, one may extend the domain of these basis symmetric functions from partitions to compositions. Precisely speaking, one may define $b_{I}=b_{\rho(I)}$ for any composition $I$ and any basis $\{b_{\lambda}\}_{\lambda}$. With this convention, we are safe to write $e_{I}$ instead of the redundant expression $e_{\rho(I)}$. Since $\{e_{I}\}_{I\vDash n}$ is not a basis of $\mathrm{Sym}^{n}$, the notation $[e_{I}]f$ is undefined.

Stanley [23] introduced the chromatic symmetric function for a graph $G$ as

where $\mathbf{x}=\left(x_{1},x_{2},\ldots\right)$ is a countable list of indeterminates, and $\kappa$ runs over proper colorings of $G$. Chromatic symmetric functions are particular symmetric functions, and it is a generalization of Birkhoff’s chromatic polynomials $\chi_{G}(k)$, since $X_{G}(1^{k}00\dotsm)=\chi_{G}(k)$. For instance, the chromatic symmetric function of the complete graph $K_{n}$ is

We will need the $p$-expansion of $X_{G}$, see [23, Theorem 2.5].

By [18, Theorem 2.22], every $e$-coefficient in a power sum symmetric function $p_{\mu}$ is an integer. It then follows from Proposition 2.1 that every $e$-coefficient of $X_{G}$ is integral. Stanley [23, Corollary 3.6] presented the following quick criterion for the $e$-positivity.

Such graphs have several characterizations, such as the complements of bipartite graphs and the incomparability graphs of $3$-free posets, see Guay-Paquet [12, Theorem 5.3]. Stanley [23, Propositions 5.3 and 5.4] confirmed the $e$-positivity of paths and cycles.

Explicit formulas for the $e$-coefficients of $X_{P_{n}}$ and $X_{C_{n}}$ were obtained by extracting the coefficients of these generating functions, see Wolfe [32, Theorem 3.2]. Shareshian and Wachs [22] obtained the much simpler Eq. 1.1 for paths. Ellzey [6, Corollary 6.2] gave a formula for the chromatic quasisymmetric function of cycles, whose $t=1$ specialization is an equally simple one.

We provide a proof for Proposition 2.4 using the composition method in Appendix A. Orellana and Scott [19, Theorem 3.1, Corollaries 3.2 and 3.3] established the triple-deletion property for chromatic symmetric functions.

For an introduction and basic knowledge on noncommutative symmetric functions, see Gelfand et al. [11]. Let $K$ be a field of characteristic zero. The algebra of noncommutative symmetric functions is the free associative algebra $\mathrm{NSym}=K\langle\Lambda_{1},\Lambda_{2},\dots\rangle$ generated by an infinite sequence $\{\Lambda_{k}\}_{k\geq 1}$ of indeterminates over $K$, where $\Lambda_{0}=1$. It is graded by the weight function $w(\Lambda_{k})=k$. The homogeneous component of weight $n$ is denoted $\mathrm{NSym}_{n}$. Let $t$ be an indeterminate that commutes with all indeterminates $\Lambda_{k}$. The elementary symmetric functions are $\Lambda_{n}$ themselves, whose generating function is denoted by

The complete homogeneous symmetric functions $S_{n}$ are defined by the generating function

The power sum symmetric functions $\Psi_{n}$ of the first kind are defined by the generating function

For any composition $I=i_{1}i_{2}\dotsm$, define

The algebra $\mathrm{NSym}$ is freely generated by any one of these families. Here the superscript notation are adopted to indicate that the functions are multiplicative with respect to composition concatenations. The sign of $I$ is defined by

It is direct to check that

Another linear basis of $\mathrm{NSym}$ is the ribbon Schur functions $R_{I}$, which can be defined by

see [11, Formula (62)]. We list some transition rules for these bases, see [11, Propositions 4.15 and 4.23, and Note 4.21].

Equation 2.7 is true by virtue of Eq. 2.2, though it was expressed in terms of the product $lp(J,I)$ in [11]. Recall from Eq. 1.3 that $\rho$ maps a composition to its underlying partition. We use the same notation $\rho$ to denote the projection map defined by $\rho(\Lambda^{I})=e_{I}$ and by extending it linearly. By definition, for any composition $I$,

where $\mathrm{sh}(I)$ is the skew partition of shape $I$. For instance,

When $\rho(F)=f$ for some $F\in\mathrm{NSym}$ and $f\in\mathrm{Sym}$, we say that $f$ is the commutative image of $F$, and that $F$ is a noncommutative analog of $f$. For instance, Eqs. 1.1 and 2.4 imply that $X_{P_{n}}$ and $X_{C_{n}}$ have the noncommutative analogs

respectively. If a chromatic symmetric function $X_{G}$ has a noncommutative analog $\widetilde{X}_{G}\in\mathrm{NSym}$, then for any partition $\lambda\vdash\abs{V(G)}$,

The aforementioned ambiguity issue is solved naturally in the language of the algebra $\mathrm{NSym}$. Indeed, since $\{\Lambda^{I}\}_{I\vDash n}$ is a basis of $\mathrm{NSym}_{n}$, we talk about the well defined $\Lambda^{I}$-coefficients instead of the undefined “$e_{I}$-coefficients”.

By definition, any chromatic symmetric function has an infinite number of noncommutative analogs, among which only a finite number with integer coefficients are $e$-positive. In particular, if a symmetric function $\sum_{\lambda\vdash n}c_{\lambda}e_{\lambda}$ is $e$-positive, then the analog $\sum_{\lambda\vdash n}c_{\lambda}\Lambda^{\lambda}$ is $\Lambda$-positive. Therefore, a symmetric function is $e$-positive if and only if it has a $\Lambda$-positive noncommutative analog. Therefore, in order to prove that a graph $G$ is $e$-positive, it suffices to find a $\Lambda$-positive analog of $X_{G}$. The algebra $\mathrm{NSym}$ plays the role of providing theoretical support for the composition method. As a consequence, we display only positive $e_{I}$-expansions in theorem statements. We would not write in terms of noncommutative analogs except when arguing $\Lambda^{I}$-coefficients is convenient.

This section consists of a property of the function $w_{I}$ defined by Eq. 1.2, some other composition functions and their interrelations, as well as some practices of using these functions.

From definition, it is straightforward to see that $w_{I}=w_{J}$ for any composition $J$ that is obtained by rearranging the non-first parts of $I$. Another five-finger exercise is as follows.

For any number $a\leq\abs{I}$, we define the surplus partial sum of $I$ with respect to $a$ to be the number

Define the $a$-surplus of $I$ to be the number

Then $\Theta_{I}^{+}(a)\geq 0$. The function $\Theta_{I}^{+}(\cdot)$ will appear in Theorem 3.3. Here is a basic property.

Lemma 2.8 will be used in the proof of Theorem 3.10. Similarly, for any number $a\geq 0$, we define the deficiency partial sum of $I$ with respect to $a$ to be the number

and define the $a$-deficiency of $I$ to be the number

Then $\Theta_{I}^{-}(a)\geq 0$. The function $\sigma^{-}_{I}$ (resp., $\Theta^{-}_{I}$) can be expressed in terms of $\sigma^{+}_{I}$ (resp., $\Theta^{+}_{I}$).

Lemma 2.9 will be used in the proof of Theorem 3.9. Let us express the product $X_{P_{l}}X_{C_{m}}$ in terms of the functions $w_{I}$ and $\Theta_{I}^{+}(\cdot)$.

Note that neither of Eqs. 2.18 and 2.19 holds for $l=0$. Now we compute a partial convolution of $X_{P_{l}}$ and $X_{C_{m}}$.

We need the noncommutative setting in the proof above since the coefficient of $w_{K}\Lambda^{K}$ is considered. Lemma 2.11 will be used in the proof of Theorem 3.3 for tadpoles.

It can be shown alternatively by taking $m=n-1$ in Eq. 2.21 and using Proposition 2.4 and the identity $\Theta_{\overline{I}}^{-}(n-1)=n-i_{1}$, or, by Proposition 2.3.

In view of Eq. 2.6, if a noncommutative symmetric function $F$ is $\Lambda$-positive, then it is $R$-positive. Thibon and Wang [28] discovered that the analog $\widetilde{X}_{P_{n}}$ has the rather simple ribbon expansion

We present a $\Psi$-expansion for a noncommutative analog of cycles.