# A categorification of the chromatic symmetric polynomial

Radmila Sazdanović, Martha Yip

► To cite this version:

Radmila Sazdanović, Martha Yip. A categorification of the chromatic symmetric polynomial. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.631-642, 10.46298/dmtcs.2527. hal-01337787

HAL Id: hal-01337787

https://hal.science/hal-01337787

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A categorification of the chromatic symmetric polynomial

Radmila Sazdanović<fnref n="1" />†and Martha Yip<fnref n="2" />‡

**Abstract.** The Stanley chromatic symmetric polynomial of a graph $G$ is a symmetric function generalization of the chromatic polynomial, and has interesting combinatorial properties. We apply the techniques of Khovanov homology to construct a homology $H_*(G)$ of graded $\mathfrak{S}_n$-modules, whose bigraded Frobenius series $\text{Frob}_G(q, t)$ reduces to the chromatic symmetric polynomial at $q = t = 1$. We also obtain analogues of several familiar properties of the chromatic symmetric polynomials in terms of homology.

**Résumé.** Le polynôme chromatique symétrique d'un graphe $G$ est une généralisation par une fonction symétrique du polynôme chromatique, et possède des propriétés combinatoires intéressantes. Nous appliquons les techniques de l'homologie de Khovanov pour construire une homologie $H_*(G)$ de modules gradués $\mathfrak{S}_n$, dont la série bigraduée de Frobeniusse $\text{Frob}_G(q, t)$ réduit au polynôme chromatique symétrique à $q = t = 1$. Nous obtenons également des analogies pour plusieurs propriétés connues des polynômes chromatiques en termes d'homologie.

**Keywords:** symmetric functions, chromatic polynomial, Khovanov homology, $\mathfrak{S}_n$-modules, Frobenius series, graph colouring

## 1 Introduction

Let $G$ be a graph with vertex set $V(G) = \{v_1, \dots, v_n\}$ and edge set $E(G)$. A proper colouring of $G$ is a function $\kappa: V(G) \to \mathbb{N}$ such that $\kappa(v_i) \neq \kappa(v_j)$ if an edge is incident to both $v_i$ and $v_j$.

**Definition 1** The chromatic symmetric polynomial of $G$ is

$$X_G(\mathbf{x}) = X_G(x_1, x_2, \dots) = \sum_{\kappa} x_{\kappa(v_1)} \cdots x_{\kappa(v_n)}, \qquad (1)$$

where the sum is over all proper colourings $\kappa: V(G) \to \mathbb{N}$.

<footnote n="1">¹Department of Mathematics, North Carolina State University</footnote>

<footnote n="2">²Department of Mathematics, University of Kentucky</footnote>

<footnote>†Email: rsazdanovic@math.ncsu.edu</footnote>

<footnote>‡Email: martha.yip@uky.edu</footnote>
The polynomial $X_G$ is a generalization of the chromatic polynomial $\chi_G$ in the sense that $X_G(1^k) = \chi_G(k)$ (Stanley, 1995, Proposition 2.2).

The polynomial $X_G$ is also a symmetric function (we refer the reader to Macdonald (1995) for background material on symmetric functions). Following the standard notation used by Macdonald, let $p_\lambda$ and $s_\lambda$ denote the power sum symmetric functions and the Schur functions, respectively. Given a subset of edges $F \subseteq E(G)$, its partition type $\lambda(F)$ is the partition associated to the sizes of the connected components of the subgraph of $G$ induced by the edge set $F$. The following formula (Stanley, 1995, Theorem 2.5) can be proved by an inclusion-exclusion argument.

$$X_G = \sum_{F \subseteq E(G)} (-1)^{|F|} p_{\lambda(F)}. \qquad (2)$$

This formula forms the basis of our categorification process.

Categorification can be thought as a way of replacing an $n$-category by an $(n+1)$-category; for example, lifting the Euler characteristic of a topological space to its homology. One of the most successful recent examples of categorification include Khovanov (2000) link homology, which is a new kind of link invariant that lifts the properties of the Jones polynomial and carries a rich algebraic structure. In this theory, every link is assigned bigraded homology groups whose Euler characteristic is the Jones polynomial, and additionally, link cobordisms are assigned homomorphisms of homology groups. This categorification has been successfully used in determining topological properties of knots, and give a purely combinatorial proof of the Milnor conjecture, also known as Kronheimer-Mrowka theorem.

Chromatic graph homology, developed by Helme-Guizon and Rong (2005), is one of several categorifications of polynomial graph invariants. The construction follows that of Khovanov; a bigraded homology theory is associated to a graph and a commutative graded algebra in a way that its graded Euler characteristic is the value of the chromatic polynomial at the $q$-dimension of the algebra. There are other categorifications of the chromatic polynomial, and many of them possess a long exact sequence of homology that lifts the deletion-contraction formula for the chromatic polynomial, in the same vein that Khovanov homology lifts the skein relations for the Jones polynomial.

