Sminaire Lotharingien de Combinatoire 72 (2015), Article B72d

INCIDENCE HOPF ALGEBRA OF THE HYPERTREE POSETS

BÉRÉNICE DELCROIX-OGER

Abstract. We adapt the computation of characters on incidence Hopf algebras introduced by Schmitt in the 1990s for families of bounded posets to a family mixing bounded and unbounded finite posets. This computation relies on the introduction of an auxiliary bialgebra: the coproduct in this bialgebra enables us to compute the convolution of some characters on the incidence Hopf algebra. After establishing a general result on the link between the bialgebra and the incidence Hopf algebra, we apply it to the family of hypertree posets and partition posets. This link for hypertree posets enables us to recover the Möbius numbers of these posets due to the coproduct in the associated bialgebra. This coproduct is computed using the number of hypertrees with fixed valency set and fixed edge sizes set.

Contents

Introduction

1. Generalities on posets and incidence Hopf algebras 2 2. Incidence Hopf algebra of triangle and diamond posets 4 3. Hypertree posets 8 4. Computation of the number of hypertrees with fixed parameters 11 5. Coproduct in the bialgebra 15 6. Computation of the Möbius number of augmented hypertree posets 18 References 21

Introduction

In 1994, Schmitt [13] defined the notion of incidence Hopf algebra associated with a given family of intervals satisfying some closure properties. Using the Hopf algebra structure, one can define a convolution on characters on this algebra. The Möbius number for posets of the family can then be computed using characters on the incidence Hopf algebra.

However, the incidence Hopf algebras of Schmitt are only defined for bounded posets. In the present article, we introduce a way to compute some characters for another type of finite posets, called the triangle and diamond posets. The diamond posets are bounded posets whereas the triangle posets have a least element but no greatest one. If we consider the hereditary family generated by the diamond posets and the augmented triangle posets, i.e., the triangle posets with an added greatest element, we can build the associated incidence Hopf algebra H. The coproduct in the non-counital bialgebra B generated by isomorphism classes in the hereditary family obtained from diamond and triangle posets can be linked with the coproduct of the incidence Hopf algebra H: this relation enables us to identify a computation involving maps from the bialgebra B to ℚ with the convolution of characters on the incidence Hopf algebra H. The advantage of this method is that the computation of such maps on the bialgebra B is, in most cases, easier. In the rest of the article, we will apply this method to hypertree posets. This method could also be applied to other families mixing bounded and unbounded posets, such as, for instance, to planar hypertree posets or pointed hypertree posets (cf. [10]), which are Cohen–Macaulay but for which there is still no known closed formula for their Möbius numbers.

Key words and phrases. poset, incidence Hopf algebra, hypertree, Möbius number.

In the first section of the article, we present generalities on posets and incidence Hopf algebras, before defining the bialgebra B in the second section.

In the third section of the article, we recall the notion of hypertrees. Hypergraphs have been introduced in 1989 by Berge [3] as a generalization of graphs. Hypertrees are hypergraphs satisfying a kind of connectedness and acyclicity. The set of hypertrees on a vertex set I can be endowed with a partial order given by union of edges. We provide a criterion on sequences (α_{i}) and (π_{j}) for the existence of a hypertree with α_{i} vertices of valency i and π_{j} edges of size j, which also appears in [1]. In the fourth section, we also present a formula for the number of hypertrees with a given edge-size and valency sets, which was already computed by Bacher [1] and by Bousquet-Mélou and Chapuy in [4] (see also [16]). We include the proof for self-containment, and refer the reader to the beginning of this section for more bibliographic details.

The results of the third and fourth section are then used in the fifth section to compute the coproduct in the bialgebra B_{HT} associated with the hypertree posets. The Möbius number of the poset of hypertrees on n vertices has been computed by McCammond and Meier in [8]. The hypertree poset has also been studied in [6]. Chapoton has computed its characteristic polynomial in [5], and he conjectured a formula for the action of the symmetric group on the homology of the hypertree poset. This conjecture has been proven by the author in [11]. In the last section, we propose a new way to compute the Möbius number of the hypertree posets. The advantage of this method is that it is algebraic, that it does not need the Cohen–Macaulayness of the posets, and that it uses the usual framework of incidence Hopf algebra. This leads to the enumerative formula (6.4) relating an alternating sum of quotients of factorials to the number of rooted trees on n − 1 vertices.

We thank the referees for their advice, which helped me to improve this paper.

1. Generalities on posets and incidence Hopf algebras

In this section, we review some general notions on posets and incidence Hopf algebras which will be needed in this article.

1.1. Generalities on posets. A poset is a set endowed with a partial order ≤. All posets considered here will be finite. The trivial poset is the poset which has only one element. If P is a poset in which x ≤ y, then the interval [x, y] is the set {z ∈ P : x ≤ z ≤ y}, and the half-open interval [x, y) is the set {z ∈ P : x ≤ z < y}. If P is an interval, P is called a bounded poset. In this case, its least and greatest elements will be denoted by ˆ0_{P} and ˆ1_{P}, respectively, or by ˆ0 and ˆ1 if there is no ambiguity.

Given a locally finite poset P, its Möbius function μ is recursively defined by

(1.1)  μ(x, x) = 1, for all x ∈ P,
(1.2)  μ(x, y) = − ∑_{x≤z<y} μ(x, z), for all x < y ∈ P.

The Möbius invariant, or Möbius number, of a finite bounded poset P is defined as

(1.3)  μ(P) := μ(ˆ0_{P} , ˆ1_{P}).

Conceptually, the Möbius number of a poset can be defined as the inverse of the zeta function with respect to convolution, as explained in Section 6.1.

Example 1.1. The Möbius number of the poset B_{n} of subsets of ⟦1, n⟧, ordered by inclusion, is (−1)^{n}.

1.2. Generalities on incidence Hopf algebra. All the definitions recalled here are extracted from the article [13] of Schmitt.

A family of intervals P is interval closed, if it is non-empty and, for all P ∈ P and x ≤ y ∈ P, the interval [x, y] belongs to P. An order compatible relation on an interval closed family P is an equivalence relation ∼ such that P ∼ Q if and only if there exists a bijection ϕ : P → Q such that [0_{P} , x] ∼ [0_{Q}, ϕ(x)] and [x, 1_{P}] ∼ [ϕ(x), 1_{Q}], for all x ∈ P. Isomorphism of posets is an example of an order compatible relation.

Given an order compatible relation ∼ on an interval closed family P, we consider the quotient set P/ ∼ and denote by [P] the ∼-equivalence class of a poset P ∈ P. We define a ℚ-coalgebra C(P) as follows.

Proposition 1.2 ([13, Theorem 3.1]). Let C(P) denote the free ℚ-module generated by P/ ∼. We define linear maps Δ : C(P) → C(P) ⊗ C(P) and ϵ : C(P) → ℚ by

(1.4)  Δ[P] = ∑_{x∈P}[0_{P} , x] ⊗ [x, 1_{P}]

and

(1.5)  ϵ[P] = δ_{|P |,1},

where δ_{i,j} is the Kronecker symbol. Then C(P) is a coalgebra with comultiplication Δ and counit ϵ.

The direct product of posets P_{1} and P_{2} is the Cartesian product P_{1} × P_{2} partially ordered by the relation (x_{1}, x_{2}) ≤ (y_{1}, y_{2}) if and only if x_{i} ≤ y_{i} in P_{i}, for i = 1, 2. A hereditary family is an interval closed family which is also closed under formation of direct products. Let ∼ be an order compatible relation on P which is also a semigroup congruence, i.e., whenever P ∼ Q in P, then P × R ∼ Q × R and R × P ∼ R × Q, for all R ∈ P. This relation is reduced if, whenever |R| = 1, then P × R ∼ R × P ∼ P: all trivial intervals are then equivalent and give a unit element for the product on the quotient. These hypotheses ensure that the product will be well defined on the quotient. The obtained unit is denoted by ν. An order compatible relation on a hereditary family P which is also a reduced congruence is called a Hopf relation on P. Isomorphism of posets is a Hopf relation.

