# Combinatorial Hopf Algebras of Simplicial Complexes

Carolina Benedetti, Joshua Hallam, John Machacek

► To cite this version:

Carolina Benedetti, Joshua Hallam, John Machacek. Combinatorial Hopf Algebras of Simplicial Complexes. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.949-960, 10.46298/dmtcs.2506. hal-01337756

HAL Id: hal-01337756

https://hal.science/hal-01337756

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
obtains Stanley's chromatic symmetric function. In our case, the quasi-symmetric functions that we obtain encode colorings of the simplicial complex as well its f-vector.

The paper is organized as follows. In Section 2 we review the definitions of combinatorial Hopf algebras and simplicial complexes. We then introduce the Hopf algebra, A, of simplicial complexes. Section 3 provides a cancellation-free formula for the antipode of A. Section 4 introduces a family of characters on A giving rise to families of combinatorial Hopf algebras. Using these characters, we explore the quasi-symmetric functions associated to them. Finally, we discuss some future work in Section 5.

# 2 A Hopf algebra of simplicial complexes

## 2.1 Hopf algebra basics

We now review some background material on Hopf algebras. For a more complete overview, the reader is encouraged to see [GR]. Let $\mathcal{H}$ be a vector space over a field $\mathbb{K}$. Let $\text{Id}$ be the identity map on $\mathcal{H}$. We call $\mathcal{H}$ an associative $\mathbb{K}$-algebra with unit 1 provided $\mathcal{H}$ has a $\mathbb{K}$-linear map $m: \mathcal{H} \otimes \mathcal{H} \to \mathcal{H}$ with the property that $m \circ (m \otimes \text{Id}) = m \circ (\text{Id} \otimes m)$. Additionally, the unit 1 can be associated with a $\mathbb{K}$-linear map $u: \mathbb{K} \to \mathcal{H}$ defined by $t \mapsto t \cdot 1$. The maps $m$ and $u$ must be compatible so that

$$m \circ (\text{Id} \otimes u) = m \circ (u \otimes \text{Id}) = \text{Id}.$$

A coalgebra is a vector space $\mathcal{D}$ over $\mathbb{K}$ equipped with a coproduct $\Delta: \mathcal{D} \to \mathcal{D} \otimes \mathcal{D}$ and a counit $\epsilon: \mathcal{D} \to \mathbb{K}$. Both $\Delta$ and $\epsilon$ must be $\mathbb{K}$-linear maps. The coproduct is coassociative so that $(\Delta \otimes \text{Id}) \circ \Delta = (\text{Id} \otimes \Delta) \circ \Delta$ and must be compatible with $\epsilon$. That is,

$$(\epsilon \otimes \text{Id}) \circ \Delta = (\text{Id} \otimes \epsilon) \circ \Delta = \text{Id}.$$

If an algebra $(\mathcal{H}, m, u)$ is also equipped with a coalgebra structure given by $\Delta$ and $\epsilon$, then we say that $\mathcal{H}$ is a bialgebra provided $\Delta$ and $\epsilon$ are algebra homomorphisms.

**Definition 1** A Hopf algebra $\mathcal{H}$ is a $\mathbb{K}$-bialgebra together with a $\mathbb{K}$-linear map $S: \mathcal{H} \to \mathcal{H}$ called the antipode. This map must satisfy the following

$$\sum_{(a)} S(a_1)a_2 = u(\epsilon(a)) = \sum_{(a)} a_1 S(a_2) \quad \text{where} \quad \Delta(a) = \sum_{(a)} a_1 \otimes a_2 \quad \text{in Sweedler notation.}$$

**Remark:** The definition of the antipode given above is rather superficial. The antipode is in fact the inverse of the identity map on $\mathcal{H}$ under the convolution product. See [GR, Definition 1.30] for details.

We say that a bialgebra $\mathcal{H}$ is graded if it can be decomposed into a direct sum

$$\mathcal{H} = \bigoplus_{n \ge 0} H_n$$

where $m(H_i \otimes H_j) \subseteq H_{i+j}$, $u(\mathbb{K}) \subseteq H_0$, $\Delta(H_n) \subseteq \bigoplus_{i=0}^n H_i \otimes H_{n-i}$ and for $n \ge 1$, $\epsilon(H_n) = 0$. We call $\mathcal{H}$ connected if $H_0 \cong \mathbb{K}$.

Any graded and connected $\mathbb{K}$-bialgebra is a Hopf algebra since the antipode can be defined recursively. In many instances computing the antipode of a given Hopf algebra is a very difficult problem. However, we will provide an explicit cancellation-free formula for the antipode in the Hopf algebra of finite simplicial complexes that we will study here. Now we will introduce some basic concepts about the combinatorial objects we are interested in.
<figure><img src="image_2.png" /><figcaption>Fig. 1: A simplicial complex and its 1-dimensional skeleton.</figcaption></figure>

