# The Incidence Hopf Algebra of Graphs

Brandon Humpert¹ and Jeremy L. Martin¹

¹Department of Mathematics, University of Kansas, KS, USA

**Abstract.** The graph algebra is a commutative, cocommutative, graded, connected incidence Hopf algebra, whose basis elements correspond to finite simple graphs and whose Hopf product and coproduct admit simple combinatorial descriptions. We give a new formula for the antipode in the graph algebra in terms of acyclic orientations; our formula contains many fewer terms than Schmitt's more general formula for the antipode in an incidence Hopf algebra. Applications include several formulas (some old and some new) for evaluations of the Tutte polynomial.

**Résumé.** L'algèbre de graphes est une algèbre d'incidence de Hopf commutative, cocommutative, graduée, et connexe, dont les éléments de base correspondent à des graphes finis simples et dont le produit et coproduit de Hopf admettent une description combinatoire simple. Nous présentons une nouvelle formule de l'antipode dans l'algèbre de graphes utilisant les orientations acycliques; notre formule contient beaucoup moins de termes que la formule générale de Schmitt pour l'antipode dans une algèbre d'incidence de Hopf. Les applications incluent plusieurs formules (connues et inconnues) pour les évaluations du polynôme de Tutte.

**Keywords:** combinatorial Hopf algebra, graph, chromatic polynomial, Tutte polynomial, acyclic orientation

## 1 Introduction

The graph algebra $\mathcal{G}$ is a commutative, cocommutative, graded, connected Hopf algebra, whose basis elements correspond to finite simple graphs $G$, and whose Hopf product and coproduct admit simple combinatorial descriptions. The graph algebra was first considered by Schmitt in the context of incidence Hopf algebras [Sch94, §12] and furnishes an important example in the work of Aguiar, Bergeron and Sottile [ABS06, Example 4.5].

We derive a new formula (Theorem 3.1) for the Hopf antipode in $\mathcal{G}$. Our formula is specific to the graph algebra in that it involves acyclic orientations; therefore, it is not a consequence of Schmitt's general formula [Sch94, Thm. 4.1] for the antipode in an incidence Hopf algebra. Our formula turns out to be well suited for studying graph invariants, including the Tutte polynomial $T_G(x, y)$ and various specializations of it. The idea is to make $\mathcal{G}$ into a combinatorial Hopf algebra in the sense of Aguiar, Bergeron and Sottile [ABS06] by defining a character on it, then to define a graph invariant by means of a Hopf morphism to a polynomial ring. The antipode formula leads to combinatorial interpretations of the convolution inverses of several natural characters. When we view the Tutte polynomial itself as a character, its $k$-th convolution power itself is a Tutte evaluation at rational functions in $x, y, k$ (Theorem 4.1). This implies several well-known formulas such as Stanley's formula for acyclic orientations in terms of the chromatic polynomial [Sta73]. Further enumerative consequences of Theorem 4.1 include interpretations of less
familiar specializations of the Tutte polynomial (for example, $T_G(3, 2)$), as well as an unusual-looking reciprocity relation between complete graphs of different sizes (Eqns. (15) and (16)).

This is an extended abstract of the full paper [HM10], containing background material and theorems but no proofs. Subsequently to writing this paper, we learned [Agu] that Aguiar and Ardila have independently discovered a more general antipode formula than ours, in the context of Hopf monoids (for which see [AM10]); their work will appear in a forthcoming paper.

We thank Marcelo Aguiar, Aaron Lauve, Vic Reiner and Frank Sottile for numerous helpful conversations.

# 2 Hopf algebras

## 2.1 Basic definitions

We briefly review the basic facts about Hopf algebras, omitting the proofs. Good sources for the full details include Sweedler [Swe69] and (for combinatorial Hopf algebras) Aguiar, Bergeron and Sottile [ABS06].

Fix a field $\mathbb{F}$ (typically $\mathbb{C}$). A bialgebra $\mathcal{H}$ is a vector space over $\mathbb{F}$ equipped with linear maps

$$m : \mathcal{H} \otimes \mathcal{H} \to \mathcal{H}, \quad u : \mathbb{F} \to \mathcal{H}, \quad \Delta : \mathcal{H} \to \mathcal{H} \otimes \mathcal{H}, \quad \epsilon : \mathcal{H} \to \mathbb{F},$$