Proposition 1.3 ([12]). Let ∼ be a Hopf relation on a hereditary family P. Then H(P) = (C(P), ×, Δ, ν, ϵ, S) is a Hopf algebra over ℚ, with the antipode S on an equivalence class of posets [P] in C(P) given by

(1.6)  S[P] = ∑_{k≥0} ∑_{\begin{matrix}x_{0}<···<x_{k} \\ x_{0}=0_{P} \\ x_{k}=1_{P} \end{matrix}}(−1)^{k} ∏_{i=1}^{k}[x_{i−1}, x_{i}].

Example 1.4. The incidence Hopf algebra generated by the family of posets of subsets of ⟦1, n⟧ is the polynomial algebra ℚ[x], endowed with the coproduct

Δ(x^{n}) = ∑_{k=0}^{n} \binom{n}{k}x^{k} ⊗ x^{n−k}.

We may consider the set of ℚ-linear algebra homomorphisms between H(P) and ℚ, which send the trivial poset to the unit of ℚ. These homomorphisms are called characters. The set of characters has a canonical group structure as follows. Given two characters ϕ and ψ and an element P of H(P), the convolution of ϕ and ψ is defined by

(1.7)  (ϕ ∗ ψ)(P) = ∑ ϕ(P_{(1)})ψ(P_{(2)}),

where Δ(P) = ∑ P_{(1)} ⊗ P_{(2)}, using Sweedler’s convention. The unit of this group is the counit of the Hopf algebra H(P).

2. Incidence Hopf algebra of triangle and diamond posets

In this section, we first present the incidence Hopf algebra of triangle and diamond posets. This incidence Hopf algebra is bigger than desired, as some open intervals of triangle posets are products of triangle posets but cannot be decomposed as products anymore once bounded by the addition of a greatest element. We thus present in the second subsection a non-counital bialgebra for the family of triangle and diamond posets, before linking characters on the incidence Hopf algebra of triangle and diamond posets with a computation in the bialgebra associated with triangle and diamond posets. This link is used in Section 6 to compute some characters on the hypertree posets.

2.1. Presentation of the triangle and diamond posets and their incidence Hopf algebra. Let us consider the family F_{0} consisting of posets {(d_{i})_{i≥1}, (t_{j})_{j≥3}}, such that d_{1} is the trivial poset, d_{i} is a finite interval for all i ≥ 2, and t_{j} is a finite poset with a least element but without a greatest element. The elements of the collection (d_{i})_{i≥1} will be called diamond posets, and the elements of (t_{j})_{j≥2} will be called triangle posets. We denote by t̂_{j} the augmented triangle poset, bounded by the addition of a greatest element ˆ1 to t_{j}. We moreover assume that:

Decomposition Property 1. Any closed interval in a diamond poset can be written as a direct product of diamond posets. Decomposition Property 2 a. Any closed interval in a triangle poset can be written as a direct product of diamond posets.

Decomposition Property 2 b. Any half-open interval [t, ˆ1) in an augmented triangle poset t̂_{j} is trivial or can be written as a direct product of triangle posets (see Figure 2.1).

We denote by F_{1} the smallest hereditary family containing F_{0}. Due to the decomposition properties, this family is constituted by direct products of diamond and triangle posets. As diamond and triangle posets admit a least element, all posets in F_{1} have a least element, some of these are intervals but others are not. We construct a hereditary family of intervals from this family.

To apply Schmitt’s construction, we now consider the smallest hereditary family F_{2} containing the elements of the family F_{1} augmented with a maximal element when they are not intervals. The family F_{2} then contains all the augmented elements of F_{1}, but also upper intervals in augmented triangle posets which cannot be rewritten as a direct product anymore, and direct products of these posets. The family F_{2} is then a hereditary family of intervals. We apply Schmitt’s construction to this family taking isomorphism of posets as a reduced order compatible relation to obtain the incidence Hopf algebra H_{⋄,▽}. We show that, under some assumptions, the calculus of some characters on H_{⋄,▽} can be reduced to a calculus in a smaller algebra.

2.2. A smaller bialgebra constructed on triangle and diamond posets. The family F_{1} is closed under direct product and under taking intervals, in the sense that any closed or half-open interval of a poset of the family belongs to the family. We construct a bialgebra from this family in the same way as Schmitt constructs an incidence Hopf algebra from a hereditary family of intervals, adapting the construction to the fact that some posets of the family have no greatest element. The bialgebra obtained is not counital on the right due to the absence of a greatest element in some poset. It would be interesting to generalize this construction to a family F of finite not necessarily bounded posets, closed under direct product and by taking down- and up-sets, i.e., such that, for any poset P and any x in P, the sets D(x) = {y ∈ P | y ≤ x} and U(x) = {y ∈ P | y ≥ x} belong to the family F. The obtained bialgebra would be counital on the right if and only if all posets in F have a greatest element and counital on the left if and only if all posets in F have a least element. However, as the posets considered in the rest of this paper have a least element, we will restrict ourselves to families of posets of this type.

Taking isomorphism of posets as an order compatible relation which is also a reduced congruence ∼, the set F̃_{1} = F_{1}/ ∼ is a monoid, with product induced by direct product of posets and identity element 1 equal to the class of any trivial poset. Let us denote by V (F_{1}) the free ℚ-module generated by F̃_{1}. The monoid structure on F̃_{1} induces an algebra structure on V (F_{1}), isomorphic to the monoid algebra of F̃_{1} over ℚ. As F_{1} is the set of monomials on triangle and diamond posets of F_{0}, the algebra V (F_{1}) is generated by isomorphism classes of triangle and diamond posets of F_{0}. Let us remark that all elements of F_{1} have a least element, but some of them do not have a greatest element. We define the coproduct on P ∈ F_{1} by

(2.1)  Δ(P) = ∑_{x∈P} D(x) ⊗ U(x),

•  •

Figure 2.1. Intervals in diamond and triangle posets: all of these are products of diamond posets, except half-open upper intervals in triangle posets, which are trivial or products of triangle posets.

where D(x) = {y ∈ P |y ≤ x} is called a down-set and U(x) = {y ∈ P |y ≥ x} is called an up-set, as above.

Let us remark that diamond posets are intervals, whereas triangle posets are not: these two types of posets thus cannot belong to the same isomorphism class.

Proposition 2.1. The coproduct Δ is an algebra homomorphism. The algebra V (F_{1}) together with this coproduct is then a bialgebra, not counital on the right, and denoted by B_{⋄,▽}.

The subalgebra D_{⋄} generated by the diamond posets is a subbialgebra of B_{⋄,▽} isomorphic to the incidence Hopf algebra of diamond posets. The subalgebra T_{▽} of B_{⋄,▽} generated by the triangle posets is a right comodule over D_{⋄}.

Proof. An interval I in a product of posets P_{1} × ⋯ × P_{k} can be seen as a product of intervals I_{1} × ⋯ × I_{k}, where each I_{k} is an interval in P_{k}.

Due to this property, we can rewrite the coproduct of a product of two posets P and Q in the form

Δ(P × Q) = ∑_{x∈P,y∈Q} D(x, y) ⊗ U(x, y)

= ∑_{x∈P} ∑_{y∈Q} (D(x) × D(y)) ⊗ (U(x) × U(y))

= ∑_{x∈P} D(x) ⊗ U(x) × ∑_{y∈Q} D(y) ⊗ U(y).