## 2.2 Simplicial complexes

A finite (abstract) simplicial complex, $\Gamma$, is a collection of subsets of some finite set such that if $X \in \Gamma$ and $Y \subseteq X$, then $Y \in \Gamma$. The elements of $\Gamma$ are called *faces* and the maximal (with respect to inclusion) faces are called *facets*. Notice that the facets completely determine the simplicial complex. If $X$ is a face of $\Gamma$ then the *dimension* of $X$ is $\dim X = |X| - 1$. The faces of dimension 0 are called *vertices* of $\Gamma$ and the set of vertices will be denoted $V(\Gamma)$ where we identify $\{v\}$ with $v$. For instance, if $\Gamma$ has facets $\{1, 2, 3\}$ and $\{3, 4\}$ then $V(\Gamma) = \{1, 2, 3, 4\}$. The dimension of $\Gamma$, written as $\dim \Gamma$, is the maximum of the dimensions of its facets.

If $\Gamma$ and $\Theta$ are simplicial complexes with vertex sets $V_1$ and $V_2$, the *disjoint union* of $\Gamma$ and $\Theta$ is the simplicial complex $\Gamma \uplus \Theta$ with vertex set $V_1 \uplus V_2$ and faces $X$ such that $X \in \Gamma$ or $X \in \Theta$. If $k$ is a nonnegative integer, the *k-skeleton* of $\Gamma$ is the collection of faces of $\Gamma$ with dimension no greater than $k$. We will denote the $k$-skeleton of $\Gamma$ by $\Gamma^{(k)}$. For example, if $\Gamma$ has facets $\{1, 2, 3\}$ and $\{3, 4\}$, then $\Gamma^{(1)}$ is the simplicial complex with facets $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ and $\{3, 4\}$. Figure 1 provides a pictorial representation of this example. Notice that a simple graph gives rise to a simplicial complex of dimension 1 or less. Conversely, a simplicial complex of dimension 1 or less can be thought of as a simple graph.

Let $\Gamma$ and $V(\Gamma)$ be defined as above. Given $T \subseteq V(\Gamma)$, define the *induced simplicial complex* of $\Gamma$ on $T$, denoted by $\Gamma_T$, to be the simplicial complex with faces $\{X \cap T \mid X \in \Gamma\}$. So if we return to our example with $\Gamma$ having facets $\{1, 2, 3\}$, $\{3, 4\}$ and if $T = \{1, 3, 4\}$, then $\Gamma_T$ has facets $\{1, 3\}$ and $\{1, 4\}$.

Now we define a Hopf algebra structure on simplicial complexes as in [GSJ]. Let $\mathbb{K}$ be a field and let $\mathcal{A} = \bigoplus_{n \ge 0} A_n$ where $A_n$ is the $\mathbb{K}$-linear span of isomorphism classes of simplicial complexes on $n$ vertices. We denote by $\emptyset$ the simplicial complex with no vertices. Given a simplicial complex $\Gamma$, we will denote its isomorphism class by $[\Gamma]$.

Define the product $m : \mathcal{A} \otimes \mathcal{A} \to \mathcal{A}$ by

$$m ([\Gamma] \otimes [\Theta]) = [\Gamma] \uplus [\Theta].$$

Notice that with this multiplication, the unit $u : \mathbb{K} \to \mathcal{A}$ is given by

$$u(1) = [\emptyset].$$

The coproduct $\Delta : \mathcal{A} \to \mathcal{A} \otimes \mathcal{A}$, is given by

$$\Delta([\Gamma]) = \sum_{T \subseteq V(\Gamma)} [\Gamma_T] \otimes [\Gamma_{V(\Gamma)-T}].$$

Additionally, define the counit of $\mathcal{A}$ by

$$\epsilon([\Gamma]) = \delta_{[\Gamma], [\emptyset]}$$
where $\delta_{[\Gamma],[\emptyset]}$ is the Kronecker delta.

It follows that $\mathcal{A}$ is a graded, connected $\mathbb{K}$-bialgebra and hence a Hopf algebra. Also, it is not hard to see that $\mathcal{A}$ is commutative and cocommutative. In fact, the reader might notice the resemblance of this Hopf algebra with the Hopf algebra of graphs defined in [Sch94]. In the next section, we turn our attention to the antipode of the Hopf algebra $\mathcal{A}$ and we will provide a cancellation-free formula for it. From now on, we will drop the brackets from the notation $[\Gamma]$, keeping in mind that we are considering isomorphism classes of simplicial complexes.