respectively the multiplication, unit, comultiplication, and counit, such that the following properties are satisfied: (1) $m \circ (m \otimes I) = m \circ (I \otimes m)$ (associativity); (2) $m \circ (u \otimes I) = m \circ (I \otimes u) = I$ (where $I$ is the identity map on $\mathcal{H}$); (3) $(\Delta \otimes I) \circ \Delta = (I \otimes \Delta) \circ \Delta$ (coassociativity); (4) $(\epsilon \otimes I) \circ \Delta = (I \otimes \epsilon) \circ D = I$; and (5) $\Delta$ and $\epsilon$ are multiplicative (equivalently, $m$ and $u$ are comultiplicative). If there exists a bialgebra automorphism $S : \mathcal{H} \to \mathcal{H}$ such that $m \circ (S \otimes I) \circ \Delta = m \circ (I \otimes S) \circ \Delta = u \circ \epsilon$, we say that $\mathcal{H}$ is a Hopf algebra, and $S$ is its antipode$^{(i)}$

A Hopf algebra $\mathcal{H}$ is graded if $\mathcal{H} = \bigoplus_{n \ge 0} \mathcal{H}_n$ as vector spaces, and multiplication and comultiplication respect this decomposition, i.e.,

$$m(\mathcal{H}_i \otimes \mathcal{H}_j) \subseteq \mathcal{H}_{i+j} \quad \text{and} \quad \Delta(\mathcal{H}_k) \subseteq \sum_{i+j=k} \mathcal{H}_i \otimes \mathcal{H}_j.$$

Meanwhile, $\mathcal{H}$ is connected if $\dim(\mathcal{H}_0) = 1$. If $\mathcal{H}$ is a graded and connected bialgebra, then its antipode can be defined inductively as follows: $S(h) = h$ for $h \in \mathcal{H}_0$, and, then $(m \circ (S \otimes I) \circ \Delta)(h) = 0$ for $h \in \mathcal{H}_i, i > 0$. Most (if not all) of the Hopf algebras arising naturally in combinatorics are graded and connected, and every algebra we consider henceforth will be assumed to have these properties.

A character of a Hopf algebra $\mathcal{H}$ is a multiplicative linear map $\phi : \mathcal{H} \to \mathbb{F}$. The convolution product of two characters is $\phi * \psi = (\phi \otimes \psi) \circ \Delta$. That is, if $\Delta h = \sum_i h_1^{(i)} \otimes h_2^{(i)}$, then $(\phi * \psi)(h) = \sum_i \phi(h_1^{(i)})\psi(h_2^{(i)})$. (This formula can be written more concisely in Sweedler notation: if $\Delta h = \sum h_1 \otimes h_2$, then $(\phi * \psi)(h) = \sum \phi(h_1)\psi(h_2)$.) Convolution makes the set of characters $\mathbb{X}(\mathcal{H})$ into a group, with identity $\epsilon$ and inverse given by $\phi^{-1} = \phi \circ S$. There is a natural involutive automorphism $\phi \mapsto \bar{\phi}$ of $\mathbb{X}(\mathcal{H})$ given by $\bar{\phi}(h) = (-1)^n \phi(h)$ for $h \in \mathcal{H}_n$. If $\mathcal{H}$ is a graded connected Hopf algebra and $\zeta \in \mathbb{X}(\mathcal{H})$, then the pair $(\mathcal{H}, \zeta)$ is called a combinatorial Hopf algebra, or CHA for short. A morphism of CHAs $\Phi : (\mathcal{H}, \zeta) \to (\mathcal{H}', \zeta')$ is a linear transformation $\mathcal{H} \to \mathcal{H}'$ that is a morphism of Hopf algebras (i.e., a linear transformation that preserves the operations of a bialgebra) such that $\zeta \circ \Phi = \zeta'$.

<footnote>(i) It can be shown that $S$ is the unique automorphism of $\mathcal{H}$ with this property.</footnote>
## 2.2 The binomial and graph Hopf algebras

The binomial Hopf algebra is the ring of polynomials $\mathbb{F}[k]$ in one variable $k$, with the usual multiplicative structure; comultiplication $\Delta(f(k)) = f(k \otimes 1 + 1 \otimes k)$; counit $\epsilon(f(k)) = \epsilon_0(f(k)) = f(0)$; and character $\epsilon_1(f(k)) = f(1)$. The following proposition is a consequence of work of Aguiar, Bergeron, and Sottile [ABS06, Thm. 4.1].