This coproduct is thus an algebra homomorphism. The algebra V (F_{1}) is then endowed with a coproduct which is an algebra homomorphism: it is a bialgebra. Let us remark that for a triangle poset P, the coproduct Δ(P) never contains the term P ⊗ 1: the bialgebra is therefore not counital on the right.

The subalgebra D_{⋄} generated by the diamond posets is also a subcoalgebra according to the first decomposition property. Indeed, every interval in a diamond poset is a product of diamond posets, therefore the coproduct of a diamond poset is a sum of tensor products of products of diamond posets. The subalgebra D_{⋄} is then a subbialgebra of B_{⋄,▽}. By definition, this subbialgebra is isomorphic as a bialgebra to the incidence Hopf algebra of diamond posets.

According to the second decomposition property, the coproduct of a triangle poset is a sum of tensor products. The terms on the left of this product are diamond posets and the terms on the right are triangle posets: the subalgebra T_{▽} of B_{⋄,▽} generated by the triangle posets is then a right comodule over D_{⋄}. The subalgebra T_{▽} is not unital. □

We next show that the computation of some characters on the incidence Hopf algebra H_{⋄,▽} can be reduced to some calculus in the bialgebra B_{⋄,▽}.

2.3. Characters on the incidence Hopf algebra of triangle and diamond posets. We define the linear map

(2.2)  λ : B_{⋄,▽} → H_{⋄,▽}

which sends an isomorphism class c_{d_{i}} of a diamond poset d_{i} in B_{⋄,▽} to the isomorphism class c_{d_{i}} of d_{i} in H_{⋄,▽} and which sends an isomorphism class c_{t_{j}} of a triangle poset t_{j} in B_{⋄,▽} to the isomorphism class ct̂_{j} of the augmented triangle poset t̂_{j} in H_{⋄,▽}. We stress the fact that this map is neither an algebra homomorphism nor a coalgebra homomorphism.

This linear map is well defined. Indeed, if two diamond posets are in the same isomorphism class in B_{⋄,▽}, then they are also in the same isomorphism class in H_{⋄,▽}. If two triangle posets are in the same isomorphism class in B_{⋄,▽}, then these posets augmented with a greatest element are also isomorphic, and thus in the same isomorphism class in H_{⋄,▽}.

We would like to compute some characters on the isomorphism classes of the diamond posets d_{i} of F_{0} and augmented triangle posets t̂_{j} coming from triangle posets t_{j} of F_{0} in H_{⋄,▽}. As F_{0} is a subfamily of F_{1}, to any element of F_{0} corresponds an isomorphism class in B_{⋄,▽} which is sent to the isomorphism class of the corresponding element in H_{⋄,▽}: the elements on which we want to compute characters belong to the image of λ.

We observe that the fibre of any isomorphism class in the image of λ contains at most one isomorphism class of triangle posets and at most one isomorphism class of diamond poset. Indeed, if two isomorphism classes of triangle posets, or two isomorphism classes of diamond posets, are sent by λ to the same isomorphism class, then these isomorphism classes are equal.

A character γ on H_{⋄,▽} is said to satisfy the HtoB-condition if there exists a rational number ω_{γ} and a map γ̃ from B_{⋄,▽} to ℚ which satisfy

(2.3)  γ(λ(c_{d_{i}})) = γ̃(c_{d_{i}}) and γ(λ(c_{t_{j}})) = ω_{γ}γ̃(c_{t_{j}}),

The number ω will be chosen as −1 in the example of hypertree posets developed in the following sections.

The convolution of two characters on H_{⋄,▽} can be computed by means of the following theorem.

Theorem 2.2. The convolution of the characters α and β on H_{⋄,▽} satisfying the HtoBcondition (2.3) is given by

(α ∗ β)(λ(c_{d_{i}})) = ∑ α̃(c_{d_{i}}^{(1)})β̃(c_{d_{i}}^{(2)}),

and

(α ∗ β)(λ(c_{t_{j}})) = ω_{β} ∑ α̃(c_{t_{j}}^{(1)})β̃(c_{t_{j}}^{(2)}) + ω_{α}α̃(c_{t_{j}}),

where Δ(c_{d_{i}}) = ∑ c_{d_{i}}^{(1)} ⊗ c_{d_{i}}^{(2)} and Δ(c_{t_{j}}) = ∑ c_{t_{j}}^{(1)} ⊗ c_{t_{j}}^{(2)} in B_{⋄,▽}.

Proof. The isomorphism class λ(c_{d_{i}}) is the isomorphism class of the diamond poset d_{i} in H_{⋄,▽} by definition of λ. Moreover, the coproduct of λ(c_{d_{i}}) in H_{⋄,▽} and of c_{d_{i}} in B_{⋄,▽} are the same by definition of the coproduct. As α and α̃ on the one hand, and β and β̃ on the other hand, are equal on λ(c_{d_{i}}) and c_{d_{i}}, respectively, the first equality follows.

To obtain the second equality, we observe that the isomorphism class λ(c_{t_{j}}) corresponds to the isomorphism class of the augmented triangle poset t̂_{j} by definition of λ. Hence the coproduct of λ(c_{t_{j}}) in H_{⋄,▽} has one more term than the coproduct of c_{t_{j}} in B_{⋄,▽}, due to the fact that the poset t̂_{j} has one more element than the poset t_{j}. This term is λ(c_{t_{j}}) ⊗ 1. All the other terms can be matched by associating λ(c_{t_{j}}) with the unique isomorphism class of triangle posets of its fibre c_{t_{j}}. Moreover, the posets on the left part of the coproduct of λ(c_{t_{j}}) are of diamond type, except for the term that does not belong to the coproduct of c_{t_{j}}, and α and α̃ coincide on diamond posets. Therefore we have

(α ∗ β)(λ(c_{t_{j}})) = ∑ α̃(c_{t_{j}}^{(1)})ω_{β}β̃(c_{t_{j}}^{(2)}) + ω_{α}α̃(c_{t_{j}}).

This yields the claimed result. □

3. Hypertree posets

A hypergraph is a pair (V, E), where the elements of V are called vertices and the elements of E, called edges, are sets of at least two vertices. We will only consider hypertrees on at least two vertices: each vertex thus belongs to at least one edge. The size of an edge e is the number of vertices in the edge e. The valency of a vertex v is the number of edges to which v belongs. A walk on a hypergraph H = (V, E) from a vertex s of H to a vertex f of H is an alternating sequence of vertices and edges in H, s = v_{0}, e_{0}, v_{1}, e_{1}, …, e_{n−1}, v_{n} = f, such that e_{i} is an edge containing the vertices v_{i} and v_{i+1}, for i ∈ ⟦0, n − 1⟧. A hypertree is a hypergraph such that, given any pair (s, f) of vertices, there exists exactly one walk from s to f without repeated edges. Given a hypertree T with vertex set V of cardinality n, we say that T is a hypertree on n vertices.

We may define the following order on hypertrees: a hypertree T is smaller than a hypertree T′ whenever the edges of T are unions of some edges of T′. The set of hypertrees on n vertices endowed with this partial order is a poset denoted by h_{n}. This poset has a least element ˆ0, given by the hypertree the only edge of which being the one which is formed by the complete vertex set V. The poset obtained by adding a greatest element ˆ1 is called the (n-)augmented hypertree poset and is denoted by ĥ_{n}.