In this paper we apply a Khovanov-type construction to the chromatic symmetric polynomial. This process is described in Section 2. Every spanning subgraph of $G$ is assigned a graded $\mathbb{S}_n$-module, leading to a chain complex whose differential maps are defined based on the Boolean lattice structure of the set of spanning subgraphs of $G$. The Frobenius series $\text{Frob}_G(q, t)$ of the resulting bigraded homology (which we call the chromatic symmetric homology, or the Khovanov-Stanley homology) specializes to the chromatic symmetric polynomial, naturally expressed in the Schur basis (Theorem 9).

In Section 3, we give the analogues of several familiar properties of the chromatic symmetric polynomial on the categorified level. In particular, we consider the homology of graphs which contain a loop or multiple edges, and the homology of a disjoint union of graphs.

Unlike the chromatic polynomial $\chi_G$, the chromatic symmetric polynomial $X_G$ does not satisfy a deletion-contraction formula, but as Orellana and Scott (2014) and Guay-Paquet (2013) have recently shown, if $G$ contains a 3-cycle, then $X_G$ satisfies a recursive formula involving the deletion of two of the edges of the 3-cycle. We present the analogous result (Theorem 15), which lifts the recursive formula for $X_G$ to a long exact sequence in homology, and in Section 4, we illustrate this result for the triangle graph.

To conclude, we provide computations of homology for small graphs in Section 5. Finally, it is our hope that Khovanov-Stanley homology will be useful in addressing open problems regarding the chromatic
symmetric polynomial, such as the characterization of graphs whose $X_G$ is Schur-positive (Gasharov (1996)), and whether $X_G$ is a complete invariant for trees (Martin et al. (2008)). Also, we hope that this construction may shed light on the chromatic quasisymmetric function of Shareshian and Wachs (2014).

# 2 The construction

## 2.1 The states

Let $G$ be a graph with vertex set $V(G) = \{v_1, \dots, v_n\}$ and edge set $E(G) = \{e_1, \dots, e_m\}$.

**Definition 2** A state of $G$ is a spanning subgraph with a subset of edges $F \subseteq E(G)$. Let $|F|$ denote the number of edges in $F$.

A graph with $m$ edges has $2^m$ states. We identify a state $F$ with the binary string $z_F = z_1 \cdots z_n$ where

$$z_i = \begin{cases} 0, & \text{if } e_i \in F, \\ 1, & \text{if } e_i \notin F. \end{cases}$$

The states of $G$ form a Boolean lattice $Q(G)$; that is, in the Hasse diagram of $Q(G)$, there is an edge from a state $F$ to a state $F'$ if and only if their associated binary strings differ in exactly one position. The lattice $Q(G)$ is graded by the number of edges in the states.

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** The eight states of $K_3$ and their signed per-edge maps.</figcaption></figure>

## 2.2 The graded modules

We shall assign a graded $\mathfrak{S}_n$-module to each state. Let $S^\lambda$ denote the irreducible $\mathfrak{S}_n$-module indexed by the partition $\lambda$. (We refer the reader to Fulton (1997) for background on representations of the symmetric
group.) For $a \in \mathbb{N}$, let $\mathcal{L}_a$ denote the graded $\mathfrak{S}_n$-module

$$ \mathcal{L}_a = \bigoplus_{i=0}^{a-1} S^{(a-i, 1^i)}. \qquad (3) $$

Since $\wedge^i S^{(a-1,1)} \cong S^{(a-i,1^i)}$, we may also think of $\mathcal{L}_a$ as the exterior algebra $\wedge^* S^{(a-1,1)}$.

Suppose $F \subseteq E(G)$ is a state with $r$ connected components $B_1, \dots, B_r$ of sizes $b_1, \dots, b_r$ respectively. To $F$, we assign the graded $\mathfrak{S}_n$-module

$$ \mathcal{M}_F = \mathrm{Ind}_{\mathfrak{S}_{B_1} \times \dots \times \mathfrak{S}_{B_r}}^{\mathfrak{S}_{V(G)}} (\mathcal{L}_{b_1} \otimes \dots \otimes \mathcal{L}_{b_r}), \qquad (4) $$

where $\mathfrak{S}_{B_1} \times \dots \times \mathfrak{S}_{B_r}$ is a Young subgroup of $\mathfrak{S}_{V(G)} \cong \mathfrak{S}_n$. For the sake of simpler notation, we will sometimes use the shorthand

$$ \mathrm{Ind}_{B_1 | \dots | B_r} = \mathrm{Ind}_{\mathfrak{S}_{B_1} \times \dots \times \mathfrak{S}_{B_r}}^{\mathfrak{S}_{V(G)}}. \qquad (5) $$

<figure><img src="image_3.png" /><figcaption>Fig. 2: The graded $\mathfrak{S}_3$-modules corresponding to the states of $K_3$.</figcaption></figure>
## 2.3 The per-edge maps

For each edge $\varepsilon$ in the Hasse diagram of $Q(G)$ from a state $F$ to a state $F'$, we shall define a graded $\mathfrak{S}_n$-module morphism $d_\varepsilon : \mathcal{M}_F \to \mathcal{M}_{F'}$. These are the per-edge maps.