**Proposition 2.1 (Polynomiality)** Every combinatorial Hopf algebra $(\mathcal{H}, \zeta)$ has a unique CHA morphism to $(\mathbb{F}[k], \epsilon_1)$.

We regard this Hopf morphism as a way to associate a polynomial invariant $P_{\zeta,h}(k) = \zeta^k(h) \in \mathbb{F}[k]$ with each element $h \in \mathcal{H}$. In fact, Aguiar, Bergeron, and Sottile proved something much stronger: the algebra $\mathcal{Q}$ of quasisymmetric functions is a terminal object in the category of CHAs, i.e., every CHA has a unique morphism to $\mathcal{Q}$. Composing this morphism with the principal specialization$^{(ii)}$ gives the morphism of Proposition 2.1. We will not use the full power of the Aguiar–Bergeron–Sottile theorem (which can be viewed as a way to associate a quasisymmetric-function invariant to each element of $\mathcal{H}$). Note that for $k \in \mathbb{Z}$, the identity $\zeta^k(h) = P_{\zeta,h}(k)$ follows from the definition of a CHA morphism; therefore, it is actually an identity of polynomials in $k$.

The graph algebra$^{(iii)}$ is the $\mathbb{F}$-vector space $\mathcal{G} = \bigoplus_{n \ge 0} \mathcal{G}_n$, where $\mathcal{G}_n$ is the linear span of isomorphism classes of simple graphs on $n$ vertices. This is a graded connected Hopf algebra, with multiplication $m(G \otimes H) = G \cdot H = G \uplus H$ (where $\uplus$ denotes disjoint union); unit $u(1) = \emptyset$ (the graph with no vertices); comultiplication $\Delta(G) = \sum_{T \subseteq V(G)} G|_T \otimes G|_{\bar{T}}$ (where $G|_T$ denotes the induced subgraph on vertex set $T$, and $\bar{T} = V(G) \setminus T$); and counit

$$ \epsilon(G) = \begin{cases} 1 & \text{if } G = \emptyset, \\ 0 & \text{if } G \neq \emptyset. \end{cases} $$

This Hopf algebra is commutative and cocommutative; in particular, its character group $\mathbb{X}(G)$ is abelian. As proved by Schmitt [Sch94, eq. (12.1)], the antipode in $\mathcal{G}$ is given by $S(G) = \sum_{\pi} (-1)^{|\pi|} G_{\pi}$, where the sum runs over all ordered partitions $\pi$ of $V(G)$ into nonempty sets (or “blocks”), and $G_{\pi}$ is the disjoint union of the induced subgraphs on the blocks. Here we have two canonical involutions on characters:

$$ \bar{\phi}(G) = (-1)^{n(G)} \phi(G), \quad \tilde{\phi}(G) = (-1)^{\mathrm{rk}(G)} \phi(G), $$

where rk($G$) denotes the graph rank of $G$ (that is, the number of edges in a spanning tree). (Note that $\phi \mapsto \tilde{\phi}$ is not an automorphism of $\mathbb{X}(G)$.) The graph algebra was studied by Schmitt [Sch94] and appears as the chromatic algebra in the work of Aguiar, Bergeron and Sottile [ABS06], where it is equipped with the character

$$ \zeta(G) = \begin{cases} 1 & \text{if } G \text{ has no edges,} \\ 0 & \text{if } G \text{ has an edge.} \end{cases} $$

We will study several characters on $\mathcal{G}$ other than $\zeta$.

<footnote>(ii) If $F(x_1, x_2, \dots)$ is a formal power series, then its principal specialization is obtained by setting $x_i = 1$ and $x_i = 0$ for all $i > 1$.</footnote>

<footnote>(iii) The literature contains many other instances of “Hopf algebras of graphs”; for example, the algebra $\mathcal{G}$ is not the same as that studied by Novelli, Thibon and Thiéry [NTT04].</footnote>
## 3 A new antipode formula

Our first result is a new formula for the Hopf antipode in $\mathcal{G}$. Unlike Schmitt's formula, our formula applies only to $\mathcal{G}$ and does not generalize to other incidence algebras. On the other hand, our formula involves many fewer summands, which makes it useful for enumerative formulas involving characters.