We now want to characterize tuples α = (α_{1}, … α_{k}) and (π_{2}, …, π_{ℓ}) such that there exists a hypertree with α_{i} vertices of valency i and π_{j} edges of size j, for i ≥ 1 and j ≥ 2. For that purpose, we will consider hypertrees as ⟦1, n⟧-labelled bipartite trees as in [9]. A ⟦1, n⟧-labelled bipartite tree is a tree T together with a bijection from ⟦1, n⟧ to a subset of its vertex set such that the image of ⟦1, n⟧ includes all of the vertices of valency 1, and for every edge in T exactly one of its endpoints lies in the image of ⟦1, n⟧. The labelled vertices of a bipartite tree correspond to the vertices of the associated hypertree, and the other vertices correspond to the edges of the hypertree. An example of a hypertree and the associated labelled bipartite tree is presented in Figure 3.2. The number of labelled vertices of valency i is then denoted by α_{i} and the number of unlabelled vertices of valency j (or of edges of size j in the hypertree) by π_{j}.

ˆ1 1 2 3 1 2 3 1 2 3 1 2 3

Figure 3.1. The poset ĥ_{3}

4 1 2 3 5 6 7  \begin{matrix}• \\ • \\ • \\ 4 \\ 1 \\ 2 \\ 3 \\ 5 \\ 6 \\ 7 \end{matrix}

Figure 3.2. A hypertree and its associated labelled bipartite tree.

We obtain the following criterion for the existence of such an hypertree, which was first given in an equivalent formulation by Bacher [1]. Here, we provide a direct proof of his result.

Proposition 3.1. Given two tuples α = (α_{1}, …, α_{k}) and π = (π_{2}, …, π_{ℓ}), there exists a hypertree on n vertices with α_{i} vertices of valency i and π_{j} edges of size j if and only if

(3.1)  ∑_{i=1}^{k} α_{i} = n,

(3.2)  ∑_{j=2}^{ℓ}(j − 1)π_{j} = n − 1,

(3.3)  ∑_{i=1}^{k} iα_{i} = n + ∑_{j=2}^{ℓ} π_{j} − 1.

We postpone the proof of this proposition in order to illustrate it first by an example.

Example 3.2. For n = 4, the second equation of (3.1) implies that ∑_{j=2}^{ℓ} π_{j} ≤ 3, i.e., ∑_{i=1}^{k} iα_{i} ≤ 6. The possible α’s are:

• α = (4); in that case, we obtain the condition ∑_{j=2}^{ℓ} π_{j} = 1, so the only possible π is π = (0, 0, 1);

• α = (3, 1); in that case, we obtain the condition ∑_{j=2}^{ℓ} π_{j} = 2, so the only possible π is π = (1, 1);

• α = (2, 2); in that case, we obtain the condition ∑_{j=2}^{ℓ} π_{j} = 3, so the only possible π is π = (3); • α = (3, 0, 1); in that case, we obtain the condition ∑_{j=2}^{ℓ} π_{j} = 3, so the only

possible π is π = (3).

We now give a new direct proof of the criterion in Proposition 3.1.

Proof of Proposition 3.1. Suppose that there exists such a hypertree. Let T be such a hypertree. Every vertex in T has a fixed valency. Therefore, counting vertices, we obtain the first equation

∑_{i=1}^{k} α_{i} = n.

By construction of the labelled bipartite tree B associated with T, every unlabelled vertex is linked with a labelled vertex. This leads to the following equality by counting edges around labelled and unlabelled vertices of B:

(3.4)  ∑_{i=1}^{k} iα_{i} = ∑_{j=2}^{ℓ} jπ_{j}.

Moreover, with a bipartite tree we may associate a simplicial complex with faces of dimension at most 1. This simplicial complex is connected without cycles, therefore its Euler characteristic is equal to 1 and can be expressed as

(3.5)  χ = 1 = ∑_{j≥2} π_{j} − ∑_{j≥2} jπ_{j} + ∑_{i≥1} α_{i}.

These equations are equivalent to (3.1)–(3.3).

Let us now prove that this condition is also sufficient. We consider a set of α_{i} labelled vertices with i half-edges and π_{j} unlabelled vertices with j half-edges, with i ≥ 1 and j ≥ 2, such that (3.1)–(3.3) are satisfied. As this implies that (3.4) is satisfied, we can then choose a way to associate the vertices to obtain a ⟦1, n⟧-labelled bipartite graph T, i.e., a graph together with a chosen bijection from ⟦1, n⟧ to a subset of its vertex set such that the image of ⟦1, n⟧ includes all of the vertices of valency 1 and for every edge in T exactly one of its endpoints lies in the image of ⟦1, n⟧.

As our assumption also implies that (3.5) is satisfied, the Euler characteristic, i.e., the difference between the number of connected components and the number of cycles, is equal to 1. If the graph T is connected, then it has no cycles: it is a tree and we have constructed a ⟦1, n⟧-labelled bipartite tree. The associated hypertree has fixed set of valencies and fixed set of edge sizes.

If the graph T is not connected, then there is a cycle in one of the connected components. Therefore, there is an edge in this connected component that can be removed without increasing the number of connected components. This edge is between an unlabelled vertex u_{1} and a labelled vertex l_{1}. Let us cut an edge in one of the other connected components between two vertices u_{2} and l_{2}. We then obtain a graph with each element of the set {u_{1}, l_{1}, u_{2}, l_{2}} having an unlinked half-edge. Linking u_{2} with l_{1} and u_{1} with l_{2}, we obtain a ⟦1, n⟧-labelled graph satisfying the conditions with one less connected component. Indeed, we may have disconnected the connected component of u_{2} and l_{2} by deleting the edge but when linking the vertices we create a path from u_{2} to l_{2} by using the one existing between u_{1} and l_{1}. As this operation decreases the number of connected components, we can repeat it until we find a hypertree matching the required conditions. □

From the second equation of the proposition, we may deduce the following expression for π_{2} in terms of π_{j} for j ≥ 3:

π_{2} = n − 1 − ∑_{j≥3}(j − 1)π_{j}.

4. Computation of the number of hypertrees with fixed parameters

In this section, we compute the number of hypertrees with a given edge size and valency set. After having written the proof, the author was informed that this result was already obtained by Bacher [1] and by Bousquet-Mélou and Chapuy [4] in terms of bicoloured trees (see also [16]). Although the proof of this section is really close to the reasoning of Bacher, we still present it here for self-containment. The Prüfer code presented here is different from the one presented by Bacher, although it was already introduced by Selivanov in [14] according to Bacher [2]. We thank the different mathematicians who have reported to us the already existing literature and helped us improve the accuracy of the references.

We want to compute the number of hypertrees with α_{i} vertices of valency i and π_{j} edges of size j. We do this using bijections. Given a tuple π, we call a partition a π-hanging partition if it has one block consisting of a vertex, π_{j} other blocks consisting of j − 1 vertices, and in each of these π_{j} other blocks a “fastener”, which by definition is a mark in the block indicating that this block will be linked to the vertex of another block, for j ≥ 2.

Example 4.1. A π-hanging partition P, for π = (1, 2):

2  15  43  6  .

For convenience, we write X for the fastener and represent the π-hanging partition as

P = (2) (X|1 5) (X|4 3) (X|6).

Then the assembly of elements of a π-hanging partition of a hypertree can be seen as an assembly of coat-hangers and coat racks. In Figure 4.1, we represent the assembly of the π-hanging partition

(2) (X|1 5) (X|4 3) (X|6) (X|7 8 9)

and the corresponding hypertree.

Let us fix π and α and denote the set of π-hanging partitions by Π_{HP}, and the set of rooted hypertrees with α_{i} vertices of valency i and π_{j} edges of size j by H_{α,π}^{p}. We define a map φ : H_{α,π}^{p} → Π_{HP} in the following way. Given an edge e, we map it to the set of all vertices of e, except the closest to the root, with a fastener added to this set. If we add the singleton made of the root to this set of hanging sets, we obtain a π-hanging partition. Indeed, all sets but one of cardinality one have a fastener, and the