Suppose the binary strings $z_F$ and $z_{F'}$ differ in the jth position. Identify $\varepsilon$ with the sequence $\varepsilon_1 \cdots \varepsilon_m$ defined by $\varepsilon_j = \ast$, and $\varepsilon_i = (z_F)_i = (z_{F'})_i$ for $i \neq j$. See Figure 1 for an example.

To define the per-edge maps $d_\varepsilon$, there are two cases to consider. Suppose $F' = F - e$ where $e \in E(G)$. **Case 1.** the edge $e$ is incident to vertices from the same connected component of $F'$. Since $\mathcal{M}_F$ and $\mathcal{M}_{F'}$ are canonically isomorphic, we define $d_\varepsilon : \mathcal{M}_F \to \mathcal{M}_{F'}$ to be the identity map on $\mathcal{M}_F$.

**Case 2.** the edge $e$ is incident to vertices from different connected components of $F'$. First consider the case where $F$ consists of one connected component, and $F'$ consists of two connected components $A$ and $B$. Suppose $|A| = a$ and $|B| = b$, so that $a + b = n$. Then

$$ \mathcal{M}_F = \mathcal{L}_n = \bigoplus_{k=0}^{n-1} S^{(n-k, 1^k)}, $$

$$ \mathcal{M}_{F'} = \operatorname{Ind}_{\mathfrak{S}_A^n \times \mathfrak{S}_B} (\mathcal{L}_a \otimes \mathcal{L}_b) = \bigoplus_{k=0}^{n-2} \bigoplus_{i+j=k} \operatorname{Ind}_{\mathfrak{S}_A^n \times \mathfrak{S}_B} (S^{(a-i, 1^i)} \otimes S^{(b-j, 1^j)}). $$

Observe that since $i \le a-1$ and $j \le b-1$, then $i+j \le a+b-2=n-2$, so our goal is to define maps $d_\varepsilon$ for $0 \le k \le n-2$:

$$ \begin{array}{ccc} \mathcal{M}_F: & \begin{array}{c} S^{(n)} \\ \downarrow d_\varepsilon \end{array} \longrightarrow \begin{array}{c} S^{(n-1,1)} \\ \downarrow d_\varepsilon^0 \end{array} \longrightarrow \dots \longrightarrow \begin{array}{c} S^{(2,1^{n-2})} \\ \downarrow d_\varepsilon^{n-2} \end{array} \longrightarrow \begin{array}{c} S^{(1^n)} \\ \downarrow 0 \end{array} & \\ \mathcal{M}_{F'}: & (\mathcal{M}_{F'})_0 \longrightarrow (\mathcal{M}_{F'})_1 \longrightarrow \dots \longrightarrow (\mathcal{M}_{F'})_{n-2} \longrightarrow 0 \end{array} $$