**Theorem 3.1** Let $G$ be a graph with vertex set $[n]$ and edge set $E$. Then

$$S(G) = \sum_{\substack{F \subseteq E \\ F \text{ is a flat}}} (-1)^{n-\mathrm{rk}(F)} a(G/F) G_{V,F}$$

where $a(G)$ is the number of acyclic orientations of $G$, $\mathrm{rk}(F)$ is the rank of the flat $F$, and $G_{V,F}$ is the graph with vertices $V$ and edges $F$.

For the proof, see [HM10]. An easy consequence is the following:

**Proposition 3.2** Let $P$ be any family of graphs such that $G \uplus H \in P$ if and only if $G \in P$ and $H \in P$. That is, the function

$$\chi_P(G) = \begin{cases} 1 & \text{if } G \in P, \\ 0 & \text{if } G \notin P \end{cases}$$

is a character. Then

$$\chi_P^{-1}(G) = \sum_{\text{flats } F \subseteq G: F \in P} (-1)^{n-\mathrm{rk}(F)} a(G/F).$$

**Example 3.3** Let $P$ be the family of graphs with no edges. Then $\chi_P = \zeta$ and $\chi_P^{-1}(G)(-1)^n a(G)$, which is Stanley's well-known formula [Sta73].

**Example 3.4** Let $P$ be the family of acyclic graphs, and let $\alpha = \chi_P$. Then

$$\alpha^{-1}(G) = \sum_{\text{acyclic flats } F} (-1)^{n-\mathrm{rk}(F)} a(G/F).$$

First, let $G = C_n$. The acyclic flats of $G$ are just the sets of $n-2$ or fewer edges, so an elementary calculation (which we omit) gives $\alpha^{-1}(C_n) = (-1)^n + 1$, the Euler characteristic of an $n$-sphere. (For many other families $P$, the $P$-free flats of the $n$-cycle are just the flats, i.e., the edge sets of cardinality $\neq n-1$. In such cases, the same omitted calculation gives $\chi_P(C_n) = (-1)^n$.)

Second, let $G = K_n$. The acyclic flats of $G$ are matchings; for $0 \le k \le \lfloor n/2 \rfloor$, the number of $k$-edge matchings is $n!/(2^k(n-2k)!k!)$, and contracting such a matching yields a graph whose underlying simple graph is $K_{n-k}$. Therefore, $\alpha^{-1}(K_n) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^{n-k} \frac{n!}{2^k(n-2k)!k!} (n-k)!$. These numbers (starting at $n=1$) are
$$-1, 1, 0, -6, 30, -90, 0, 2520, -22680, 113400, 0, -7484400, \dots$$

This is sequence A009775 in [Slo10]; the generating function is $-\tanh(\ln(1+x))$.

**Example 3.5** Fix any connected graph $S$. Say that $G$ is $S$-free if it has no subgraph isomorphic to $S$. [Note: This is stronger than saying that $G$ has no induced subgraph isomorphic to $S$.] Let $\eta_S$ be the corresponding “avoidance character”: $\eta_S(G) = 1$ if $G$ is $S$-free, otherwise $\eta_S(G) = 0$. For example,
$\eta_{K_1} = \epsilon$ and $\eta_{K_2} = \zeta$, and $\delta_m := \eta_{K_{m,1}}$ detects whether or not $G$ has maximum degree $< m$. For an avoidance character, the sum in Proposition 3.2 is taken over all $S$-free flats $F$. For example, we have

$$ \eta_{K_m}^{-1}(K_n) = \sum_{j=0}^{m-1} \binom{n}{j} (-1)^{n-j-1} (n-j)! $$

Another consequence: if $T$ is a tree with $r = n - 1$ edges, then

$$ \eta_S^{-1}(G) = \sum_{S\text{-free forests } F \subseteq T} (-1)^{r+1-|F|} 2^{r-|F|} = - \sum_{S\text{-free forests } F \subseteq T} (-2)^{r-|F|}. $$

Moreover, $P_{\eta_T}(T; k) = k^{n(T)} - k$.