### 3 A cancellation-free formula for the antipode

The formula for the antipode of $\mathcal{A}$ we give in this section is an extension of the formula for the antipode of graphs that was first shown in [HM12]. In [BS, Theorem 3.1] the authors use involutions and Takeuchi's formula [Tak71] to provide a proof for the formula of the antipode of graphs. One can use a slight modification of this proof and obtain a cancellation-free formula for the antipode in $\mathcal{A}$, whose proof we omit due to its similarity to [BS, Theorem 3.1].

Before stating the main result in this section, we review some basic ideas from graph theory. Suppose $G = (V, E)$ is a graph. A flat, $F$, of $G$ is a collection of edges such that in the graph with vertex set $V$ and edge set $F$, each connected component is an induced subgraph of $G$. If $F$ is a flat then we will denote the subgraph of $G$ with vertex set $V$ and edges $F$ by $G_{V,F}$ and its number of connected components by $c(F)$. The set of flats of a graph, $G$, will be denoted by $\mathcal{F}(G)$. We denote by $G/F$ the graph obtained from $G$ by contracting the edges in $F$. Recall that an orientation of a graph is called acyclic if it does not contain any directed cycles. The number of acyclic orientations of a graph $G$ will be denoted by $a(G)$. Let $\Gamma$ be a simplicial complex. Given a flat $F$ in $\Gamma^{(1)}$ define $\Gamma_{V,F}$ to be the subcomplex of $\Gamma$, with vertex set $V = V(\Gamma)$, whose faces are given by

$$ \{X \in \Gamma : X^{(1)} \subseteq \Gamma_{V,F}^{(1)}\}. $$

For example, if we again take $\Gamma$ to have facets $\{1, 2, 3\}$, $\{3, 4\}$ and let $F = \{\{1, 2\}, \{1, 3\}, \{2, 3\}\}$ then $\Gamma_{V,F}$ is the simplicial complex with facets $\{1, 2, 3\}$, $\{4\}$.

**Theorem 2** Let $\Gamma \in \mathcal{A}_n$ be a basis element where $n \ge 1$. Then

$$ S(\Gamma) = \sum_{F \in \mathcal{F}(\Gamma^{(1)})} (-1)^{c(F)} a(\Gamma^{(1)}/F) \Gamma_{V,F} $$

where the sum runs over all flats of the 1-skeleton, $\Gamma^{(1)}$.

Notice that if $\dim \Gamma \le 1$ then $S(\Gamma)$ coincides with the antipode formula of the Hopf algebra of graphs in [HM12].

Let us return to our previous example with $\Gamma$ generated by the facets $\{1, 2, 3\}$ and $\{3, 4\}$. For each flat $F$ in $\Gamma^{(1)}$, we find the number of connected components of $F$ and the number of acyclic orientations of $\Gamma^{(1)}/F$. This information is included in Table 1. Using the information from the table, we see that

$$ S(\Gamma) = 12\bar{K}_4 - 18(K_2 \uplus \bar{K}_2) + 2(K_2 \uplus K_2) + 4(P_3 \uplus K_1) + 2(T \uplus K_1) - \Gamma \quad (1) $$

where $K_n$ is the complete graph on $n$ vertices, $\bar{K}_n$ is the complement of the complete graph on $n$ vertices, $P_n$ is the path on $n$ vertices and $T$ is the 2-simplex. Figure 2 gives a pictorial representation of this
<table><caption>Tab. 1: Information to compute the antipode of Γ.</caption><thead><tr><th>F ∈ F(Γ<sup>(1)</sup>)</th><th>(-1)<sup>c(F)</sup></th><th>a(Γ<sup>(1)</sup>/F)</th></tr></thead><tbody><tr><td>∅</td><td>(-1)<sup>4</sup></td><td>12</td></tr><tr><td>{1, 2}</td><td>(-1)<sup>3</sup></td><td>4</td></tr><tr><td>{1, 3}</td><td>(-1)<sup>3</sup></td><td>4</td></tr><tr><td>{2, 3}</td><td>(-1)<sup>3</sup></td><td>4</td></tr><tr><td>{3, 4}</td><td>(-1)<sup>3</sup></td><td>6</td></tr><tr><td>{1, 2}, {3, 4}</td><td>(-1)<sup>2</sup></td><td>2</td></tr><tr><td>{1, 3}, {3, 4}</td><td>(-1)<sup>2</sup></td><td>2</td></tr><tr><td>{2, 3}, {3, 4}</td><td>(-1)<sup>2</sup></td><td>2</td></tr><tr><td>{1, 2}, {1, 3}, {2, 3}</td><td>(-1)<sup>2</sup></td><td>2</td></tr><tr><td>{1, 2}, {1, 3}, {2, 3}, {3, 4}</td><td>(-1)<sup>1</sup></td><td>1</td></tr></tbody></table>