Let $\alpha_i = (a-i, 1^i)$ and $\beta_j = (b-j, 1^j)$. The $k$th grading of the module $\mathcal{M}_{F'}$ is

$$ (\mathcal{M}_{F'})_k = \bigoplus_{i=\min(0, k-(b-1))}^{\min(a-1, k)} \operatorname{Ind}_{\mathfrak{S}_A^n \times \mathfrak{S}_B} (S^{\alpha_i} \otimes S^{\beta_{k-i}}). \qquad (6) $$

By the Littlewood-Richardson rule (see for example (Fulton, 1997, §5.2 Corollary 3)),

$$ \operatorname{Ind}_{\mathfrak{S}_A^n \times \mathfrak{S}_B} (S^{\alpha_i} \otimes S^{\beta_{k-i}}) \cong S^{(n-k, 1^k)} \oplus \mathcal{U}, \qquad (7) $$

where $\mathcal{U}$ does not contain factors isomorphic to $S^{(n-k, 1^k)}$. Thus, to be precise,

$$ (\mathcal{M}_{F'})_k \cong (S^{(n-k, 1^k)})^{\oplus m_k} \oplus \mathcal{V}, \qquad (8) $$

where $m_k = \min(a-1, k) - \max(k - (b-1), 0) + 1$, and $\mathcal{V}$ does not contain factors isomorphic to $S^{(n-k, 1^k)}$. Therefore, for $0 \le k \le n-2$, we define

$$ d_{\varepsilon}^{k} : S^{(n-k, 1^k)} \to S^{(n-k, 1^k)} \oplus^{m_k} \mathcal{V} : x \mapsto \underbrace{(x, \dots, x, \mathbf{0}_{\mathcal{V}})}_{m_k}, \quad \text{and} \quad d_{\varepsilon} = \bigoplus_{k \ge 0} d_{\varepsilon}^{k}. \qquad (9) $$
See section 5.1 for an example.

It remains to consider the general case where $F$ has more than one connected component. The definition of the per-edge map in this case is achieved through induction of the two component case; the map on the components not joined by $e$ shall be the identity.

Suppose $F$ is a state with $r$ connected components $B_1, \dots, B_r$ of sizes $b_1, \dots, b_r$. Further suppose that the removal of the edge $e \in E(G)$ decomposes $B_r$ into two components $A$ and $B$ of sizes $a$ and $b$ respectively. Let $d_\zeta : \mathcal{L}_{a+b} \to \mathrm{Ind}_{\mathcal{S}_{A} \times \mathcal{S}_{B}}^{\mathcal{S}_{B_r}} (\mathcal{L}_a \otimes \mathcal{L}_b)$ be the per-edge map defined previously, and let $\mathcal{N} = \mathcal{L}_{b_1} \otimes \dots \otimes \mathcal{L}_{b_{r-1}}$. The map $d_\epsilon : \mathcal{M}_F \to \mathcal{M}_{F'}$ is chosen to be

$$d_{\epsilon} = \mathrm{Ind}_{\mathcal{S}_{B_1} \times \dots \times \mathcal{S}_{B_{r-1}} \times \mathcal{S}_{B_r}}^{\mathcal{S}_{V(G)}} (\mathrm{id}_{\mathcal{N}} \otimes d_{\zeta}). \quad (10)$$

**Definition 3** If an edge $\epsilon = \epsilon_1 \cdots \epsilon_m$ in the Hasse diagram of $Q(G)$ has $k$ ones after the * entry, then the signed per-edge map that corresponds to $\epsilon$ is

$$\mathrm{sgn}(\epsilon)d_{\epsilon} = (-1)^k d_{\epsilon}. \quad (11)$$

## 2.4 The chain complex of graded modules

Now that we have assigned a graded $\mathcal{S}_n$-module $\mathcal{M}_F$ to each state $F$ of $G$, and defined signed per-edge maps, we can make the following definitions.

**Definition 4** For $i \ge 0$, the $i$th chain module for $G$ is

$$C_i(G) = \bigoplus_{|F|=i} \mathcal{M}_F. \quad (12)$$

More precisely, since $\mathcal{M}_F = \bigoplus_{j \ge 0} (\mathcal{M}_F)_j$ is graded, then for $i, j \ge 0$, we can define

$$C_{i,j}(G) = \bigoplus_{|F|=i} (\mathcal{M}_F)_j. \quad (13)$$

**Definition 5** For $i \ge 0$, define $d_i : C_i(G) \to C_{i-1}(G)$ by

$$d_i = \sum_{\epsilon} \mathrm{sgn}(\epsilon) d_{\epsilon}, \quad (14)$$

where the sum is over all edges $\epsilon$ in the Hasse diagram of $Q(G)$ joining a state with $i$ edges to a state with $i-1$ edges. We also define $d_{i,j} : C_{i,j}(G) \to C_{i-1,j}(G)$ to be the map $d_i$ in the $j$th grading.

**Proposition 6** This defines a differential; that is, $d^2 = 0$.

**Proof:** (Outline) Since $d$ is defined via per-edge maps, it suffices to show that $d^2 = 0$ on the per-edge maps. This is achieved through case checking; up to signs, the three cases that must be considered depend on how the removal of two edges from a state of $G$ will disconnect graph components. $\square$

So $C_*(G)$ is a chain complex of graded $\mathcal{S}_n$-modules. See Figure 2 for an example.
## 2.5 Homology and Frobenius series

**Definition 7** For $i, j \ge 0$, the $(i, j)$th homology of $G$ is

$$ H_{i,j}(G) = \ker d_{i,j} / \operatorname{im} d_{i+1,j}, \quad \text{so that} \quad H_i(G) = \bigoplus_{j \ge 0} H_{i,j}(G). \qquad (15) $$

The bigraded Frobenius series of $H_*(G) = \bigoplus_{i,j \ge 0} H_{i,j}(G)$ is

$$ \mathrm{Frob}_G(q, t) = \sum_{i,j \ge 0} (-1)^{i+j} t^i q^j \operatorname{ch}(H_{i,j}(G)), \qquad (16) $$

where $\operatorname{ch}: R \to \Lambda_C : [S^\lambda] \mapsto s_\lambda$ is the Frobenius characteristic map from the Grothendieck ring of representations to the ring of symmetric functions.

**Lemma 8** For any graph $G$,

$$ \sum_{i,j \ge 0} (-1)^{i+j} \operatorname{ch}(H_{i,j}(G)) = \sum_{i,j \ge 0} (-1)^{i+j} \operatorname{ch}(C_{i,j}(G)). $$

**Proof:** This proof is similar to that of the Euler characteristic of chain complexes. We refer the reader to (Helme-Guizon and Rong, 2005, Proposition 2.9). $\square$

**Theorem 9** For any graph $G$,

$$ \mathrm{Frob}_G(1, 1) = X_G. $$

**Proof:** Applying Lemma 8, we compute

$$ \begin{align*} \mathrm{Frob}_G(1, 1) &= \sum_{i,j \ge 0} (-1)^{i+j} \operatorname{ch}(H_{i,j}(G)) \\ &= \sum_{i \ge 0} (-1)^i \left( \sum_{j \ge 0} (-1)^j \operatorname{ch}(C_{i,j}(G)) \right) \\ &= \sum_{i \ge 0} (-1)^i \sum_{\substack{F \subseteq E(G) \\ |F|=i}} p_{\lambda(F)} \\ &= X_G, \end{align*} $$

where the last equality is Equation (2). $\square$
# 3 Properties of $H_*(G)$

## 3.1 Loops and multiple edges

**Proposition 10** If $G$ contains a loop, then $H_*(G) = 0$.

**Proof:** (Outline) Suppose $\ell$ is a loop in $G$. The states of $G$ which do not contain $\ell$ induce a chain complex which we denote by $(C_*(A), d_*^A)$, while the states of $G$ which contain $\ell$ induce a chain complex which we denote by $(C_*(B), d_*^B)$. These two chain complexes are isomorphic, and moreover,

$$C_{i,j}(G) = C_{i-1,j}(B) \oplus C_{i,j}(A), \quad \text{with} \quad d_{i,j}^G = d_{i-1,j}^B + \text{id}_{C_{i-1,j}(B)} + d_{i,j}^A. \quad (17)$$

In other words, $C_*(G)$ is the mapping cone over $\text{id}: C_*(B) \to C_*(A)$. It can be shown that this is acyclic, from which it follows that $H_{i,j}(G) = 0$ for all $i, j \ge 0$. □

**Proposition 11** Let $G$ be a multigraph with edges $e$ and $e'$ incident to the same pair of vertices $x$ and $y$. Then $H_*(G) = H_*(G - e')$.

**Proof:** (Outline) Consider the subgraph $Z = G - e'$, so that $C_{i,j}(Z) \subseteq C_{i,j}(G)$ for all $i, j \ge 0$. Define $C_{i,j}(G, Z) = C_{i,j}(G)/C_{i,j}(Z)$. The induced chain complex $(C_*(G, Z), d_*)$ leads to relative homology $H_{i,j}(G, Z) = \ker d_{i,j}/\text{im } d_{i+1,j}$, and for every $i, j \ge 0$, there is a short exact sequence

$$0 \longrightarrow C_{i,j}(Z) \longrightarrow C_{i,j}(G) \longrightarrow C_{i,j}(G, Z) \longrightarrow 0,$$

that stretches out into a long exact sequence of homology

$$\dots \longrightarrow H_i(Z) \longrightarrow H_i(G) \longrightarrow H_i(G, Z) \longrightarrow H_{i-1}(Z) \longrightarrow \dots$$

Using a similar approach as in Proposition 10, it can be shown that $H_{i,j}(G, Z) = 0$ for all $i, j \ge 0$, from whence it follows that $H_*(G) = H_*(Z)$. □

## 3.2 Disjoint unions

Given graphs $A$ and $B$, let $A + B$ denote their disjoint union. Since the power sum symmetric functions are multiplicative, one can deduce from this that $X_{A+B} = X_A X_B$. We can lift this formula to homology via the Künneth formula (Weibel, 1995, §3.6).

**Proposition 12** For $i, j \ge 0$,

$$H_{i,j}(A+B) = \bigoplus_{\substack{p+r=i \\ q+s=j}} \text{Ind}_{\mathfrak{S}_{A}^{A \cup B} \times \mathfrak{S}_{B}} (H_{p,q}(A) \otimes H_{r,s}(B)).$$

**Proof:** (Outline) First consider the modules corresponding to each state of the graph $A+B$ as $\mathfrak{S}_A \times \mathfrak{S}_B$-modules. For $i, j \ge 0$, we have $C_{i,j}(A+B) = \bigoplus_{\substack{p+r=i \\ q+s=j}} C_{p,q}(A) \otimes C_{r,s}(B)$ with differential maps $d(c_A \otimes c_B) = d_A(c_A) \otimes c_B + (-1)^p c_A \otimes d_B(c_B)$ which induce a map on homology

$$\bigoplus_{\substack{p+r=i \\ q+s=j}} (H_{p,q}(A) \otimes H_{r,s}(B)) \to H_{i,j}(A+B). \quad (18)$$
Since there are no torsion terms, Künneth's formula implies that this is an isomorphism. Induce all modules to $\mathfrak{S}_n$ to get the desired result. $\square$

**Corollary 13** Frob$_{A+B}(q, t) = \text{Frob}_A(q, t) \cdot \text{Frob}_B(q, t). $\square$

For example, if $G$ is a graph with $n$ vertices, then the homology of the disjoint union of $G$ with a single vertex $v_0$ is obtained by branching (see (Fulton, 1997, §7.3 Corollary 3)). If $H_{i,j}(G) = \bigoplus_{\lambda} (S^{\lambda})^{\oplus m_{\lambda}}$, then

$$H_{i,j}(G + v_0) = \text{Ind}_{\mathfrak{S}_n}^{\mathfrak{S}_{n+1}} H_{i,j}(G) = \bigoplus_{\mu=\lambda \cup \square} (S^{\mu})^{\oplus m_{\lambda}},$$

where the latter sum is over all partitions $\mu$ which can be obtained by adding a box to the partitions $\lambda$ indexing the irreducible factors of $H_{i,j}(G)$.

# 4 A Mayer-Vietoris sequence

If the graph $G$ has $n$ vertices, then $X_G$ is homogeneous of degree $n$, so it follows that $X_G$ does not satisfy a deletion-contraction type recurrence. However, if $G$ contains triangles, then the following result provides a method for expressing $X_G$ as a linear combination of chromatic symmetric functions of graphs with fewer edges.

**Theorem 14** (Orellana and Scott, 2014, Theorem 3.1) and (Guay-Paquet, 2013, Proposition 3.1) Let $G$ be a graph where the edges $e_1, e_2, e_3 \in E(G)$ form a triangle. Then

$$X_G = X_{G-e_1} + X_{G-e_2} - X_{G-e_1-e_2}.$$

The categorical analogue of this formula is a Mayer-Vietoris sequence in homology. Let $A = G - e_1$, $B = G - e_2$, and let

$$C_i(A + B) = \bigoplus_{\substack{|F|=i, \\ F \in \mathcal{Q}(A) \cup \mathcal{Q}(B)}} \mathcal{M}_F$$

be the graded submodule of $C_i(G)$ that is the direct sum of the modules $\mathcal{M}_F$ where $F$ is either a state of the subgraph $A$ or a state of the subgraph $B$. The differential $d_i : C_i(G) \to C_{i-1}(G)$ sends $C_i(A \cup B)$ to $C_{i-1}(A \cup B)$, so $C_*(A \cup B)$ forms a chain complex. It turns out that the inclusion $\iota : C_*(A \cup B) \hookrightarrow C_*(G)$ induces an isomorphism on homology. Moreover, there exists a short exact sequence

$$0 \longrightarrow C_i(A \cap B) \xrightarrow{\varphi} C_i(A) \oplus C_i(B) \xrightarrow{\psi} C_i(A \cup B) \longrightarrow 0$$

for each $i \ge 0$, where $\varphi(x) = (x, -x)$, and $\psi(a, b) = a + b$. The short exact sequence of chains induces the long exact sequence in homology, yielding the following result.

**Theorem 15** Let $G$ be a graph where the edges $e_1, e_2, e_3 \in E(G)$ form a triangle. Let $A = G - e_1$ and $B = G - e_2$. Then there is a long exact sequence

$$\dots \longrightarrow H_i(A \cap B) \xrightarrow{\varphi} H_i(A) \oplus H_i(B) \xrightarrow{\psi} H_i(G) \xrightarrow{\delta} \dots \longrightarrow H_0(G) \longrightarrow 0.$$

$\square$
## 4.1 The $K_3$ example

Theorem 14 gives

$$ \begin{array}{ccccl} \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3] 
    \node (A) at (0,0) {$G$};
    \node (B) at (2,0) {$A$};
    \node (C) at (4,0) {$B$};
    \draw[->] (A) -- (B); \draw[->] (A) -- (C);
    \node[above] at (A) {$e_2$}; \node[above] at (B) {$e_2$}; \node[above] at (C) {$e_1$};
    \node[below] at (A) {$e_3$}; \node[below] at (B) {$e_3$}; \node[below] at (C) {$e_1$};
    \node[above] at (A) {$\bullet$}; \node[above] at (B) {$\bullet$}; \node[above] at (C) {$\bullet$};
    \node[below] at (A) {$\bullet$}; \node[below] at (B) {$\bullet$}; \node[below] at (C) {$\bullet$};
    \end{tikzpicture} & = & \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3] 
    \node (A) at (0,0) {$A$};
    \node (B) at (2,0) {$B$};
    \draw[->] (A) -- (B);
    \node[above] at (A) {$e_2$}; \node[above] at (B) {$e_1$};
    \node[below] at (A) {$\bullet$}; \node[below] at (B) {$\bullet$};
    \node[above] at (A) {$\bullet$}; \node[above] at (B) {$\bullet$}; \node[above] at (A) {$\bullet$};
    \node[below] at (A) {$\bullet$}; \node[below] at (B) {$\bullet$}; \node[below] at (A) {$\bullet$};
    \end{tikzpicture} & + & \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3] 
    \node (A) at (0,0) {$B$};
    \node (C) at (4,0) {$A \cap B$};
    \draw[->] (A) -- (C);
    \node[above] at (A) {$e_2$}; \node[above] at (C) {$e_3$}; \node[below] at (A) {$\bullet$}; \node[below] at (C) {$\bullet$};
    \node[above] at (A) {$\bullet$}; \node[above] at (C) {$\bullet$}; \node[above] at (A) {$\bullet$};
    \node[below] at (A) {$\bullet$}; \node[below] at (C) {$\bullet$}; \node[below] at (A) {$\bullet$};
    \end{tikzpicture} & - & \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3] 
    \node (A) at (0,0) {$A$};
    \node (B) at (2,0) {$A \cap B$};
    \draw[->] (A) -- (B);
    \node[above] at (A) {$e_2$}; \node[above] at (B) {$e_3$}; \node[below] at (A) {$\bullet$}; \node[below] at (B) {$\bullet$};
    \node[above] at (A) {$\bullet$}; \node[above] at (B) {$\bullet$}; \node[above] at (A) {$\bullet$};
    \node[below] at (A) {$\bullet$}; \node[below] at (B) {$\bullet$}; \node[below] at (A) {$\bullet$};
    \end{tikzpicture} \\ 
    6s_{111} & = & (s_{21} + 4s_{111}) & + & (s_{21} + 4s_{111}) & - & (2s_{21} + 2s_{111}) \end{array} $$

To condense notation, let $H_*(Z) = H_*(A \cap B)$ and $H_*(Y) = H_*(A) \oplus H_*(B)$. Using the computations from Sections 5.2, 5.3 and Section 5.1 combined with Corollary 13, the Mayer-Vietoris sequence for $G = K_3$ is

$$ \begin{array}{c} H_2Z \to H_2Y \to H_2G \to H_1Z \to H_1Y \to H_1G \to H_0Z \to H_0Y \to H_0G \to 0 \\ 0 \to 2S^{111} \to 2S^{111} \to 0 \to 0 \to 0 \to 0 \to 0 \to 0 \to 0 \\ 0 \to 0 \to 0 \to S^{21}+S^{111} \to 2S^{21}+4S^{111} \to S^{21}+3S^{111} \to 0 \to 0 \to 0 \to 0 \\ 0 \to 0 \to 0 \to 0 \to 0 \to S^{21} \to S^{21}+S^{111} \to 2S^{111} \to S^{111} \to 0 \end{array} $$

In terms of the Frobenius series $\text{Frob}_G(q, 1)$,

$$ \begin{array}{c|cccc} \text{Frob}_{K_3}(q, 1) & = & \text{Frob}_A(q, 1) & + & \text{Frob}_B(q, 1) \\ \hline 2q^2 s_{111} & = & q^2 s_{111} & + & q^2 s_{111} \\ q(s_{21} + 3s_{111}) & = & q(s_{21} + 2s_{111}) & + & q(s_{21} + 2s_{111}) \\ s_{111} - s_{21} & = & s_{111} & + & s_{111} \end{array} \begin{array}{c} - \\ 0 \\ q(s_{21} + s_{111}) \\ (s_{21} + s_{111}) \end{array} $$

# 5 Examples

We include computations of Khovanov-Stanley homology for several simple graphs.

## 5.1 A single edge

Let $G = K_2$. The diagram of states together with the signed per-edge map is

$$ \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3] 
    \node (A) at (0,0) {$C_1(G)$};
    \node (B) at (2,0) {$C_0(G)$};
    \draw[->] (A) -- (B);
    \node[above] at (A) {$1$}; \node[above] at (B) {$0$};
    \node[above] at (A) {$\bullet$}; \node[above] at (B) {$\bullet$};
    \node[below] at (A) {$\bullet$}; \node[below] at (B) {$\bullet$};
    \node[above] at (A) {$\bullet$}; \node[above] at (B) {$\bullet$}; \node[above] at (A) {$\bullet$};
    \node[below] at (A) {$\bullet$}; \node[below] at (B) {$\bullet$}; \node[below] at (A) {$\bullet$};
    \node[above] at (A) {$\bullet$}; \node[above] at (B) {$\bullet$}; \node[above] at (A) {$\bullet$};
    \node[below] at (A) {$\bullet$}; \node[below] at (B) {$\bullet$}; \node[below] at (A) {$\bullet$};
    \end{tikzpicture} \quad \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3] 
    \node (A) at (0,0) {$d_*$};
    \node (B) at (2,0) {$\bullet$};
    \draw[->] (A) -- (B);
    \node[above] at (A) {$\bullet$}; \node[above] at (B) {$\bullet$};
    \node[above] at (A) {$\bullet$}; \node[above] at (B) {$\bullet$}; \node[above] at (A) {$\bullet$};
    \node[below] at (A) {$\bullet$}; \node[below] at (B) {$\bullet$}; \node[below] at (A) {$\bullet$};
    \node[above] at (A) {$\bullet$}; \node[above] at (B) {$\bullet$}; \node[above] at (A) {$\bullet$};
    \node[below] at (A) {$\bullet$}; \node[below] at (B) {$\bullet$}; \node[below] at (A) {$\bullet$};
    \end{tikzpicture} $$

