# Semi-pointed partition posets

Bérénice Delcroix-Oger

► To cite this version:

Bérénice Delcroix-Oger. Semi-pointed partition posets. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.321-332, 10.46298/dmtcs.2532 . hal-01337814

HAL Id: hal-01337814

https://hal.science/hal-01337814

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
Semi-pointed partition posets

Bérénice Delcroix-Oger¹†

¹Institut Camille Jordan, Lyon, France

**Abstract.** We present here a family of posets which generalizes both partition and pointed partition posets. After a short description of these new posets, we show that they are Cohen-Macaulay, compute their Moebius numbers and their characteristic polynomials. The characteristic polynomials are obtained using a combinatorial interpretation of the incidence Hopf algebra associated to these posets.

**Résumé.** Nous introduisons ici une famille de posets qui généralise à la fois les poset de partitions et les posets de partitions pointées. Après une description rapide de ces nouveaux posets, nous montrons qu’ils sont Cohen-Macaulay et nous calculons leurs nombres de Moebius et leurs polynômes caractéristiques. Ces derniers sont obtenus grâce à une interprétation combinatoire de l’algèbre de Hopf d’incidence associée à ces posets.

**Keywords:** Partition, Incidence Hopf Algebra, Moebius number, characteristic polynomial

The partition poset on a finite set $V$ is the well-known poset of partitions of $V$, endowed with the following partial order: a partition $P$ is smaller than another partition $Q$ if the parts of $Q$ are unions of parts of $P$. A variant of partition posets, called *pointed partition posets*, has been studied by F. Chapoton and B. Vallette in [CV06] and [Val07]. A pointed partition of a set $V$ is a partition of $V$, with a distinguished element for each of its parts. The pointed partition poset on $V$ is then the set of pointed partitions of $V$, where a pointed partition $P$ is smaller than another pointed partition $Q$ if and only if the parts of $Q$ are unions of parts of $P$ and the set of pointed elements of $Q$ is contained in the set of pointed elements of $P$.

We study here a generalisation of both partition posets and pointed partition posets, called *semi-pointed partition posets*. These posets naturally arise in the study of pointed hypertree posets (cf. [DO14]). After a short description of semi-pointed partition posets, we show that these posets are Cohen-Macaulay thanks to total semi-modularity. Then, it is usual in that case to compute the Moebius numbers, which are equal, up to a sign, to the dimension of their unique non trivial homology group. In the case of semi-pointed partition posets, we obtain a closed formula for Moebius numbers, which factorizes nicely and incites us to look further by computing a generalization of Moebius numbers: the characteristic polynomials.

These characteristic polynomials can be computed as characters on the incidence Hopf algebra associated to the hereditary family generated by maximal intervals in semi-pointed partition posets. This relies on the combinatorial interpretation of the incidence Hopf algebra as a Hopf algebra of generating series.

<footnote>†Email: oger@math.univ-lyon1.fr.</footnote>
# 1 Semi-pointed partitions posets: presentation and Cohen-Macaulayness

Let us first define semi-pointed partition posets and show that their homology is concentrated in maximal degree.

## 1.1 Semi-pointed partitions posets

**Definition 1.1** Let $V = V_1 \sqcup V_2$ be a set of cardinality $n$, with $V_1$ of cardinality $\ell$ and $V_2$ of cardinality $p$ ($\ell + p = n$). A semi-pointed partition of $V = V_1 \sqcup V_2$ is a partition of $V$ such that each part in the partition satisfies:

* If all elements in the part belong to $V_1$, the part is pointed in one of its elements,

* If all elements in the part belong to $V_2$, the part is not pointed,

* If some elements in the part belong to $V_1$ and others to $V_2$, the part can be either not pointed or pointed in one of its elements belonging to $V_1$.

A $(n, \ell)$-semi-pointed partition is a semi-pointed partition of $V = \{1, \dots, n\}$ with $V_1 = \{1, \dots, \ell\}$ and $V_2 = \{\ell + 1, \dots, n\}$.

We will write a tilde over the pointed element in each part.

**Example 1.2** There are 35 (4, 2)-semi-pointed partitions.

**Remark 1.3** A structure of 2-coloured operad is hidden in the decoration of partitions described in the definition of semi-pointed partitions.

Let $V$ be a finite set. The set of semi-pointed partitions on $V = V_1 \sqcup V_2$ can be endowed with the following partial order:

**Definition 1.4** Let $P$ and $Q$ be two semi-pointed partitions. The partition $P$ is smaller than the partition $Q$ if and only if the parts of $Q$ are unions of parts of $P$ and the pointing of parts of $Q$ is "inherited" from the ones of $P$, meaning that if a part $q$ of $Q$ is union of parts $(p_1, \dots, p_n)$ of $P$, then the pointing of $q$ is chosen in those of the $p_i$, given that if one of the $p_i$ is not pointed, the part $q$ can be not pointed. We denote by $\preceq$ the order on the posets.