$$S(\text{▲} \rightarrow \cdot) = 12(\cdots\cdots) - 18(\cdots\cdots) + 2(\cdots\cdots) + 4(\cdots\cdots) + 2(\text{▲} \cdot) - (\text{▲} \cdot)$$

<caption>Fig. 2: Antipode of an element in $\mathcal{A}_4$.</caption>

calculation. We note here that once we have this information, we can easily find the antipode of the simplicial complex $\Gamma^{(1)}$ by just taking the 1-skeleton of each of the terms in the sum for the antipode. So we immediately get that

$$S(\Gamma^{(1)}) = 12\overline{K}_4 - 18(K_2 \uplus \overline{K}_2) + 2(K_2 \uplus K_2) + 4(P_3 \uplus K_1) + 2(K_3 \uplus K_1) - \Gamma^{(1)}.$$

More generally, let $\mathcal{A}^{(k)}$ be the $\mathbb{K}$-linear span of isomorphism classes of simplicial complexes of dimension at most $k$. That is, complexes $\Gamma \in \mathcal{A}$ such that $\Gamma^{(k)} = \Gamma$. For each $k \ge 0$, we define the map

$$\phi_k : \mathcal{A} \rightarrow \mathcal{A}^{(k)} \\ \Gamma \mapsto \Gamma^{(k)}$$

which takes the $k$-skeleton of a simplicial complex. We extend this map linearly to all of $\mathcal{A}$.

**Proposition 3** For any nonnegative integer $k$, $\mathcal{A}^{(k)}$ is a Hopf subalgebra of $\mathcal{A}$ and the map $\phi_k : \mathcal{A} \rightarrow \mathcal{A}^{(k)}$ is a Hopf algebra homomorphism.

**Proof:** Let $\Gamma$ and $\Theta$ be simplicial complexes. Since $\dim \Gamma \uplus \Theta = \max\{\dim \Gamma, \dim \Theta\}$ and given that $\dim \Gamma_T \le \dim \Gamma$ for any $T \subseteq V(\Gamma)$, it follows that $\mathcal{A}^{(k)}$ is in fact a Hopf subalgebra. Observe that

$$(\Gamma \uplus \Theta)^{(k)} = \{X : X \in \Gamma \uplus \Theta, |X| < k\} = \{X \in \Gamma : |X| < k\} \uplus \{X \in \Theta : |X| < k\}.$$

Therefore $(\Gamma \uplus \Theta)^{(k)} = \Gamma^{(k)} \uplus \Theta^{(k)}$ and $\phi_k$ is an algebra homomorphism. Next, since

$$(\Gamma_T)^{(k)} = \{X \in \Gamma : X \subseteq T, |X| < k\} = (\Gamma^{(k)})_T$$
we have

$$ \sum_{T \subseteq V(\Gamma)} (\Gamma_T)^{(k)} \otimes (\Gamma_{V(\Gamma)-T})^{(k)} = \sum_{T \subseteq V(\Gamma)} \Gamma_T^{(k)} \otimes \Gamma_{V(\Gamma)-T}^{(k)} $$

and so $\phi_k$ is also a coalgebra homomorphism. We conclude that $\phi_k$ is a Hopf algebra homomorphism. $\square$

**Corollary 4** For any simplicial complex $\Gamma$ and nonnegative integer $k$ if

$$ S(\Gamma) = \sum_{i=1}^{m} c_i \Gamma_i, $$

then

$$ S(\Gamma^{(k)}) = \sum_{i=1}^{m} c_i \Gamma_i^{(k)}. $$

This corollary follows from the previous proposition along with the fact that for any Hopf algebra homomorphism $\beta: \mathcal{H}_1 \to \mathcal{H}_2$ one has $\beta(S_{\mathcal{H}_1}(h)) = S_{\mathcal{H}_2}(\beta(h))$ for any $h \in \mathcal{H}_1$ (see [GR, Proposition 1.46]).

Looking at the expression for the antipode in equation (1), we see that if we add all the coefficients together we obtain 1. It turns out that the sum of the coefficients of the antipode of a basis element is always $(-1)^n$ where $n$ is the number of vertices of the simplicial complex. We will derive this fact using characters and quasi-symmetric functions in the next section (see Corollary 7).

# 4 Characters and quasi-symmetric functions