6 1 5 2 4 3 7 8 9  2 6 1 5 4 3 7 8 9

Figure 4.1. A hypertree and the corresponding assembly of a π-hanging partition (2) (X|1 5) (X|4 3) (X|6) (X|7 8 9).

size of each hanging set is one less than the size of the associated edge. An example of the image of a hypertrees under the map φ is presented in Example 4.3.

Given P in Π_{HP}, we denote the fibre φ^{−1}(P) by F_{P}. The cardinality of H_{α,π}^{p} is the sum of the cardinalities of the disjoint fibres. As we will see in the proof, the cardinality of a fibre is independent of the considered π-hanging partitions. We denote this cardinality by d_{α}^{n}. We will say that we can construct a hypertree H from a π-hanging partition P if φ(H) = P.

Let us now link hypertrees to hanging partitions.

Lemma 4.2. The number of rooted hypertrees with α_{i} vertices of valency i and π_{j} edges of size j is given by

(4.1)  |H_{α,π}^{p}| = \frac{1}{n} × \frac{n!}{∏_{j≥2}(j − 1)!^{π_{j}}π_{j}!} × d_{α}^{n}.

Proof. We want to compute the cardinality of H_{α,π}^{p}. Let us consider the action of the symmetric group 𝔖_{n} on H_{α,π}^{p} by permutation of vertices. By definition of the map φ, which is 𝔖_{n}-equivariant, this action induces an action of the symmetric group on the set Π_{HP}. The action of the symmetric group 𝔖_{n} on the set of all hanging partitions of type π is transitive, as it does not change the sizes of the blocks of the partitions. Let (O_{j})_{1≤j≤p} be the orbits for the action of 𝔖_{n} on the set H_{α,π}^{p}. The fibre F_{P} has a component f_{j}^{P} in every orbit O_{j}. We summarize all these notations in the diagram of Figure 4.2.

φ Π_{HP} H_{α,π}^{p} O_{1} O_{2} O_{3} P H_{3} H_{2} H_{1} f_{3}^{P} f_{2}^{P} f_{1}^{P} F_{P}

Figure 4.2. The map φ.

We consider a hypertree H_{j} in each f_{j}^{P}. The orbit-stabilizer theorem applied to O_{j} yields

n! = |O_{j}| × | Aut_{H_{j}} |,

where | Aut_{H_{j}} | is the cardinality of the automorphism group of the rooted hypertree H_{j}. As H_{α,π}^{p} = ⨆_{j=1}^{p} O_{j}, we obtain the relation

(4.2)  |H_{α,π}^{p}| = n! × ∑_{j=1}^{p} \frac{1}{| Aut_{H_{j}} |}.

Let us consider the group G_{P} of permutations of ⟦1, n⟧ fixing P. There are exactly ∏_{j≥2}(j − 1)!^{π_{j}}π_{j}! such permutations. The group G_{P} acts on the fibre F_{P} transitively on each f_{j}^{P}. Indeed, if σ ∈ 𝔖_{n} sends a hypertree H of f_{k}^{P} to a hypertree H′ of f_{k}^{P}, then σ stabilizes P since φ(H) = φ(σ(H)) = P. Subsequently, the orbit-stabilizer theorem applied to f_{j}^{P} gives

(4.3)  |f_{j}^{P} | × | Stab_{G_{P}} H_{j}| = |G_{P} | = ∏_{j≥2}(j − 1)!^{π_{j}}π_{j}!,

where Stab_{G_{P}} H_{j} = {σ ∈ G_{P} |σ(H_{j}) = H_{j}}.

We show that Stab_{G_{P}} H_{j} = Aut_{H_{j}}. As G_{P} ⊆ 𝔖_{n}, it is easily shown that Stab_{G_{P}} H_{j} ⊆ Aut_{H_{j}}. For a permutation σ in Aut_{H_{j}}, we have φ(σ(H_{j})) = φ(H_{j}) = P and φ(σ(H_{j})) = σ(P). In other words, σ stabilizes P. Therefore, we obtain the relation Stab_{G_{P}} H_{j} = Aut_{H_{j}}. Combined with (4.2) and (4.3), we get the result, since d_{α}^{n} = ∑_{j=1}^{p} |f_{j}^{P} |. □

Example 4.3. We consider the π-hanging partition P

P = (2) (X|1 5) (X|4 3) (X|6),

with π = (1, 2), where X represents the fastener of the block. For α = (4, 2), we may construct the following rooted hypertrees (and many others):

T =  6 1 5 2 4 3  and T′ =  6 5 1 2 4 3  .

Let us consider the group G_{P} of permutations of ⟦1, n⟧ fixing P, introduced in the proof of Lemma 4.2. We describe an example of the action of the group G_{P} on the fibre of P. Considering T and T′ in the fibre of P (φ(T) = φ(T′) = P), the permutation (3 4) fixes T and T′, but the permutation (1 5) sends T to T′. Hence T and T′ are in the same orbit.

The following hypertree T′′ is not in the orbit of T and T′:

6 4 3 2 1 5 .

We now want to compute the number d_{α}^{n} of constructions of a hypertree of valency set α from a π-hanging partition P_{π}. This is also the cardinality of the fibre φ^{−1}(P_{π}). This construction is given by a bijection introduced by Bacher in [1], which we recall for self-containment of this article.

Lemma 4.4. Given a pair (α, π) in P_{n} and a π-hanging partition P_{π}, there is a bijection between the set of constructions of a rooted hypertree of valency set α from P_{π} and the set of words on ⟦1, n⟧ of length ∑_{j≥2} π_{j} − 1 with ∑_{i≥2} α_{i} different letters, where α_{i} letters appear i − 1 times for i ≥ 2.

Proof. We prove this lemma using a Prüfer code type proof. We want to count the number of different rooted hypertrees which can be constructed from a π-hanging partition P_{π} and which have α_{i} vertices of valency i for i ≥ 1. Given such a rooted hypertree, we recursively construct a variant of Prüfer code.

If the hypertree has only one edge of size n, then we can separate the root from the edge and put a fastener instead: we obtain two blocks, the one of the root and another hanging one of size n − 1. Given a π-hanging partition, we assemble the two blocks of the partition into one edge and it gives back the hypertree. The associated word is the empty word, which is of length 0.

If the rooted hypertree H has more than one edge, we consider the set of leaves of the hypertree, i.e., the set of edges whose vertices but the closest from the root, called the petiole, are of valency 1. We order the set of leaves according to their minimal unshared element. The petiole of the minimal leaf will be the first letter w_{1} of the word w associated with H. We suppose that this vertex has a valency v. We denote the size of the minimal leaf by s_{m}. Then, by deleting the minimal leaf and its s_{m} − 1 vertices different from the petiole, we obtain a rooted hypertree H′ on n − s_{m} + 1 vertices in which the valency of the petiole w_{1} has decreased by one, the number of vertices of valency 1 has decreased by s_{m} − 1, and all other vertices have the same valency. As vertices of valency 1 do not appear in the word associated with the hypertree, the deletion of these vertices only decreases the number of occurrences of w_{1} in the word associated with H′ by one compared with the word associated with H. If w is the word associated with H and w′ the one associated with H′, then w = w_{1}w′.

Moreover, the hanging partition associated with H′ can be obtained from P_{π} by deleting the hanging block of P_{π} containing the vertices of valency 1 of the minimal leaf. We then construct the word w′ associated with H′: it is a word of length ∑_{j≥2} π_{j}−2 letters, with ∑_{i≥2} α_{i} different letters, where α_{i} letters appear i−1 times for i ≠ v, v −1, α_{v} − 1 letters appear v − 1 times, and α_{v−1} + 1 letters appear v − 2 times. We note that the vertex w_{1} is of valency v − 1 in H′, so it appears v − 2 times in w′. Hence, the letter w_{1} appears v − 1 times in the word w = w_{1}w′, and the word w = w_{1}w′ satisfies the required conditions.