**Example 3.6** Let $S$ be a connected graph and $\eta_S$ the corresponding avoidance character. Then $P_{\eta_S}(G; k)$ equals the number of $k$-colorings such that every color-induced subgraph is $S$-free. For instance, if $S$ is the star $K_{m,1}$, then $P_{\eta_S}(G; k)$ is the number of $k$-colorings such that no vertex belongs to $m$ or more monochromatic edges. This “degree-chromatic polynomial” counts colorings of $G$ in which no color-induced subgraph has a vertex of degree $\ge m$; if $m = 1$, then we recover the usual chromatic polynomial. In general, two trees with the same number of vertices need not have the same degree-chromatic polynomials. For example, if $G$ is the three-edge path on four vertices, $H$ is the three-edge star, and $S$ is the two-edge path, then $P_{\eta_S}(G; k) = k^4 - 2k^2 + k$ and $P_{\eta_S}(H; k) = k^4 - 3k^2 + 2k$. Based on experimental evidence, we conjecture that if $T$ is any tree on $n$ vertices, $m < n$, and $\eta = \delta_m$ (see Example 3.5), then

$$ P_{\eta}(T; k) = k^n - \sum_{v \in V(T)} \binom{d_T(v)}{m} k^{n-m} + (\text{lower order terms}). $$

# 4 Tutte characters

The Tutte polynomial $T_G(x, y)$ is a powerful graph invariant. It can be viewed as a universal deletion-contraction invariant of graphs (in the sense that every graph invariant satisfying a deletion-contraction recurrence can be obtained from $T_G(x, y)$ via a standard “recipe” [Bol98, p. 340]). It is defined in closed form by the formula

$$ T_G(x, y) = \sum_{A \subseteq E(G)} (x-1)^{\mathrm{rk}(G)-\mathrm{rk}(A)} (y-1)^{\mathrm{null}(A)} $$

where $\mathrm{rk}(A)$ is the graph rank of $A$, and $\mathrm{null}(A) = |A| - \mathrm{rk}(A)$ (the nullity of $A$). For much more on the background and application of the Tutte polynomial, see [BO92]. We note that $T_G(x, y)$ is multiplicative on connected components, so we can regard it as a character on the graph algebra:

$$ \tau_{x,y}(G) = T_G(x, y). $$

We may regard $x, y$ either as indeterminates or as (typically integer-valued) parameters. It is often more convenient to work with the *rank-nullity polynomial*

$$ R_G(x, y) = \sum_{A \subseteq E} (x-1)^{\mathrm{rk}(A)} (y-1)^{\mathrm{null}(A)} = (x-1)^{\mathrm{rk}(G)} T_G(x/(x-1), y) \quad (1) $$
which carries the same information as $T_G(x, y)$, and is also multiplicative on connected components, hence is a character on $\mathcal{G}$. Note that $R_G(1, y) = 1$, and that

$$T_G(x, y) = (x - 1)^{\mathrm{rk}(G)} R_G(x/(x - 1), y). \qquad (2)$$

Let $\rho_{x,y}$ denote the function $G \mapsto R_G(x, y)$, viewed as a character of the graph algebra $\mathcal{G}$. Let $P_{x,y}(G; k) = \rho_{x,y}^k(G)$ be the image of $G$ under the CHA morphism $(\mathcal{G}, \rho_{x,y}) \to \mathbb{F}(x, y)[k]$ (see Proposition 2.1); note that $P_{x,y}(G; k)$ is a polynomial function of $k$.

For later use, we record the relationship between $\rho$ and $\tau$:

$$\tau_{x,y} = (x - 1)^{\mathrm{rk}(G)} \rho_{x/(x-1),y}, \quad \rho_{x,y} = (x - 1)^{\mathrm{rk}(G)} \tau_{x/(x-1),y}. \qquad (3)$$

In particular,

$$\tau_{0,y} = \tilde{\rho}_{0,y} \quad \text{and} \quad \rho_{2,y} = \tau_{2,y}. \qquad (4)$$

Our main theorem on Tutte characters is that $P_{x,y}(G; k)$ is itself a Tutte polynomial evaluation, as follows:

**Theorem 4.1** We have

$$\rho_{x,y}^k(G) = P_{x,y}(G; k) = k^{c(G)}(x-1)^{\mathrm{rk}(G)} T_G \left( \frac{k+x-1}{x-1}, y \right).$$

As is typical for Tutte polynomial identities, the idea of the proof is to show that the left-hand side satisfies a deletion-contraction recurrence.

## 4.1 Applications to Tutte polynomial evaluations