Now that we have endowed $\mathcal{A}$ with a Hopf algebra structure, we will proceed to define a family of characters on $\mathcal{A}$. This will give rise to a family of combinatorial Hopf algebras. We will then show how these characters give combinatorial information about simplicial complexes.

## 4.1 The Hopf algebra $QSym$

We review some key facts about characters and quasi-symmetric functions. More details can be found in [ABS06]. The Hopf algebra of quasi-symmetric functions $QSym$ is graded as $QSym = \bigoplus_{n \ge 0} QSym_n$ where $QSym_n$ is spanned linearly over $\mathbb{K}$ by $\{M_\alpha\}_{\alpha \vdash n}$. Here $M_\alpha$ is defined by

$$ M_{\alpha} := \sum_{i_1<i_2<\cdots<i_l} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \cdots x_{i_l}^{\alpha_l} $$

where $\alpha = (\alpha_1, \dots, \alpha_l)$ is a composition of $n$. The basis given by $\{M_\alpha\}$ is known as the *monomial basis* of $QSym$. We let $M_\{\iota\} = 1$, which spans $QSym_0$, where $\{\iota\}$ is the composition of 0 with no parts.

Let the map $\zeta_Q: QSym \to \mathbb{K}$ be defined as $\zeta_Q(f) = f(1, 0, 0, \dots)$ for a quasi-symmetric function $f(x_1, x_2, x_3, \dots)$. Given that $\zeta_Q$ is an evaluation map, it is also an algebra map and hence a character of $QSym$. This endows $QSym$ with a combinatorial Hopf algebra structure. Moreover, Theorem 4.1 of [ABS06] states that given a combinatorial Hopf algebra $(\mathcal{H}, \zeta)$ there is a unique Hopf algebra homomorphism

$$ \Psi_{\zeta}: \mathcal{H} \to QSym. $$
<figure><img src="image_3.png" /><figcaption>Fig. 3: A 2-coloring of Γ in (a) and a 3-coloring of Γ in (b).</figcaption></figure>

Given $h \in H_n$, the map $\Psi_{\zeta}$ is defined as

$$ \Psi_{\zeta}(h) = \sum_{\alpha \vdash n} \zeta_{\alpha}(h) M_{\alpha} \qquad (2) $$

with $\zeta_{\alpha}$ given by the composition of functions

$$ \mathcal{H} \xrightarrow{\Delta^{k-1}} \mathcal{H}^{\otimes k} \to H_{\alpha_1} \otimes H_{\alpha_2} \otimes \dots \otimes H_{\alpha_k} \xrightarrow{\zeta^{\otimes k}} \mathbb{K} $$

where the unlabeled map in the canonical projection and $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_k)$.

Observe that if the Hopf algebra $\mathcal{H}$ is cocommutative, as is the case for $\mathcal{A}$, then equation (2) immediately gives that $\Psi_{\zeta}(h)$ is actually a symmetric function. In particular,

$$ \Psi_{\zeta}(h) = \sum_{\lambda \vdash n} \zeta_{\lambda}(h) m_{\lambda} \qquad (3) $$

where

$$ m_{\lambda} = \sum_{\alpha} M_{\alpha} $$

summing over all the compositions $\alpha$ that can be rearranged to the partition $\lambda$. For instance, the compositions $(1, 2)$ and $(2, 1)$ rearrange to the partition $(2, 1)$. In Section 4.4, we will see how equation (3) allows us to obtain the $f$-vector of a simplicial complex. Hence, one can obtain the topologically invariant Euler characteristic.

## 4.2 Colorings

Let $\mathbb{P}$ denote the set of positive integers and let $G$ be a graph with vertex set $V$. A *coloring* of $G$ is a map $f: V \to \mathbb{P}$. We refer to $f(u)$ as the color of $u$. A *proper coloring* of $V$ is a coloring such that $f(u) \neq f(v)$ whenever $uv$ is an edge of $G$. Given a simplicial complex $\Gamma$ and $s \in \mathbb{N}$, define an *$s$-simplicial coloring*<sup>(i)</sup> to be a coloring of $V(\Gamma)$ such that any face contains at most $s$ vertices using a given color. Notice that any 1-simplicial coloring of $\Gamma$ is simply a proper coloring of its 1-skeleton $\Gamma^{(1)}$. In Figure 3 we use our earlier example and depict two colorings of $\Gamma$ using the colors $\{x, y, z\} \subseteq \mathbb{P}$.

Given a graph $G$, the number of proper colorings using the colors $\{1, 2, \dots, t\}$ is the well-known chromatic polynomial, $\chi(G; t)$. For a simplicial complex $\Gamma$ the number of $s$-simplicial colorings of $V(\Gamma)$