The chain complex of graded $\mathfrak{S}_2$-modules corresponding to the states is

$$ \begin{array}{c} S^{11} \\ \wedge \\ S^2 \end{array} \xrightarrow{d_{10}} \operatorname{Ind}_{\mathfrak{S}_1 \times \mathfrak{S}_1} (S^1 \otimes S^1). $$
Recall that $\mathfrak{S}_2 = \langle s_1 | s_1^2 = e \rangle$. Then $\mathrm{Ind}_{\mathfrak{S}_1 \times \mathfrak{S}_1}(S^1 \otimes S^1) \cong S^2 \oplus S^{11} \cong \mathbb{C}[\mathfrak{S}_2] = \mathrm{span}\{e, s_1\}$. Choosing $S^2 = \mathrm{span}_{\mathbb{C}}\{e + s_1\}$ and $S^{11} = \mathrm{span}_{\mathbb{C}}\{e - s_1\}$, then

$$d_{10}: \mathrm{span}_{\mathbb{C}}\{e + s_1\} \to \mathrm{span}_{\mathbb{C}}\{e, s_1\} \qquad (19)$$

is simply the inclusion map. Therefore, the chromatic symmetric homology of graded $\mathfrak{S}_2$-modules for $G = K_2$ is

$$\begin{array}{c|ccc}
1 & \mathfrak{S}^{11} & \\
0 & 0 & \mathfrak{S}^{11} \\
\hline
& H_1(K_2) & H_0(K_2)
\end{array}$$