Theorem 4.1 has many enumerative consequences, some familiar and some less so. Many of the formulas we obtain resemble those in the work of Ardila [Ard07]; the precise connections remain to be investigated.

First, observe that setting $x = y = t$ in Theorem 4.1 yields

$$\rho_{t,t}^k(G) = P_{t,t}(G; k) = k^{c(G)}(t-1)^{\mathrm{rk}(G)} T_G \left( \frac{k+t-1}{t-1}, t \right) = k^{c(G)} \bar{\chi} C_G(k; t) \qquad (5)$$

where $\bar{\chi}$ denotes Crapo's coboundary polynomial$^{(iv)}$; see [MR05, p. 236] and [BO92, §6.3.F]. A consequence is the following pair of identities:

**Corollary 4.2** For $k \in \mathbb{Z}$ and $y$ arbitrary, the Tutte characters $\tau_{2,y}$ and $\tau_{0,y}$ satisfy the identities

$$(\tau_{2,y})^k(G) = k^{c(G)} T_G(k+1, y), \qquad (6)$$

$$(\tilde{\tau}_{0,y})^k(G) = k^{c(G)} (-1)^{\mathrm{rk}(G)} T_G(1-k, y). \qquad (7)$$

In particular, $(\tilde{\tau}_{0,y})^{-1} = \overline{\tau_{2,y}}$.

<footnote>$^{(iv)}$ The bar is standard notation and has no relation to the involution $\phi \mapsto \bar{\phi}$ on $\mathbb{X}(\mathcal{G})$.</footnote>
In this vein, we can find combinatorial interpretations of convolution powers of the characters $\tau_{2,2}$, $\tau_{2,0}$, $\tilde{\tau}_{0,2}$, and $\tilde{\tau}_{0,0}$. In the last case, we recover the standard formula for the chromatic polynomial as a specialization of the Tutte polynomial. Note that $\tilde{\tau}_{0,0} = \tau_{0,0}$, because these characters are both zero on any graph with one or more edges.

This setup leads to combinatorial interpretations of other Tutte evaluations. If $G$ is connected, then substituting $y = 2$ and $k = 2$ into (6) yields

$$2T(G; 3, 2) = P_{2,2}(G; 2) = (\tau_{2,2} * \tau_{2,2})(G) = \sum_{U \subseteq V(G)} 2^{e(G|U)} 2^{e(G|\bar{V})} = \sum_{U \subseteq V(G)} 2^{e(G|U)+e(G|\bar{V})}. \quad (8)$$

That is, $T(G; 3, 2)$ counts the pairs $(f, A)$, where $f$ is a 2-coloring of $G$ and $A$ is a set of monochromatic edges.

In order to interpret more general powers of Tutte characters, we use (3) to rewrite the left-hand side of Theorem 4.1 as

$$k^{c(G)}(x-1)^{\mathrm{rk}(G)} T_G \left( \frac{k+x-1}{x-1}, y \right) = \sum_{V_1 \uplus \cdots \uplus V_k = V(G)} \prod_{i=1}^{k} (x-1)^{\mathrm{rk}(G_i)} \tau_{x/(x-1), y}(G_i)$$

where $G_i = G|_{V_i}$. Note that in the special case $G = K_n$, we have $G_i \cong K_{|V_i|}$ and $\mathrm{rk}(G_i) = |V_i| - 1$ for all $i$, so the equation simplifies to

$$(x-1)^{n-1} T_{K_n} \left( \frac{k+x-1}{x-1}, y \right) = k^{-1} (\tau_{x/(x-1), y})^k (K_n). \quad (9)$$

This equation has further enumerative consequences: setting $x = 2$ gives

$$T_{K_n}(k+1, y) = \frac{1}{k} \sum_{a_1+\cdots+a_k=n} \frac{n!}{a_1! a_2! \cdots a_k!} \tau_{2,y}(K_{a_1}) \cdots \tau_{2,y}(K_{a_k}). \quad (10)$$

Setting $y = 0$ in (10), and observing that $\tau_{2,0}(K_a) = a!$ gives $T_{K_n}(k+1, 0) = (n+k-1)!/k!$ (which is not a new formula—it follows from the standard specialization of the Tutte polynomial to the chromatic polynomial, and the well-known formula $k(k-1)\cdots(k-n+1)$ for the chromatic polynomial of $K_n$). On the other hand, setting $y = 2$ in (10), and recalling that $\tau_{2,2}(K_a) = 2^{|E(K_a)|} = 2^{\binom{a}{2}}$, gives