<footnote><sup>(i)</sup> In [DMN] the authors use the term $(P, s)$-coloring for an *$s$-simplicial coloring* which uses some palette of colors $P \subseteq \mathbb{P}$. To avoid confusion with terminology in graphs, we have adopted the term *$s$-simplicial coloring*.</footnote>
using colors {1, 2, ..., t} is called the s-chromatic polynomial, $\chi_s(\Gamma; t)$, as defined in [Nor12]. Although it is not obvious that $\chi_s(\Gamma; t)$ is a polynomial, we will see that this is the case once we realize it as an evaluation of a certain symmetric function.

Stanley provided a generalization (see [Sta95]) of the chromatic polynomial of a graph $G$ by defining

$$ \psi(G; x_1, x_2, \dots) = \sum_f \prod_{i \ge 1} x_i^{|f^{-1}(i)|} $$

where the sum is over proper colorings $f: V \to \mathbb{P}$. This formal power series is known as Stanley's chromatic symmetric function. For a simplicial complex $\Gamma$ we define the s-chromatic symmetric function as

$$ \psi_s(\Gamma; x_1, x_2, \dots) = \sum_f \prod_{i \ge 1} x_i^{|f^{-1}(i)|} $$

where now the sum is over s-simplicial colorings $f: V \to \mathbb{P}$. Notice that when $s = 1$ we obtain Stanley's chromatic symmetric function. The s-chromatic polynomial, $\chi_s(\Gamma; t)$, is a specialization of $\psi_s(\Gamma; x_1, x_2, \dots)$ at $x_i = 1$ for $1 \le i \le t$ and $x_i = 0$ for $i > t$. In [GR] the authors refer to this as the principal specialization at $t$. It will be denoted by $ps^1(\psi_s(\Gamma))(t)$. Summarizing we have

$$ ps^1(\psi_s(\Gamma))(t) = \chi_s(\Gamma; t) $$

for $s, t \ge 1$.

Define the map $\zeta_s: \mathcal{A} \to \mathbb{K}$ by

$$ \zeta_s(\Gamma) = \begin{cases} 1 & \dim \Gamma < s \\ 0 & \dim \Gamma \ge s \end{cases} $$

for each $s \ge 1$, and extend linearly. Notice that $\zeta_s$ is an algebra map, for all $s$, and hence a character. We then get a family of combinatorial Hopf algebras $\{(\mathcal{A}, \zeta_s) : s \ge 1\}$.

**Theorem 5** Fix $s$ and consider the combinatorial Hopf algebra $(\mathcal{A}, \zeta_s)$. For any basis element $\Gamma \in \mathcal{A}$, we have that $\Psi_{\zeta_s}(\Gamma) = \psi_s(\Gamma; x_1, x_2, \dots)$.

**Proof:** Consider the formula in equation (2). Given a simplicial complex $\Gamma \in \mathcal{A}_n$ and a composition $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_l) \vdash n$, we have that the coefficient of $M_\alpha$ is the number of ordered set partitions $V_1 \uplus V_2 \uplus \dots \uplus V_l$ of $V(\Gamma)$ such that $|V_i| = \alpha_i$ and $\dim \Gamma_{V_i} < s$ for each $i$. In an s-simplicial coloring, every element of a subset $T$ of $V(\Gamma)$ can be assigned the same color if and only if $\dim \Gamma_T < s$. Thus the coefficient of $M_\alpha$ counts s-simplicial colorings using only colors $\{j_1 < j_2 < \dots < j_i\} \subseteq \mathbb{P}$ where $|f^{-1}(j_i)| = \alpha_i$ for each $i$. The result follows. $\square$

## 4.3 Acyclic orientations and chromatic polynomial evaluations

In this section, we use our antipode formula along with the characters defined above to interpret certain evaluations of the s-chromatic polynomial. Given any character $\zeta: \mathcal{A} \to \mathbb{K}$, the following identity holds (see [GR, Proposition 1.45])

$$ \zeta^{-1} = \zeta \circ S $$
where $S$ is the antipode in $\mathcal{A}$ and $\zeta^{-1}$ is the inverse of $\zeta$ under convolution. In other words, $\zeta^{-1} \star \zeta = u \circ \epsilon$ where $\zeta^{-1} \star \zeta = m \circ (\zeta^{-1} \otimes \zeta) \circ \Delta$.

Now, since $ps^1(\psi_s(\Gamma))(t) = \chi_s(\Gamma; t)$, using [GR, Proposition 7.7] we get

$$ \zeta_s^{-1}(\Gamma) = ps^1(\psi_s(\Gamma))(-1) = \chi_s(\Gamma; -1). \quad (4) $$

This allows us to prove the following theorem.