If we have a π-hanging partition and a word w satisfying the required conditions, we can build the associated rooted hypertree by ordering the blocks with a fastener whose elements are not letters of w according to their minimal element. Then we attach the least element of these blocks to the last letter of the word, which is an element of another block and delete this last letter. We repeat these operations until the word is empty. We finally obtain a rooted hypertree, and this operation is the inverse of the construction above. Hence, this gives a bijection between the constructions of rooted hypertrees from hanging partitions and the set of words of the lemma. □

Example 4.5. Considering the hanging partition P and the hypertrees T, T′, and T′′ of Example 4.3, the words associated with the construction of T, T′ and T′′ from P are 1 6, 5 6, and 2 6, respectively.

The hypertree whose construction from P is associated with the word 6 2 is

6 1 5 2 4 3 .

There are 36 words associated with the π-hanging partition: 6 corresponding to hypertrees with a vertex of valency 3 and the others of valency 1, and 30 corresponding to hypertrees with two vertices of valency 2 and the others of valency 1.

Lemma 4.6. For a tuple (α_{1}, α_{2}, …), put k = ∑_{i≥1}(i − 1)α_{i} and n = ∑_{i≥1} α_{i}. Then the number of length k words on the alphabet [1, n], with α_{i} letters repeated i − 1 times, is

(4.4)  d_{α}^{n} = \frac{k! × n!}{∏_{i≥1}(i − 1)!^{α_{i}}α_{i}!}.

Proof. This lemma is a classical result. □

Using this lemma, we obtain the following proposition.

Proposition 4.7. If the tuples α = (α_{1}, …) and π = (π_{2}, …) satisfy (3.1)–(3.3), the number of hypertrees with α_{i} vertices of valency i and π_{j} edges of size j, for i ≥ 1 and j ≥ 2, is given by

(4.5)  c_{α,π}^{n} = \frac{1}{n} × \frac{n!}{∏_{j≥2}(j − 1)!^{π_{j}}π_{j}!} × \frac{(K − 1)! × n!}{∏_{i≥1}(i − 1)!^{α_{i}}α_{i}!},

with K = ∑_{j≥2} π_{j} = ∑_{i≥1}(i − 1)α_{i} + 1 and n = ∑_{i≥1} α_{i}.

Proof. This proposition follows from Lemmas 4.2, 4.4, and 4.6. □

5. Coproduct in the bialgebra

Some intervals in the hypertree posets will be described in terms of another type of posets: partition posets. A partition poset is a poset on the set of all partitions of a set V. A partition a_{1} is smaller than a partition a_{2} if each block of a_{1} is the union of some blocks of a_{2}. The partition poset on n vertices p_{n} is based on the set of partitions of a set of cardinality n. The poset p_{4} is presented in Figure 5.1.

We need the following result of McCammond and Meier on intervals in the hypertree poset.

Lemma 5.1 ([8, Lemma 2.5]). Let T be a hypertree on n vertices, for n ≥ 2. Then the following hold:

(a) The interval [ˆ0, T] is a direct product of partition posets, with one factor p_{j} for each vertex in T with valency j.

(b) The half-open interval [T, ˆ1) is a direct product of hypertree posets, with one factor h_{j} for each edge in T with size j.

Let us consider the incidence Hopf algebra HĤT = (HĤT, ×, ϵ, η, Δ, S) obtained from the construction of Section 2.1 by taking the set of partition posets (p_{i})_{i≥1} for the set of diamond posets and the set of hypertree posets (h_{n})_{n≥3} for the set of triangle

{1}{2}{3}{4} {1, 2}{3}{4} {1, 3}{2}{4} {1}{2, 3}{4} {1, 4}{2}{3} {1}{2, 4}{3} {1}{2}{3, 4} {1, 2, 3}{4} {1, 2, 4}{3} {1, 2}{3, 4} {1, 3}{2, 4} {1, 3, 4}{2} {1, 4}{2, 3} {1}{2, 3, 4} {1, 2, 3, 4}

Figure 5.1. The poset p_{4}

posets. Indeed, the partition poset p_{1} on one element and the hypertree poset h_{2} on two elements are both isomorphic to the trivial poset, partition posets are intervals, and hypertree posets have a least element but no greatest one. Moreover, it is a classical result that every interval in a partition poset is isomorphic to a product of partition posets (see [16]). This fact combined with Lemma 5.1 implies that this family satisfies the decomposition property and therefore all the requirements of Section 2.1. We denote the augmented hypertree poset by ĥ_{n}.

We consider H∗ ; ĤT, the group of characters χ : HĤT → ℚ. We aim at calculating the Möbius numbers of the augmented hypertree posets using the classical techniques of characters. A good reference for such a computation of characters for the partition posets, and Möbius numbers, is the article [15] of Speicher. To compute the character which associates with a poset of HĤT its Möbius number, we use Theorem 2.2.

We write B_{HT} for the bialgebra defined in Section 2.2, where partition posets play the role of diamond posets and hypertree posets play the role of triangle posets. Due to Lemma 5.1(b), we see that this bialgebra is not only generated as an algebra by isomorphism classes of partition posets and isomorphism classes of intervals [τ, ˆ1), where τ is a hypertree, but also by a smaller set: the isomorphism classes of partition posets p_{n} and the isomorphism classes of hypertree posets h_{n}. Moreover, partition posets and hypertree posets are both graded, therefore two partition posets or hypertree posets on n and m elements, respectively, are isomorphic if and only if m and n are equal. As every p_{i} and h_{j} are pairwise not in the same isomorphism classes, due to gradings, and as we focus on these classes, we will use the same notation for the isomorphism classes of posets and posets themselves.

Let us remark that the subalgebra of B_{HT} generated by partition posets, as described in Proposition 2.1, is the Faà di Bruno Hopf algebra. This is also a subalgebra of HĤT. Moreover, the subalgebra of B_{HT} generated by hypertree posets is a right comodule over the Faà di Bruno Hopf algebra.

Example 5.2. We consider the poset ĥ_{3} shown in Figure 3.1. The computation of the coproducts gives

Δ(ĥ_{3}) = 1 ⊗ ĥ_{3} + 3 p_{2} ⊗ ĥ_{2} + ĥ_{3} ⊗ 1, in HĤT,
Δ(h_{3}) = 1 ⊗ h_{3} + 3 p_{2} ⊗ h_{2}, in B_{HT} .

Hence, the convolution of characters α and β on HĤT can be computed using the bialgebra B_{HT}.

Proposition 5.3. The convolution of characters α and β on HĤT can be computed using maps α̃ and β̃ from B_{HT} to ℚ, provided α and β satisfy the HtoB-condition (2.3). This computation is given by

(α ∗ β)(p_{i}) = ∑ α̃(p_{i}^{(1)})β̃(p_{i}^{(2)}),

and

(α ∗ β)(ĥ_{j}) = ω_{β} ∑ α̃(h_{j}^{(1)})β̃(h_{j}^{(2)}) + ω_{α}α̃(h_{j}),

where Δ(p_{i}) = ∑ p_{i}^{(1)} ⊗ p_{i}^{(2)} and Δ(h_{j}) = ∑ h_{j}^{(1)} ⊗ h_{j}^{(2)} in B_{HT}.

Proof. This is a corollary of Theorem 2.2 for p_{i} and h_{j}. □

We now compute the coproduct Δ in the algebra B_{HT}. We denote the neutral element of B_{HT} for the product, i.e., the trivial poset, by 1.