**Example 1.5** With $V_1 = \{1, 2, 3\}$ et $V_2 = \{4, 5\}$, the semi-pointed partition $\{\tilde{1}, 2\}\{3, 4\}\{5\}$ is smaller than the semi-pointed partition $\{\tilde{1}, 2, 3, 4\}\{5\}$ but cannot be compared to the semi-pointed partition $\{1, 2, \bar{3}, 4\}\{5\}$.

We denote by $\Pi_{V,V_1}$ the poset of semi-pointed partitions of $V = V_1 \sqcup V_2$ bounded by the addition of a greatest element $\hat{1}$ and $\Pi_{n,\ell}$ the poset of $(n, \ell)$-semi-pointed partitions bounded by the addition of a greatest element $\hat{1}$. The maximal intervals in $\Pi_{n,\ell} - \hat{1}$ whose greatest element is pointed are all isomorphic: we write $\Pi_{n,\ell}^1$ for the maximal interval in $\Pi_{n,\ell}$ whose greatest element is pointed in 1. We also write $\Pi_{n,\ell}^0$ for the maximal interval in $\Pi_{n,\ell} - \hat{1}$ whose greatest element is not pointed.

On Figure 1 is represented the poset $\Pi_{3,1}$. The least element of the poset $\Pi_{V,V_1}$, which is the partition whose parts are of cardinality 1, endowed with the only possible pointing, will be denoted by $\pi_{V,V_1}$.
**Remark 1.6** The poset $\Pi_{n,0}^0$ is the poset of partitions of $\{1, \dots, n\}$.

The posets $\Pi_{n,n}$ and $\Pi_{n,n-1}$ are two posets isomorphic to the pointed partition poset on $\{1, \dots, n\}$. It is clear for the first poset from the definitions. For the second poset, it comes by identifying non pointed parts with parts pointed in the last element $n$.

<figure><img src="image_2.png" /><figcaption>**Figure 1:** The poset $\Pi_{3,1}$.</figcaption></figure>

## 1.2 Cohen-Macaulayness

We now introduce the first important property of semi-pointed partition posets. The reader can refer to [Wac07] for an introduction to poset topology. A poset *P* is *totally semi-modular* if for any interval *I* in *P*, and for any elements *x*, *y* in *I* which cover an element *z* in *I*, there exists an element *t* in *I* covering *x* and *y*. It follows from the article of A. Björner and M. Wachs [BW83] that any bounded, graded totally semi-modular poset is Cohen-Macaulay, i.e. has its homology concentrated in the highest degree. We then prove the following proposition by total semi-modularity:

**Proposition 1.7** *The posets $\Pi_{n,l}$, $\Pi_{n,l}^0$ and $\Pi_{n,l}^1$ are totally semi-modular and Cohen-Macaulay.*

As a consequence of this proposition, the usual Moebius numbers on these posets are, up to a sign, the dimension of the unique non vanishing homology group associated to the posets.

# 2 Moebius numbers of semi-pointed partition posets

The aim of this section is to compute the dimension of the unique non vanishing homology group of $\Pi_{n,l}$, which is, up to a sign, the Moebius number of the poset. We use the definition of the Euler characteristic to link Moebius numbers with alternating sums of dimensions of spaces of strict chains. These alternating sums are obtained by looking at the value in $k = -1$ of some polynomials counting the numbers of large $k$-chains, for any non-negative integer $k$.

## 2.1 From strict to large chains (i)

Let us first describe how the computation of Moebius numbers can be reduced to the computation of large $k$-chains. This reasoning is inspired by the reasoning of the article [Oge13] and can be adapted to many

<footnote>(i)Here, "strict chains" means "strictly increasing chains" and "large chains" means "weakly increasing chains".</footnote>
cases of graded Cohen-Macaulay posets.

As the poset is Cohen-Macaulay, the absolute value of its Moebius number is the dimension of its only homology group. It can be obtained as the alternating sum of the dimension of the vector space generated by strict chains. After introducing some notations, we link that sum with large chains in the poset.

For a family of sets $S_{V_1, V_2}$ depending on the pair $(V_1, V_2)$, we introduce the following generating series:

$$F_S = \sum_{\ell \ge 0, p \ge 0} S_{\{1, \dots, \ell\}, \{\ell+1, \dots, \ell+p\}} \frac{x^\ell}{\ell!} \frac{y^p}{p!}.$$