**Theorem 6** Let $\Gamma \in A_n$ be a basis element and let $s$ be a positive integer. Then

$$ \chi_s(\Gamma; -1) = \sum_{\substack{F \in \mathcal{F}(\Gamma^{(1)}) \\ \dim \Gamma_{V,F} < s}} (-1)^{c(F)} a(\Gamma^{(1)}/F). $$

**Proof:** Using equation (4), the fact that $\zeta_s^{-1} = \zeta_s \circ S$, and our antipode formula in Theorem 2 we have

$$ \begin{align*} \chi_s(\Gamma; -1) &= \zeta_s(S(\Gamma)) \\ &= \sum_{F \in \mathcal{F}(\Gamma^{(1)})} (-1)^{c(F)} a(\Gamma^{(1)}/F) \zeta_s(\Gamma_{V,F}) \\ &= \sum_{\substack{F \in \mathcal{F}(\Gamma^{(1)}) \\ \dim \Gamma_{V,F} < s}} (-1)^{c(F)} a(\Gamma^{(1)}/F) \end{align*} $$

and the result is proven. $\square$

This result shows that like the chromatic polynomial for graphs, the evaluation at $t = -1$ of the $s$-chromatic polynomial for simplicial complexes has a combinatorial interpretation in terms of counting acyclic orientations.

Now we discuss some special cases of Theorem 6 that are of interest. If we take the character $\zeta_1$ we get that $\chi_1(\Gamma; -1) = (-1)^n a(\Gamma^{(1)})$ and we count the number of acyclic orientations of the 1-skeleton. The authors in [HM12] also derive this expression for the number of acyclic orientations of graphs using characters, although it was originally noticed by Stanley [Sta73]. We also get the following corollary when we take $s$ to be larger than the dimension of a given simplicial complex.

**Corollary 7** Let $\Gamma$ be a simplicial complex on a vertex set of size $n$. Then we have the following

$$ (-1)^n = \sum_{F \in \mathcal{F}(\Gamma^{(1)})} (-1)^{c(F)} a(\Gamma^{(1)}/F). \quad (5) $$

**Proof:** If we take $s > \dim \Gamma$ we have $\chi_s(\Gamma; t) = t^n$ since there is no restriction on coloring. So in that case, we have $\chi_s(\Gamma; -1) = (-1)^n$ and the result is obtained from Theorem 6 by noting $\dim \Gamma_{V,F} < s$ for any $F$ since $\dim \Gamma < s$. $\square$

Recall that if $F$ is a flat of $G$, then $c(F) = n - rk(F)$ where $n = |V(G)|$ and $rk(F)$ is the number of edges in a maximal spanning forest of $G_{V,F}$. We use the notation $rk(F)$ since this is also the rank of the flat in the cycle matroid of the graph. With this in mind, equation (5) can be rewritten as

$$ (-1)^n = \sum_{F \in \mathcal{F}(G)} (-1)^{n-rk(F)} a(G/F). $$
Dividing both sides by $(-1)^n$, one obtains

$$1 = \sum_{F \in \mathcal{F}(G)} (-1)^{rk(F)} a(G/F). \qquad (6)$$

For the flat $F = E(G)$, we have $a(G/F) = 1$. It follows that,

$$1 - (-1)^{rk(E(G))} = \sum_{F \in \mathcal{F}(G), F \neq E(G)} (-1)^{rk(F)} a(G/F).$$

In particular, when $rk(E(G))$ is even, we have

$$\sum_{\substack{F \in \mathcal{F}(G) \\ rk(F) \text{ odd}}} a(G/F) = \sum_{\substack{F \in \mathcal{F}(G), F \neq E(G) \\ rk(F) \text{ even}}} a(G/F).$$

Currently we do not have a bijective proof of this result, although it would be interesting if we could find one.

## 4.4 The f-vector

Given a simplicial complex $\Gamma$ with $\dim \Gamma = d$, the f-vector of $\Gamma$ is defined to be $(f_0, f_1, \dots, f_d)$ where $f_i$ is the number of faces of dimension $i$ in $\Gamma$. For example, if $\Gamma$ is the simplicial complex generated by the facets $\{1, 2, 3\}$ and $\{3, 4\}$, then $\Gamma$ has f-vector $(4, 4, 1)$. The next proposition tells us how to obtain the f-vector of a simplicial complex $\Gamma \in \mathcal{A}$, making use of the functions $\Psi_{\zeta_i}$ defined previously. Let $[m_{\lambda}]\Psi_{\zeta_i}(\Gamma)$ denote the coefficient of $m_{\lambda}$ in $\Psi_{\zeta_i}(\Gamma)$ expanded in the monomial basis $\{m_{\lambda}\}$, and set $\Psi_{\zeta_0}(\Gamma) = 1$. Then we have the following proposition.