and the bigraded Frobenius series is $\mathrm{Frob}_{K_2}(q, t) = qts_{11} + s_{11} = (1 + qt)s_{11}$.

## 5.2 The triangle graph

Let $G = K_3$. The Khovanov-Stanley homology of graded $\mathfrak{S}_n$-modules is

$$\begin{array}{c|ccc}
2 & (S^{111})^{\oplus 2} & \\
1 & 0 & S^{21} \oplus (S^{111})^{\oplus 3} \\
0 & 0 & S^{21} & S^{111} \\
\hline
& H_2(K_3) & H_1(K_3) & H_0(K_3)
\end{array}$$

and the bigraded Frobenius series is

$$\begin{aligned}
\mathrm{Frob}_{K_3}(q,t) &= 2q^2 t^2 s_{111} + qt(s_{21} + 3s_{111}) - ts_{21} + s_{111} \\
&= (q-1)ts_{21} + (1+qt)(1+2qt)s_{111}.
\end{aligned}$$

## 5.3 Some small trees

While the chromatic polynomial $\chi_G$ does not distinguish trees, it is conjectured that the chromatic polynomial is a complete invariant for trees. In this example, we state results in homology for trees up to four vertices. Let

$$P_3 = \bullet - \bullet - \bullet$$

$$P_4 = \bullet - \bullet - \bullet - \bullet$$