Let $k$ be an integer and $V = V_1 \cup V_2$ a finite set. The set of strict $k$-chains of semi-pointed partitions in $\Pi_{V,V_1}$ is the set of $k$-tuples $(a_1, \dots, a_k)$ where $a_i$ is a non extremal element of $\Pi_{V,V_1}$ and $a_i \prec a_{i+1}$. The associated generating series is denoted by $C_k^s$. The set of large $k$-chains of semi-pointed partitions in $\Pi_{V,V_1}$ is the set of $k$-tuples $(a_1, \dots, a_k)$ where $a_i$ is an element in $\Pi_{V,V_1}$, different from $\hat{1}$ and $a_i \le a_{i+1}$. The associated generating series is denoted by $C_k^g$. The set of strict $k$-chains with multiplicity of semi-pointed partitions in $\Pi_{V,V_1} - \hat{1}$ is the set of pairs $((a_1, \dots, a_k), m)$ made of a maximal element $m$ in $\Pi_{V,V_1} - \hat{1}$ (which is a semi-partition with only one part) and a $k$-tuple $(a_1, \dots, a_k)$ where $a_i \in ]\pi_{V,V_1}; m[$, $\forall i \in \{0, \dots, k-1\}$, and $a_i \prec a_{i+1}$, $\forall i \in \{0, \dots, k-1\}$. The associated generating series is denoted by $C_k^{sl}$. Finally, we call large $k$-chains with multiplicity the set of pairs $((a_1, \dots, a_k), m)$ made of a maximal element $m$ in $\Pi_{V,V_1} - \hat{1}$ and a large $k$-chain $(a_1, \dots, a_k)$ in $[\pi_{V,V_1}; m]$, or equivalently, the set of large $k$-chains in each maximal interval in $\Pi_{n,\ell} - \hat{1}$, counted with multiplicity. The associated generating series is denoted by $C_k^l$.

**Example 2.1** In $\Pi_{3,1}$ for instance, the longest strict chains are of length 2. An example of a strict 2-chain is $((\tilde{1}, 2)\{3\}, (\tilde{1}, 2, 3))$.

An example of a large 3-chain is $((\tilde{1})\{2\}\{3\}, (\tilde{1})\{2\}\{3\}, (\tilde{1}, 2)\{3\})$.

An example of a strict 1-chain with multiplicity is $((\tilde{1}, 2)\{3\}, \{1, 2, 3\})$, which means that we consider the chain $((\tilde{1}, 2)\{3\})$ as a chain of $[\tilde{1}\{2\}\{3\}; \{1, 2, 3\}]$, different from the chain $((\tilde{1}, 2)\{3\})$ as a chain of $[\tilde{1}\{2\}\{3\}; \{1, 2, 3\}]$.

An example of a large 4-chain with multiplicity is:

$$((\tilde{1})\{2\}\{3\}, (\tilde{1})\{2\}\{3\}, (\tilde{1}, 2)\{3\}, (\tilde{1}, 2, 3), (\tilde{1}, 2, 3)).$$

We link these generating series by using the set $M_{k,s}$ of words on $\{0, 1\}$ and of length $k$, containing $s$ letters "1". As this set has cardinality $\binom{k}{s}$, we obtain:

**Proposition 2.2** Let $k$ be a positive integer. The generating series $C_k^g$, $C_k^l$, $C_k^s$ and $C_k^{sl}$ satisfy:

$$C_k^g \cong \sum_{i \ge 0} C_i^s \times \binom{k}{i}, \qquad (1)$$

and

$$C_k^l \cong \sum_{i \ge 1} C_{i-1}^{sl} \times \binom{k}{i} + \sum_{i \ge 0} C_i^{sl} \times \binom{k}{i}. \qquad (2)$$
**Proof:** We encode repetitions in large chains thanks to words. If $(a_1, \dots, a_k)$ is a large $k$-chain in $\Pi_{n,l}$, it is equivalent to the data of a strict $s$-chain $(a_{i_1}, \dots, a_{i_s})$, obtained by deleting repetitions and the least element $\pi_{V,V_1}$ in $(a_1, \dots, a_k)$ and a word $u_1 \dots u_k$ of $M_{k,s}$ such that:

* $u_k = 0$ if $a_k = \pi_{V,V_1}$, 1 otherwise;

* $u_j = 0$ if $a_j = a_{j+1}$, 1 otherwise, for $1 \le j \le k-1$.

If $((a_1, \dots, a_k), m)$ is a large $k$-chain with multiplicity, in $[\pi_{V,V_1}, m]$, it is equivalent to the data of a strict $s$-chain with multiplicity $((a_{i_1}, \dots, a_{i_s}), m)$ obtained by deleting repetitions, $m$ and the least element $\pi_{V,V_1}$ in $(a_1, \dots, a_k)$ and a word of $M_{k-1,s}$ if the chain contains $\pi_{V,V_1}$ and of $M_{k,s}$ otherwise. $\square$

The length of a strict chain in $\Pi_{n,l}$ is at most $n-2$: the series $C_k^g$ and $C_k^l$ are then polynomials in $k$. We can thus evaluate these series at $k = -1$. Considering the Euler characteristic of the poset, we obtain:

**Proposition 2.3** *The dimension of the homology of $\Pi_{n,l}$ is given, up to a sign, by the value at $k = -1$ of $C_k^g$. The dimension of the direct sum of homologies of maximal intervals in $\Pi_{n,l} - \hat{1}$ is given, up to a sign, by the value at $k = -2$ of $C_k^l$.*

Let us remark that the same reasoning can be applied to maximal intervals in the poset.

## 2.2 Dimension of the homology of the semi-pointed partition poset

Thanks to the previous subsection, the problem has moved from computing Moebius numbers to computing large $k$-chains, for a positive integer $k$. Once found the polynomial $P(X)$ such that $P(k)$ corresponds to the number of large $k$-chains in the chosen poset, the Moebius number of the poset will be given by $P(-1)$. In an abuse of notation, we will always keep the same notations for series, even when evaluated in negative integers.

Let us fix a positive integer $k$. To obtain relations between generating series, we also need the generating series $C_k^\bullet$ (resp. $C_k^\times$) of sets of large $k$-chains in $\Pi_{V_1 \cup V_2, V_1}$, whose maximal element is a partition with only one part, which is pointed (resp. non pointed). The generating series then satisfy:

**Proposition 2.4** *For all integers $k$, the generating series $C_k^\bullet$, $C_k^\times$, $C_k^g$ and $C_k^l$ satisfy the following relations:*

$$C_k^\bullet = C_{k-1}^\bullet \times e^{C_{k-1}^\bullet + C_{k-1}^\times}, \quad (3)$$

$$C_k^\times = e^{C_{k-1}^\bullet} (e^{C_{k-1}^\times} - 1), \quad (4)$$

$$C_k^g = e(C_k^\bullet + C_k^\times) - 1, \quad (5)$$

$$C_{k-1}^l = C_k^\bullet + C_k^\times. \quad (6)$$

We prove this proposition in a combinatorial way for positive integers and the proposition is extended by polynomiality to any integers.

Thanks to these relations, we can now compute closed formulas for the dimension of the homology of semi-pointed partition posets. We first determine closed formulas for these series:
**Proposition 2.5** The series $C_{-1}^{\bullet}$ and $C_{-1}^{g}$ are linked by:

$$x = C_{-1}^{\bullet} (1 + C_{-1}^{g}), \qquad (7)$$

$$y = C_{-1}^{g} + 1 - e^{C_{-1}^{\bullet}}. \qquad (8)$$

**Proof:** The coefficient of $\frac{x^\ell y^p}{\ell! p!}$ in $C_1^\bullet$ (resp. $C_1^\times$) corresponds to the number of large 1-chains whose greatest element has only one pointed (resp. non pointed) part, with the set of possibly pointed element of size $\ell$ and the set of non pointed elements of size $p$. There are $\ell$ such chains in the pointed case and 1 in the non pointed case if $p \neq 0, 0$ otherwise. We thus obtain $C_1^\bullet = xe^{x+y}$ and $C_1^\times = e^{x+y} - e^x$.

Using the previous relations between series, (3) and (4), for $k=1$ gives:

$$\left\{ \begin{array}{l} xe^{x+y} = C_0^{\bullet}e^{C_0^{\bullet}+C_0^{\times}}, \\ e^{x+y} - e^x = e^{C_0^{\bullet}+C_0^{\times}} - e^{C_0^{\bullet}}. \end{array} \right.$$

Solving this system gives $C_0^\bullet = x$ and $C_0^\times = y$. Replacing these values in Equations (3), (4) and (5) for $k=0$ implies the result. □

**Remark 2.6** The coefficient of $x^\ell y^{n-\ell}$ in $C_1^g$ gives the number of semi-pointed partitions in $\Pi_{n,\ell}$. This series satisfies:

$$C_1^g = \exp((x+1)e^{x+y} - e^x) - 1.$$

Equations (7) and (8) enable us to obtain the following implicit equation:

$$x = C_{-1}^{\bullet} (y + e^{C_{-1}^{\bullet}}). \qquad (9)$$

Now we have equations for the series, we can compute closed formulas for their coefficients.

**Theorem 2.7** The generating series $C_{-1}^{\bullet}$, corresponding to the dimension of the only homology group of maximal intervals in semi-pointed partition posets, whose greatest element has only one pointed part, $C_{-1}^{g}$, corresponding to the dimension of the homology of the augmented poset, and $C_{-2}^{l}$, corresponding to the sum of the dimensions of the unique homology group of maximal intervals, satisfy:

$$C_{-1}^{\bullet} = \sum_{\ell \ge 1, p \ge 0} (-1)^{\ell+p-1} \frac{(\ell+p-1)!}{(\ell-1)!} (\ell+p)^{\ell-1} \frac{x^{\ell} y^{p}}{\ell! p!}, \qquad (10)$$

$$C_{-1}^{g} = \sum_{\ell \ge 1, p \ge 0} (-1)^{\ell+p-1} \frac{(\ell+p-1)!}{(\ell-1)!} (\ell+p-1)^{\ell-1} \frac{x^{\ell} y^{p}}{\ell! p!}, \qquad (11)$$

$$C_{-2}^{l} = \sum_{\substack{\ell \ge 0, p \ge 0 \\ \ell+p \ge 1}} (-1)^{\ell+p-1} \frac{(\ell+p-1)!}{\ell!} (\ell+p)^{\ell} \frac{x^{\ell} y^{p}}{\ell! p!}. \qquad (12)$$

**Proof:**
* To compute coefficients of $C_{-1}^{\bullet}$ and $C_{-1}^{g}$, we apply Lagrange inversion theorem respectively to Equation (9) and Equation (8).

* The last equation is obtained using the following lemma:

**Lemma 2.8** The generating series $C_{-2}^l$ and $C_{-1}^\bullet$ satisfy the following differential equation:

$$x \frac{\partial C_{-2}^l}{\partial x} = x \frac{\partial C_{-1}^\bullet}{\partial x} + y \frac{\partial C_{-1}^\bullet}{\partial y}.$$

The value of the coefficient of $x^0$ in the generating series $C_{-2}^l$ is moreover given by the Moebius numbers of partition posets.

This differential equation is obtained by deriving Equation (9) with respect to $x$ and $y$ and Equation (8) with respect to $x$, and then using Equations (6), (7) and (8). The result immediately follows.

□

A consequence of this theorem is the following corollary, whose proof uses methods from the article of D. Zvonkine [Zvo04]:

**Corollary 2.9** Let us define the following family of generating series, for $i \ge 1$:

$$f_i(x, y) = \sum_{\ell \ge 1, p \ge 0} \frac{(\ell + p - 1)!}{(\ell - i)!} (\ell + p)^{\ell - i} \frac{x^\ell y^p}{\ell! p!},$$

This families then satisfy the relation $f_1^i = i \times f_i$.

This relation can be rewritten, for $n, \ell \ge 1$ as:

$$\sum_{\substack{n_j=1, \\ n_j \ge 1}}^{i} \sum_{\substack{\ell_j=\ell, \\ \ell_j \ge 1}}^{i} \prod_{j=1}^{i} \binom{n_j}{\ell_j} \frac{n_j^{\ell_j-2}}{(\ell_j-1)!} = i \times \binom{n}{\ell} \frac{n^{\ell-i-1}}{(\ell-i)!}.$$

**Proof of Lemma 2.9:** We prove this lemma by induction on $I$. This is trivially true for $i = 1$. Let us first remark that $f_1(x, y) = -C_{-1}^{\bullet}(-x, -y)$, due to expression of Theorem 2.7. Then Equation (9) gives the following functional equation for $f_1$:

$$(x + yf_1)e^{f_1} = f_1. \qquad (13)$$

No generating series in the family has non-zero constant term. We introduce the following operators for all generating series $f$ in variables $x$ and $y$:

$$D_x f = x \frac{\partial f}{\partial x}, \quad D_y f = y \frac{\partial f}{\partial y} \quad \text{and} \quad D f = D_x f + D_y f.$$
Let us now show the equality for $i = 2$. Looking at coefficients in the series, we obtain $Df_2 = D_x f_1 - f_1$. To show the theorem, we thus have to show that $D(f_1^2) = 2(D_x f_1 - f_1)$. The derivative of Equation (13) with respect to $x$ and $y$ gives:

$$ 
\begin{aligned}
D_x f_1 &= f_1 D_x f_1 + (x + y D_x f_1) e^{f_1}, \\
D_y f_1 &= f_1 D_y f_1 + y f_1 e^{f_1} + y D_y f_1 e^{f_1}.
\end{aligned}
$$

These equations imply $xD_y f_1 = yf_1 D_x f_1$.

Then, we obtain successively:

$$ 
\begin{aligned}
\frac{1}{2} D(f_1^2) &= f_1 D_x f_1 + f_1 D_y f_1 = f_1 D_x f_1 \left(1 + \frac{f_1}{x} y\right) \\
&= \left(D_x f_1 - x e^{f_1} - y D_x f_1 e^{f_1}\right) \left(1 + \frac{f_1}{x} y\right).
\end{aligned}
$$

This expression reduces to $D_x f_1 - f_1$ using Equation (13).

Let us now consider $i \ge 2$. Suppose that for all $p < i$, $f_1^p = p \times f_p$. Looking at the coefficients of the derivative $D$ of $f_i - f_{i-1}$, we obtain:

$$ D(f_i - f_{i-1}) = -(i-1)f_{i-1} - D_y f_{i-1}. $$

Using the induction hypothesis, we have:

$$ D(f_i) = f_1^{i-2} D_x f_1 - f_1^{i-1} $$

and, on the other side,

$$ D\left(\frac{f_1^i}{i}\right) = f_1^{i-1} D f_1. $$

Hence, the result is equivalent to the equation $D_x f_1 - f_1 = f_1 D f_1$ which was proven in the case $i = 2$.

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

We have seen in this section that Moebius numbers can be described by pretty closed formulas (10), (11) and (12). This encourages us to look at a generalization of these Moebius numbers: characteristic polynomials.

## 3 Incidence Hopf algebra and characteristic polynomials of semi-pointed partition posets

In this section, we apply to the posets of semi-pointed partitions the construction of W. Schmitt, presented in his article [Sch94], of an incidence Hopf algebra associated to a family of posets satisfying some axioms. After computing the coproduct in this Hopf algebra, we identify the Hopf algebra with an Hopf algebra of generating series. This identification enables us to compute the characteristic polynomials.
## 3.1 Description of the incidence Hopf algebra

We briefly describe in this subsection the construction of the incidence Hopf algebra.

We consider maximal intervals in $\Pi_{n,\ell} - \hat{1}$. Using the notations introduced in the first section, we write $\Pi_{n,\ell}^{\theta}$ for $\Pi_{n,\ell}^{0}$ or $\Pi_{n,\ell}^{1}$. We denote by $\pi_{n,\ell}$ the least element of $\Pi_{n,\ell}^{\theta}$ (whose parts are of size 1) and $M_{n,\ell}^{\theta}$ the greatest element (with only one part).

The following proposition ensures that the family $\mathcal{F}$ of direct products of maximal intervals in a semi-pointed partition poset is an hereditary family:

**Proposition 3.1 (Intervals in semi-pointed partition posets)** Let $P$ be a semi-pointed partition in the poset $\Pi_{n,\ell}^{\theta}$. The interval $[p; M_{n,\ell}^{\theta}]$ in $\Pi_{n,\ell}^{\theta}$ is isomorphic to a poset of semi-pointed partitions $\Pi_{j,l}^{\theta}$, where $j$ is the number of parts in $P$ and $l$ is the number of pointed parts in $P$.

The interval $[\pi_{n,\ell}; p]$ is isomorphic to a product of semi-pointed partitions poset with a factor $\Pi_{n_j, \ell_j}^1$ for every pointed part of $P$ of size $n_j$ with $\ell_j$ elements pointed in $\pi_{n,\ell}$ and a factor $\Pi_{n_j, \ell_j}^0$ for every non-pointed part of $P$ of size $n_j$ with $\ell_j$ elements pointed in $\pi_{n,\ell}$.

We consider the equivalence relation $\equiv$ generated by $P \equiv P \times U$ if $|U| = 1$ and $P \equiv Q$ if there exists four sets $V_1^P, V_2^P, V_1^Q, V_2^Q$, such that the elements of $P$ (resp. $Q$) are semi-pointed partitions of $\Pi_{V_1^P \cup V_2^P, V_1^P}^P$ (resp. of $\Pi_{V_1^Q \cup V_2^Q, V_1^Q}^Q$) and such that there exists a poset isomorphism between $P$ and $Q$ sending pointed elements of parts of elements of $P$, $V_1^P$, on pointed elements of parts of elements of $Q$, $V_1^Q$.

This relation is a Hopf relation. Considering the hereditary family $\mathcal{F}$ and the Hopf relation $\equiv$, we can apply the construction of W. Schmitt presented in [Sch94] to obtain an incidence Hopf algebra $\mathcal{I}$. This Hopf algebra is generated as an algebra by the set of equivalence class of maximal intervals in semi-pointed partition posets, $\Pi_{n,\ell}^{\theta}$, according to Proposition 3.1.

## 3.2 Computation of the coproduct

We would like to give a more precise description of the coproduct in the incidence Hopf algebra $\mathcal{I}$. Using the decomposition of intervals described in Proposition 3.1, we obtain the following description of the coproduct:

$$ \Delta(\Pi_{n,\ell}^{\theta}) = \sum_{j=1}^{n} \sum_{\substack{n_1, \dots, n_j \ge 1, \\ \sum_{i=1}^{j} n_i = n}} \sum_{\substack{\ell_1, \dots, \ell_j \ge 0 \\ \sum_{i=1}^{j} \ell_i = \ell}} \sum_{\substack{\theta_1, \dots, \theta_j \in \{0;1\} \\ \theta \le \sum_{i=1}^{j} \theta_i \le j-1+\theta}} c_{n,\ell}^{\theta} \prod_{i=1}^{j} \Pi_{n_i, \ell_i}^{\theta_i} \otimes \prod_{j, \sum_{i=1}^{j} \theta_i} \Pi_{j, \sum_{i=1}^{j} \theta_i}^{\theta} $$

where $c_{n,\ell}^{\theta}$ is the number of partitions having $j$ parts, of size $n_1, \dots, n_j$, with in each part $\ell_1, \dots, \ell_j$ elements pointed in $\pi_{n,\ell}$ and with the $i$th part pointed if $\theta_i$ is 1 and non pointed otherwise.

Counting the number of partitions $c_{n,\ell}^{\theta}$ gives the following theorem:

**Theorem 3.2** The coproduct in the incidence Hopf algebra $\mathcal{I}$ of semi-pointed partition poset is given by:

$$ \Delta \left( \frac{\Pi_{k+l,k}^{\theta}}{l!(k-\theta)!} \right) = \sum_{p+q \ge 1} \sum_{(l_i, k_i)} \prod_{i=1}^{p} \frac{\Pi_{l_i+k_i, k_i}^{1}}{l_i!(k_i-1)!} \prod_{i=p+1}^{p+q} \frac{\Pi_{l_i+k_i, k_i}^{0}}{l_i!k_i!} \otimes \frac{\Pi_{p+q,p}^{\theta}}{q!(p-\theta)!}, \quad (14) $$
where the second sum runs over the $p+q$-tuples $(l_1, \dots, l_{p+q})$ and $(k_1, \dots, k_{p+q})$ satisfying $l_1, \dots, l_p \ge 0$, $l_{p+1}, \dots, l_{p+q} \ge 1$, $k_1, \dots, k_p \ge 1$, $k_{p+1}, \dots, k_{p+q} \ge 0$, $\sum_{i=1}^{p+q} k_i = k$ and $\sum_{i=1}^{p+q} l_i = l$.

**Proof (sketch):** In the non pointed case ($\theta = 0$), the coefficient $c_{n,\ell}^{\theta}$ is given by:

$$ \frac{k!l! \prod_{i=1}^{p} k_i}{\prod_{i=1}^{p+q} k_i!l_i!p!q!} $$

Indeed, we make $p+q$ packets of elements and the first $p$ packets have to be pointed. For the pointed case ($\theta = 1$), to ensure that the greatest part is pointed, for instance in 1, we fix that the first packet is pointed in 1. The coefficient $c_{n,\ell}^{\theta}$ is then given by:

$$ \frac{(k-1)!!l! \prod_{i=2}^{p} k_i}{(k_1-1)! \prod_{i=2}^{p+q} k_i!l_i!p!q!} $$

□

This expression of the coproduct enables us to give a combinatorial interpretation of the incidence Hopf algebra $\mathcal{I}$.

## 3.3 Computation of characteristic polynomials

The aim of this part is the computation of the characteristic polynomial.

**Definition 3.3** The characteristic polynomial of a bounded poset $P$ with minimum $\hat{0}$ and maximum $\hat{1}$ is given by:

$$ \chi_P = \sum_{x \in P} \mu([\hat{0}, x]) t^{\mathrm{rk}(\hat{1}) - \mathrm{rk}(x)} $$

We now give an interpretation of the computation of the coproduct in the previous subsection. This interpretation will help us computing characteristic polynomials.

**Proposition 3.4** The incidence Hopf algebra $\mathcal{I}$ of semi-pointed partition posets is isomorphic to the Hopf algebra structure on the polynomial algebra in the variables $(a_{k,l}^0)_{k,l \ge 1, o \in \{0,1\}}$ given by the composition of pairs $(F, G)$ of formal series of the following shape:

$$ \left\{ \begin{array}{l} F = x + \sum_{l,k \ge 1} a_{k,l}^{0} \frac{x^k}{k!} \frac{y^l}{l!}, \\ G = y + \sum_{l,k \ge 1} k a_{k,l}^{1} \frac{x^k}{k!} \frac{y^l}{l!}. \end{array} \right. $$

As a corollary, the Moebius numbers of the intervals $\Pi_{n,\ell}^0$ and $\Pi_{n,\ell}^1$ are respectively the coefficients of $A$ and $B$, where $A$ and $B$ satisfy:

$$ \left\{ \begin{array}{l} (e^B - 1)e^A = x, \\ Ae^{A+B} = y. \end{array} \right. $$

By comparison with the equations of Proposition 2.4, we obtain another proof of the expressions for Moebius numbers computed in the first section: $A = C_{-1}^*$ and $B = C_{-1}^*$.
The characteristic polynomials $\chi^{\bullet}$ and $\chi^{\times}$ of $\Pi_{n,\ell}^{1}$ and $\Pi_{n,\ell}^{0}$ are then given by:

$$ \left\{ \begin{array}{l} \chi^{\bullet} = \frac{(e^{t\mathbf{C}_{-1}^{\times}-1})e^{t\mathbf{C}_{-1}^{\bullet}}}{t}, \\ \chi^{\times} = \mathbf{C}_{-1}^{\bullet}e^{t(\mathbf{C}_{-1}^{\times}+\mathbf{C}_{-1}^{\times})}. \end{array} \right. $$

These relations implies the following proposition:

**Proposition 3.5** The characteristic polynomial of the interval $\Pi_{n,\ell}^{1}$ is given by:

$$ (t-1)(t-\ell-p)^{\ell-2} \prod_{i=\ell+1}^{\ell+p} (t-i). \qquad (15) $$

The characteristic polynomial of the poset $\Pi_{n,\ell} - \mathbb{1}$ is given by:

$$ (t - \ell - p)^{\ell - 1} \prod_{i=\ell+1}^{\ell+p} (t - i). \qquad (16) $$

The characteristic polynomial of the poset $\Pi_{n,\ell}$ is given by:

$$ t \times (t - \ell - p)^{\ell - 1} \prod_{i=\ell+1}^{\ell+p} (t - i) - (1 - \ell - p)^{\ell - 1} \prod_{i=\ell+1}^{\ell+p} (1 - i). \qquad (17) $$

**Remark 3.6** The characteristic polynomial of the poset $\Pi_{n,\ell}^{1}$ does not factorize.

**Proof:**

* We use the following relation between $\mathbf{C}_{-1}^{\bullet}$ and $\mathbf{C}_{-1}^{\times}$ obtained from Proposition 2.4:

$$ e^{\mathbf{C}_{-1}^{\bullet} + \mathbf{C}_{-1}^{\times}} = y + e^{\mathbf{C}_{-1}^{\bullet}}. $$

Then, the coefficient of $x^{l}y^{p}$ in $\chi^{\bullet}$ is given by the following residue:

$$ I = \iint \mathbf{C}_{-1}^{\bullet} (y + e^{\mathbf{C}_{-1}^{\bullet}})^t \frac{dx}{x^{l+1}} \frac{dy}{y^{p+1}}. $$

We use the substitution $z = \mathbf{C}_{-1}^{\bullet}$ to obtain:

$$ \begin{aligned} I &= \iint \frac{z(y + e^z)^t}{(y + e^z)^{l+1}} ((y + e^z) + ze^z) \frac{dz}{z^{l+1}} \frac{dy}{y^{p+1}} \\ I &= \iint z(y + e^z)^{t-l} \frac{dz}{z^{l+1}} \frac{dy}{y^{p+1}} + \iint z^2(y + e^z)^{t-l-1} e^z \frac{dz}{z^{l+1}} \frac{dy}{y^{p+1}}. \end{aligned} $$

We expand $(y+e^z)^{t-l}$ and $(y+e^z)^{t-l-1}$ and take the coefficient of $y^p$. The integral $I$ is then given by:

$$ I = \int \binom{t-l}{p} e^{(t-l-p)z} \frac{dz}{z^l} + \int \binom{t-l-1}{p} e^{(t-l-p)z} \frac{dz}{z^{l-1}} $$

As $\int e^{az} \frac{dz}{z^n} = \frac{a^{n-1}}{(n-1)!}$, this gives the result.
• The generating series $S$ of such characteristic polynomials can be seen as a generating series in $t$ whose coefficients are generating series in $x$ and $y$. Then, the coefficient of $t^{p-1}$ is the sum of Moebius numbers of partitions of $\Pi_{n,\ell}$ in $p$ parts, weighted by $x^\ell y^{n-\ell}$. We thus obtain the relation:

$$S = \frac{e^{t(\mathbf{C}_{-1}^{\bullet} + \mathbf{C}_{-1}^{\times})} - 1}{t}.$$

The result is obtained by applying Lagrange inversion formula to this relation.

• The characteristic polynomial of $\Pi_{n,\ell}$ is divisible by $(t - 1)$, as the poset is bounded, and only differs from $tS$ by its constant term. $\square$

## References

[BW83] Anders Björner and Michelle Wachs. On lexicographically shellable posets. *Trans. Amer. Math. Soc.*, 277(1):323–341, 1983.

[CV06] Frédéric Chapoton and Bruno Vallette. Pointed and multi-pointed partitions of type A and B. *J. Algebraic Combin.*, 23(4):295–316, 2006.

[DO14] Bérénice Delcroix-Oger. *Hyperarbres et Partitions semi-pointées : Aspects combinatoires, al-gébriques et homologiques*. PhD thesis, Université Lyon 1, 2014.

[Oge13] Bérénice Oger. Action of the symmetric groups on the homology of the hypertree posets. *J. Algebraic Combin.*, 38(4):915–945, 2013.

[Sch94] William R. Schmitt. Incidence Hopf algebras. *J. Pure Appl. Algebra*, 96(3):299–330, 1994.

[Val07] Bruno Vallette. Homology of generalized partition posets. *J. Pure Appl. Algebra*, 208(2):699–725, 2007.

[Wac07] Michelle L. Wachs. Poset topology: tools and applications. In *Geometric combinatorics*, volume 13 of *IAS/Park City Math. Ser.*, pages 497–615. Amer. Math. Soc., Providence, RI, 2007.

[Zvo04] Dimitri Zvonkine. An algebra of power series arising in the intersection theory of moduli spaces of curves and in the enumeration of ramified coverings of the sphere. *preprint*, 2004.