**Proposition 8** Let $\Gamma \in \mathcal{A}_n$ be a simplicial complex of dimension $d$. Let $f_i$ be the number of faces of dimension $i$ in $\Gamma$, then

$$(n-i)! f_{i-1} = [m_{(i,1^{n-i})}] (\Psi_{\zeta_i}(\Gamma) - \Psi_{\zeta_{i-1}}(\Gamma)).$$

**Proof:** The coefficient of $m_{(i,1^{n-i})}$ in $\Psi_{\zeta_i}(\Gamma)$ is $(n-i)!(n_i)$. This follows since any collection of $i$ vertices has dimension at most $i-1$ and so when we apply $\zeta_i$ none of the terms indexed by ordered set partitions with one nontrivial block of size $i$ vanishes. There are $\binom{n}{i}$ choices for this block. The remaining $n-i$ blocks, each consisting of a single vertex, can be ordered in any way and so the total number of possible ordered set partitions is $(n-i)!(n_i)$.

To find the coefficient of $m_{(i,1^{n-i})}$ in $\Psi_{\zeta_{i-1}}(\Gamma)$, we must pick ordered set partitions of $V(\Gamma)$ with one nontrivial block of size $i$ such that this $i$-element subset of $V(\Gamma)$ has dimension strictly less than $i-1$ in $\Gamma$. The number of such ordered set partitions is $(n-i)!$ multiplied by the number of $i$ element subsets of $n$ which is not contained in an $i-1$ dimensional face.

Therefore,

$$\frac{[m_{i,1^{n-i}}] (\Psi_{\zeta_i}(\Gamma) - \Psi_{\zeta_{i-1}}(\Gamma))}{(n-i)!}$$

is the total number of $i$-element subsets of $V(\Gamma)$ minus the number of $i$-element subsets of $V(\Gamma)$ which have dimension strictly less than $i-1$. The result now follows. $\square$
# 5 Future work

1. Since the number of acyclic orientations of a graph is same as the number of non-broken circuit sets of the graph, we could reinterpret equation (6) as a statement only about the cycle matroid of the graph. In the future, we would like to investigate if a similar equation holds for any matroid.

2. We have shown how to obtain the *f*-vector of any simplicial complex using quasi-symmetric functions. For some particular complexes, the *f*-vector can be obtained as coefficients of the polynomial obtained by evaluating $\Psi_{\zeta_s}(x_1, x_2, \ldots)$ at $(q, 1, 0, \ldots)$. However, there are examples where this is not the case. We are interested in obtaining the *f*-vector of arbitrary complexes by means of similar evaluations.

3. In [ABS06], the authors define the *odd* and *even* subalgebra of a combinatorial Hopf algebra. We want to explore these subalgebras together with the generalized Dehn-Sommerville relations derived from them. In particular, we want to explore how the generalized Dehn-Sommerville relations associated to the characters defined here compare to the Dehn-Sommerville equations of simplicial complexes.

# References

[ABS06] M. Aguiar, N. Bergeron, and F. Sottile. Combinatorial Hopf algebras and generalized Dehn-Sommerville relations. *Compositio Mathematica*, 142:1–30, 2006.

[BS] C. Benedetti and B. Sagan. Antipodes and involutions. arXiv:1410.5023.

[DMN] N. Dobrinskaya, J. M. Møller, and D. Notbohm. Vertex colorings of simplicial complexes. arXiv:1007.0710.

[GR] D. Grinberg and V. Reiner. Hopf algebras in combinatorics. arXiv:1409.8356.

[GSJ] V. Grujic, T. Stojadinovic, and D. Jojic. Generalized Dehn-Sommerville relations for hypergraphs. arXiv:1402.0421.

[HM12] B. Humpert and J. Martin. The incidence Hopf algebra of graphs. *SIAM J. Discrete Math.*, 26(2):555–570, 2012.

[Nor12] G. Nord. The *s*-chromatic polynomial. Master's thesis, Universiteit van Amsterdam, 2012.

[Sch94] W. Schmitt. Incidence Hopf algebras. *Journal of Pure and Applied Algebra*, 96:299–230, 1994.

[Sta73] Richard P. Stanley. Acyclic orientations of graphs. *Discrete Math.*, 5:171–178, 1973.

[Sta95] Richard P. Stanley. A symmetric function generalization of the chromatic polynomial of a graph. *Advances in Math.*, 111:166–194, 1995.

[Tak71] M. Takeuchi. Free Hopf algebras generated by coalgebras. *J. Math. Soc. Japan*, 23:561–582, 1971.