The coproduct of isomorphism classes of partition posets p_{n} has already been computed. It can be found for instance in the article [13] of Schmitt.

Proposition 5.4 ([13, Example 14.1]). The coproduct on the isomorphism classes of partition posets is given by

Δ (\frac{p_{n}}{n!} ) = ∑_{k=1}^{n} ∑_{\begin{matrix}(j_{1},...,j_{n})∈ℕ \\ ∑_{i=1}^{n} j_{i}=k, ∑_{i=1}^{n} ij_{i}=n \end{matrix}} \binom{k}{j_{1}, …, j_{n}} ∏_{i=1}^{n} (\frac{p_{i}}{i!} )^{j_{i}} ⊗ \frac{p_{k}}{k!} ,

where p_{1} is the trivial poset.

We now compute the coproduct for h_{n}. According to the structure of the hypertree posets and Lemma 5.1, the left part of the coproduct of isomorphism classes of the hypertree poset h_{n} is a product of isomorphism classes of partition posets, and the right part is a product of isomorphism classes of hypertree posets h_{k}. The coefficient of a term p_{α} ⊗ h_{π} is the number of hypertrees with α_{i} vertices of valency i and π_{j} edges of size j, as computed in Proposition 4.7, for tuples α and π satisfying (3.1)–(3.3).

Theorem 5.5. If the set P(n) is the set of tuples α = (α_{1}, …, α_{k}) and π = (π_{2}, …, π_{ℓ}) satisfying (3.1)–(3.3), the coproduct of h_{n} in B_{HT} is given by

Δ(h_{n}) = \frac{1}{n} × ∑_{(α,π)∈P(n)} \frac{n!}{∏_{j≥2}(j − 1)!^{π_{j}}π_{j}!} × \frac{(K − 1)! × n!}{∏_{i≥1}(i − 1)!^{α_{i}}α_{i}!} ∏_{i=2}^{k} p_{i}^{α_{i}} ⊗ ∏_{j=2}^{ℓ} h_{j}^{π_{j}},

with K = ∑_{j≥2} π_{j} = ∑_{i≥1}(i − 1)α_{i} + 1 and n = ∑_{i≥1} α_{i}.

Example 5.6. We are now able to compute the coproduct of some h_{n}. Using the values of (α, π) on which c_{α,π}^{n} does not vanish, computed in Example 3.2, we obtain for h_{4} that

Δh_{4} = \frac{1}{4} × \frac{4!}{3!} × \frac{0!4!}{4!} × p_{1}^{4} ⊗ h_{4} + \frac{1}{4} × \frac{4!}{2!} × \frac{1!4!}{3!} × p_{1}^{3}p_{2} ⊗ h_{2}h_{3}

+ \frac{1}{4} × \frac{4!}{3!} × \frac{2!4!}{2!2!} × p_{1}^{2}p_{2}^{2} ⊗ h_{2}^{3} + \frac{1}{4} × \frac{4!}{3!} × \frac{2!4!}{3!2!} × p_{1}^{3}p_{3} ⊗ h_{2}^{3},

Δh_{4} = 1 ⊗ h_{4} + 12 p_{2} ⊗ h_{2}h_{3} + 12 p_{2}^{2} ⊗ h_{2}^{3} + 4 p_{3} ⊗ h_{2}^{3}.

When summing the coefficients in this coproduct, we obtain the total number of hypertrees on 4 vertices, which is 29, as expected.

6. Computation of the Möbius number of augmented hypertree posets

On an incidence Hopf algebra H with algebraic generators g_{n} (which are posets), we define the characters ζ and μ for n ≥ 1 by

ζ : g_{n} ↦ 1

and

μ : g_{n} ↦ μ(g_{n}),

where μ(g_{n}) is the Möbius number of the poset g_{n}.

These characters are inverses of each other. This means that, if ϵ is the counit of H and ∗ is the convolution on characters, we have

ζ ∗ μ = μ ∗ ζ = ϵ.

Indeed, these equations come from the definitions of the convolution and the Möbius function:

(μ ∗ ζ)([h, h]) = μ([h, h]) = 1

and

(μ ∗ ζ)([h, h′]) = ∑_{h≤x≤h′} μ([h, x]) × 1 = μ(h, h′) + ∑_{h≤x<h′} μ(h, x),

for intervals [h, h′] with h < h′ in H.

According to Definition 1.1 of the Möbius function, μ ∗ ζ and ζ ∗ μ vanish on any non-trivial interval.

We want to compute the Möbius number of augmented hypertree posets. We use Proposition 5.3. To prove that the characters satisfy the assumptions of the proposition, we need the notion of a sum function. If P is a finite poset with a unique least element, then we define the sum function by s(P) = ∑_{x∈P} μ(ˆ0, x).

If P̂ is the poset obtained from P by the addition of a greatest element ˆ1, then μ(P̂) = −s(P).

Lemma 6.1 ([8, Lemma 4.4]). If P_{i}, i ∈ [k], is a list of finite posets, each with a unique minimal element, and Q = ∏_{i=1}^{k} P_{i}, then s(Q) = ∏_{i=1}^{k} s(P_{i}).

We define the following maps from B_{HT} to ℚ, for a poset p of B_{HT} with both a least and a greatest element and a poset h with a least but no greatest element:

ζ̃(p) = ζ(p) = 1, ζ̃(h) = ζ(h) = 1,

and

μ̃(p) = μ(p), μ̃(h) = s(h).

These maps satisfy the following property due to their definitions and Lemma 6.1, for i ≥ 2 and j ≥ 3:

ζ̃(∏_{i=1}^{k} p_{i}) = ∏_{i=1}^{k} ζ̃(p_{i}), ζ̃(∏_{j=1}^{ℓ} h_{j}) = ∏_{j=1}^{ℓ} ζ̃(h_{j}),

and

μ̃(∏_{i=1}^{k} p_{i}) = ∏_{i=1}^{k} μ̃(p_{i}), μ̃(∏_{j=1}^{ℓ} h_{j}) = ∏_{j=1}^{ℓ} μ̃(h_{j}).

As these maps satisfy the conditions of Proposition 5.3, we apply it in the following subsections. Since partition and hypertree posets are not mixed in the coproduct of a hypertree poset, the computation of the convolution of μ and ζ will be given by a computation using only the values of ζ̃ and μ̃ on partition and hypertree posets. The first part of this section will be devoted to the equation ζ ∗ μ = ϵ, and the second part will be devoted to the equation μ ∗ ζ = ϵ.

6.1. Right-sided computation. In this subsection, we give a simplified proof of the result of McCammond and Meier on the computation of the Möbius number of the augmented hypertree poset. The proof of McCammond and Meier presented in [8] used generating function calculus. The introduction of incidence Hopf algebras enables us to give a shorter proof, only using the hypothesis of Theorem 2.2.

Applying the Möbius function on the right side of the coproduct, we obtain

(ζ ∗ μ)(ĥ_{n}) = 0,

for n ≥ 2. Hence, applying the computation of the coproduct of Theorem 5.5 and Proposition 5.3, for n ≥ 2 we obtain the equality

0 = − ∑ μ̃(h_{n}^{(2)}) + 1,

where Δ(h_{n}) = ∑ h_{n}^{(1)} ⊗h_{n}^{(2)}. Using Lemma 5.1, the definition of the coproduct on B_{HT} computed in Theorem 5.5, and the multiplicativity of μ̃, we thus obtain

(6.1)  0 = − ∑_{h∈h_{n}} ∏_{i∈ES(h)} μ̃(ĥ_{i}) + 1,

where ES(h) is the multiset of the edge sizes of h.

The first terms are given by

μ(ĥ_{2}) = −1,
μ(ĥ_{3}) = 3 × (−μ(ĥ_{2}))^{2} − 1 = 2,