$$T_4 = \bullet - \bullet - \bullet - \bullet$$

Their Khovanov-Stanley homology of graded $\mathfrak{S}_n$-modules are

$$\begin{array}{c|ccc}
2 & \mathfrak{S}^{111} & \\
1 & 0 & S^{21} \oplus (S^{111})^{\oplus 2} \\
0 & 0 & 0 & \mathfrak{S}^{111} \\
\hline
& H_2(P_3) & H_1(P_3) & H_0(P_3)
\end{array}$$

$$\begin{array}{c|cccc}
3 & \mathfrak{S}^{1111} & & \\
2 & 0 & S^{22} \oplus (S^{211})^{\oplus 2} \oplus (S^{1111})^{\oplus 3} & \\
1 & 0 & 0 & S^{22} \oplus (S^{211})^{\oplus 2} \oplus (S^{1111})^{\oplus 3} \\
0 & 0 & 0 & 0 & \mathfrak{S}^{1111} \\
\hline
& H_3(P_4) & H_2(P_4) & H_1(P_4) & H_0(P_4)
\end{array}$$
and

<table><tr><td>3</td><td>$S^{111}$</td></tr><tr><td>2</td><td>$0$</td></tr><tr><td>1</td><td>$0$</td></tr><tr><td>0</td><td>$0$</td></tr></table>