$$T_{K_n}(k+1, 2) = \frac{1}{k} \sum_{a_1+\cdots+a_k=n} \frac{n!}{a_1! a_2! \cdots a_k!} 2^{\binom{a_1}{2}+\cdots+\binom{a_k}{2}} \quad (11)$$

This formula may be obtainable from the generating function for the coboundary polynomials of complete graphs, as computed by Ardila [Ard07, Thm. 4.1]; see also sequence A143543 in [Slo10]. Notice that setting $k = 2$ in (11) recovers (8).

It is natural to ask what happens when we set $x = 1$, since this specialization of the Tutte polynomial has well-known combinatorial interpretations in terms of, e.g., the chip-firing game [ML97] and parking functions [GS96]. The equations (1) and (2) degenerate upon direct substitution, but we can instead take the limit of both sides of Theorem 4.1 as $x \to 1$, obtaining (after some calculation, which we omit)

$$\rho_{1,y}^k(G) = k^{n(G)}.$$
We now examine what can be said about Tutte characters in light of the polynomiality principle (Proposition 2.1). Replacing $x$ with $(k+x-1)/(x-1)$ in Theorem 4.1, we get

$$P_{(k+x-1)/(x-1),y}(G;k) = k^{c(G)}(k/(x-1))^{\mathrm{rk}(G)}T(G;x,y) = k^{n(G)}(x-1)^{-\mathrm{rk}(G)}T(G;x,y). \quad (12)$$

One consequence is a formula for the Tutte polynomial in terms of $P$:

$$T(G; x, y) = k^{-n(G)}(x-1)^{\mathrm{rk}(G)}P_{(k+x-1)/(x-1),y}(G;k). \quad (13)$$

In addition, this implies that the left-hand-side of (12) — which is an element of $\mathbb{F}(x, y)[k]$ — is actually just $k^{n(G)}$ times a rational function in $x$ and $y$. Setting $k = x-1$ or $k = 1-x$, we can write down simpler formulas for the Tutte polynomial in terms of $P$:

$$T(G; x, y) = (x-1)^{-c(G)} P_{2,y}(G; x-1),$$

$$T(G; x, y) = (-1)^{n(G)} (x-1)^{c(G)} P_{0,y}(G; 1-x).$$

# 5 A reciprocity relation between $K_n$ and $K_m$

For each scalar $c \in \mathbb{C}$, define a character on $\mathcal{G}$ by $\xi_c(G) = c^{n(G)}$. It is not hard to see that

$$(\xi_c * \zeta)(G) = \sum_{\text{cocliques } Q} c^{n-|Q|}.$$

In particular, $(\xi_1 * \zeta)(G)$ is the number of cocliques in $G$, and $-(\xi_{-1} * \zeta)(G)$ is the reduced Euler characteristic of its clique complex.

Define a $k$-near-coloring to be a function $f: V \to [0, k]$, not necessarily surjective, such that each of the color classes $V_1 = f^{-1}(1), \dots, V_k = f^{-1}(k)$, but not necessarily $V_0 = f^{-1}(0)$, is a coclique. Then