and

μ(ĥ_{4}) = 13 × (−μ(ĥ_{3})) + 16 × (−μ(ĥ_{2}))^{3} + 1 = −26 + 16 + 1 = −9.

To obtain a closed formula, we consider the exponential generating function of hypertrees with a weight μ̃(ĥ_{i}) = −μ(ĥ_{i}) for each edge of size i,

T (x) = x + ∑_{n≥2} ∑_{h∈h_{n}} ∏_{i∈ES(h)} (−μ(ĥ_{i})) \frac{x^{n}}{n!} ,

where, again, ES(h) is the multiset of edge sizes of the hypertree h. Using (6.1), we obtain

T (x) = x + ∑_{n≥2} \frac{x^{n}}{n!} = e^{x} − 1.

Moreover, it has been proven by Kalikow [7] that the derivative of T satisfies the following functional equation.

Theorem 6.2 ([7]). The generating function T (x) satisfies the equation

(6.2)  xT′(x) = x × exp(y(x)) where y(x) = ∑_{j≥1} −μ(ĥ_{j+1})\frac{x^{j}T′(x)^{j}}{j!} .

Hence, we obtain

x = ∑_{j≥1} −μ(ĥ_{j+1})\frac{x^{j}e^{jx}}{j!} .

At this point, we recall that the compositional inverse of xe^{x} is the Lambert W function, given by

(6.3)  W (x) = ∑_{n≥1}(−n)^{n−1} \frac{x^{n}}{n!} .

This establishes the following theorem by McCammond and Meier.

Theorem 6.3 ([8, Theorem 5.1]). The Möbius number of the augmented hypertree poset on n vertices is given by

μ(ĥ_{n}) = (−1)^{n−1}(n − 1)^{n−2}.

As the homology of the augmented hypertree poset is concentrated in top degree, this Möbius number is also the dimension of the only homology group of the hypertree poset. The action of the symmetric group on this homology group has been computed by the author in [11].

Remark 6.4. To apply this method to pointed hypertree posets and to other posets satisfying the conditions of Theorem 2.2, it would be sufficient to have a theorem analogous to Theorem 6.2.

Moreover, using the expression for the coproduct computed in Section 5 and the Möbius numbers of the hypertree posets, we obtain the following proposition.

Proposition 6.5. We have

1 = ∑_{K=1}^{n−1} ∑_{\begin{matrix}(π_{2},...) \\ ∑_{j≥2} π_{j}=K \end{matrix}}(−1)^{K+n−1}(n − 1)!n^{K−1} ∏_{j≥2} \frac{1}{π_{j}!} (\frac{(j − 1)^{j−2}}{(j − 1)!} )^{π_{j}} ,

with K = ∑_{j≥2} π_{j} and n − 1 = ∑_{j≥2}(j − 1)π_{j}.

Proof. We use (6.1) together with the expression for the coproduct recalled in Section 5 and the expression for Möbius numbers of hypertree posets. As the left part of the coproduct does not interfere here, we can sum over the possible tuples α. This leads to a sum of multinomial coefficients which can be easily computed. □

6.2. Left-sided computation. Applying the Möbius function on the left side of the coproduct, we obtain

(μ ∗ ζ)(ĥ_{n}) = 0,

for n ≥ 2. By Proposition 5.3, for n ≥ 2 this can be rewritten as

0 = ∑ μ̃(h_{n}^{(1)})ζ̃(h_{n}^{(2)}) − μ̃(h_{n}).

The formula for the coproduct is

μ(ĥ_{n}) = − ∑_{(α,π)∈P_{n}} c_{α,π}^{n} ∏(−1)^{(i−1)α_{i}}(i − 1)!^{α_{i}}

Using Theorems 6.3 and 5.5, we obtain the following proposition.

Proposition 6.6. We have

(6.4)  (n − 1)^{n−2} = ∑_{(α,π)∈P(n)} \frac{(−1)^{iα_{i}−1}}{n} × \frac{n!}{∏_{j≥2}(j − 1)!^{π_{j}}π_{j}!} × \frac{k! × n!}{∏_{i≥1} α_{i}!},

where P(n) is the set of pairs of tuples (α, π) with α = (α_{1}, …, α_{k}) and π = (π_{2}, …, π_{ℓ}) satisfying (3.1)–(3.3).

This equation is quite surprising as it links the number of rooted trees on n vertices with an alternating sum of quotient of factorials.

Proof of Proposition 6.6. This equation comes from the computation of the coproduct, combined with the Möbius numbers of the augmented hypertree posets and of the partition posets. Indeed, the Möbius number of the partition poset on n elements is given by (−1)^{n−1}(n − 1)!. □

Example 6.7. The first terms are

μ(ĥ_{4}) = −1 + 12 − 12 − 8 = −9

and

μ(ĥ_{5}) = −1 + 20 + 12 − 120 − 60 + 60 + 120 + 30 = 64.

References

[1] R. Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees,

   arχiv:1102.2708, 2011.

[2] R. Bacher, Prüfer codes for acyclic hypertrees, Australasian Journal of Combinatorics, vol. 60, 109–127, 2014.

[3] C. Berge, Hypergraphs. North-Holland Mathematical Library, vol. 45, 1989.

[4] M. Bousquet-Mélou and G. Chapuy, The vertical profile of embedded trees. Electronic Journal of Combinatorics, vol. 19, no. 3, Paper 46, 61 pp., 2012.

[5] F. Chapoton, Hyperarbres, arbres enracinés et partitions pointées, Homology, Homotopy and Applications, vol. 9, no. 1, 193–212, 2007.

[6] C. Jensen, J. McCammond and J. Meier, The Euler characteristic of the Whitehead automorphism group of a free product, Trans. Amer. Math. Soc., vol. 359, no. 6, 2577–2595, 2007.

[7] L. H. Kalikow, Enumeration of parking functions, allowable permutation pairs, and labeled trees, Ph.D. thesis, Brandeis University, 1999.

[8] J. McCammond and J. Meier, The hypertree poset and the l^{2}-Betti numbers of the motion group of the trivial link, Mathematische Annalen, vol. 328, no. 4, 633–652, 2004.

[9] D. McCullough and A. Miller, Symmetric automorphisms of free products, Memoirs of the American Mathematical Society, vol. 122, no. 582, viii+97 pp., 1996.

[10] B. Delcroix-Oger Hypertrees and semi-pointed partitions: algebraic, combinatorial and topological aspects (french), Ph.D. thesis, Université Claude Bernard Lyon 1, 2014.

[11] B. Oger, Action of the symmetric groups on the homology of the hypertree posets, Journal of Algebraic Combinatorics, vol. 38, no. 4, 915–945, 2013.

[12] W. R. Schmitt, Antipodes and incidence coalgebras, Journal of Combinatorial Theory. Series A, vol. 46, no. 2, 264–290, 1987.

[13] W. R. Schmitt, Incidence Hopf algebras. Journal of Pure and Applied Algebra, vol. 96, no. 3, 299–330, 1994.

[14] B. I. Selivanov, Enumeration of homogeneous hypergraphs with a simple cycle structure, (Russian) Kombinatornyĭ Analiz Vyp., vol. 2, 60–67, 1972.

[15] R. Speicher, Free probability theory and non-crossing partitions, Séminaire Lotharingien de Combinatoire, vol. 39, Art. B39c, 38 pp., 1997.

[16] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, Cambridge, 2001.

Institut Camille Jordan, UMR 5208, Université Claude Bernard Lyon 1, Bât. Jean Braconnier nb 101, 43 Bd du 11 novembre 1918, 69622 Villeurbanne Cedex, France

  E-mail address: oger@math.univ-lyon1.fr