Their bigraded Frobenius series are

$$ \mathrm{Frob}_{P_3}(q, t) = qts_{21} + (1 + qt)^2 s_{111}, $$

$$ \mathrm{Frob}_{P_4}(q, t) = qt(1 + qt)s_{22} + 2qt(1 + qt)s_{211} + (1 + qt)^3 s_{1111}, $$

$$ \mathrm{Frob}_{T_4}(q, t) = qts_{31} - t(1 - q + qt)s_{22} + qt(3 + 2qt)s_{211} + (1 + qt)^3 s_{1111}. $$

## Acknowledgements

The former author would like to thank the Simons Foundation for its support via the AMS Travel and Simons Collaboration grants. The latter author would like to thank Chris Hays for helpful suggestions.

## References

* W. Fulton. *Young tableaux*. Cambridge University Press, 1997.

* V. Gasharov. Incomparability graphs of $(\mathfrak{3} + \mathfrak{1})$-free posets are s-positive. *Discrete Math.*, 157:193–197, 1996.

* M. Guay-Paquet. A modular relation for the chromatic symmetric functions of $(\mathfrak{3} + \mathfrak{1})$-free posets. *arXiv:1306.2400v1*, 2013.

* L. Helme-Guizon and Y. Rong. A categorification for the chromatic polynomial. *Algebr. Geom. Topol.*, 5:1365–1388, 2005.

* M. Khovanov. A categorification of the jones polynomial. *Duke Math. J.*, 101(3):359–426, 2000.

* I. G. Macdonald. *Symmetric functions and Hall polynomials*. Oxford University Press, 1995.

* J. Martin, M. Morin, and J. Wagner. On distinguishing trees by their chromatic symmetric functions. *J. Combin. Theory Ser. A*, 115(2):237–253, 2008.

* R. Orellana and G. Scott. Graphs with equal chromatic symmetric functions. *Discrete Math.*, 320:1–14, 2014.

* J. Shareshian and M. Wachs. Chromatic quasisymmetric functions. *arXiv:1405.4629*, 2014.

* R. P. Stanley. A symmetric function generalization of the chromatic polynomial of a graph. *Adv. Math.*, 111(1):166–194, 1995.

* C. A. Weibel. *An introduction to homological algebra*. Cambridge University Press, 1995.