$$(\xi_c * \zeta)^k(G) = \sum_f (ck)^{|V_0|} = \sum_{V_0 \subseteq V(G)} (ck)^{|V_0|} (\# \text{ of } k\text{-colorings of } G - V_0). \quad (14)$$

To see the first equality in (14), consider a partition of $V$ into $2k$ subsets. The union of the first $k$ blocks is $V_0$, and the last $k$ blocks are $V_1, \dots, V_k$. Since $V_0$ is arbitrarily divided into $k$ blocks, each $k$-near-coloring is counted $k^{|V_0|}$ times. Equation (14) implies that

$$(\xi_1 * \zeta^n)(K_m) = \sum_{W \subseteq [m]} \zeta^n(K_W) = \sum_{j=0}^{m} \binom{m}{j} (\# \text{ of } n\text{-colorings of } K_m) = \sum_{j=0}^{m} \frac{m!}{j!(m-j)!} \frac{n!}{(n-j)!}.$$

This expression is symmetric in $n$ and $m$, which yields a surprising (to us, at least) reciprocity relation:

$$(\xi_1 * \zeta^n)(K_m) = (\xi_1 * \zeta^m)(K_n). \quad (15)$$

If we apply the bar involution to both sides of (15) (or, equivalently, redo the calculation with $\xi_{-1}$ instead of $\xi_1$), we obtain

$$(\bar{\xi}_1 * \zeta^n)(K_m) = (-1)^{n+m} (\bar{\xi}_1 * \zeta^m)(K_n). \quad (16)$$
Experimental evidence indicates that

$$ (\xi_1 * \zeta^{-1})(K_n) = (-1)^n D_n, \quad (\xi_{-1} * \zeta^{-1})(K_n) = (-1)^n A_n, $$

where $D_n$ is the number of derangements of $[n]$ [Slo10, sequence A000166] and $B_n$ is the number of arrangements [Slo10, sequence A000522]. More generally, we conjecture that for all scalars $k$ and $c$, the exponential generating function for $\xi_k * \zeta^c$ is

$$ \sum_{n \ge 0} (\xi_k * \zeta^c)(K_n) \frac{x^n}{n!} = e^{-kx} (1-x)^{-c} $$

(see [Sta99, Example 5.1.2]).

## References

[ABS06] Marcelo Aguiar, Nantel Bergeron, and Frank Sottile, *Combinatorial Hopf algebras and generalized Dehn-Sommerville relations*, Compos. Math. **142** (2006), no. 1, 1–30. MR 2196760 (2006h:05233)

[Agu] Marcelo Aguiar, personal communication.

[AM10] Marcelo Aguiar and Swapneel Mahajan, *Monoidal functors, species and Hopf algebras*, CRM Monograph Series, vol. 29, American Mathematical Society, Providence, RI, 2010.

[Ard07] Federico Ardila, *Computing the Tutte polynomial of a hyperplane arrangement*, Pacific J. Math. **230** (2007), no. 1, 1–26. MR 2318445 (2008g:52034)

[BO92] Thomas Brylawski and James Oxley, *The Tutte polynomial and its applications*, Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 123–225. MR 93k:05060

[Bo198] Béla Bollobás, *Modern graph theory*, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR 1633290 (99h:05001)

[GS96] Ira M. Gessel and Bruce E. Sagan, *The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions*, Electron. J. Combin. **3** (1996), no. 2, Research Paper 9, approx. 36 pp. (electronic), The Foata Festschrift. MR 1392494 (97d:05149)

[HM10] Brandon Humpert and Jeremy L. Martin, *The incidence Hopf algebra of graphs*, 2010, preprint, arXiv:1012.4786.

[ML97] Criel Merino López, *Chip firing and the Tutte polynomial*, Ann. Comb. **1** (1997), no. 3, 253–259. MR 1630779 (99k:90232)

[MR05] Jeremy L. Martin and Victor Reiner, *Cyclotomic and simplicial matroids*, Israel J. Math. **150** (2005), 229–240. MR 2255809 (2007g:05040)

[NTT04] Jean-Christophe Novelli, Jean-Yves Thibon, and Nicolas M. Thiéry, *Algèbres de Hopf de graphes*, C. R. Math. Acad. Sci. Paris **339** (2004), no. 9, 607–610. MR 2103196 (2005g:16077)
[Sch94] William R. Schmitt, *Incidence Hopf algebras*, J. Pure Appl. Algebra **96** (1994), no. 3, 299–330.
MR 1303288 (95m:16033)

[Slo10] N.J.A. Sloane, *The On-Line Encyclopedia of Integer Sequences*, 2010, published electronically
at http://oeis.org.

[Sta73] Richard P. Stanley, *Acyclic orientations of graphs*, Discrete Math. **5** (1973), 171–178.
MR 0317988 (47 #6537)

[Sta99] ________, *Enumerative combinatorics*. Vol. 2, Cambridge Studies in Advanced Mathematics,
vol. 62, Cambridge University Press, Cambridge, 1999, With a foreword by Gian-Carlo Rota
and appendix 1 by Sergey Fomin. MR 1676282 (2000k:05026)

[Swe69] Moss E. Sweedler, *Hopf algebras*, Mathematics Lecture Note Series, W. A. Benjamin, Inc.,
New York, 1969. MR 0252485 (40 #5705)