Member, IEEE Samir Medjiah
email: medjiah@ieee.org

Member, IEEE Tarik Taleb
email: talebtarik@ieee.org

Member, IEEE Toufik Ahmed

Sailing over Data Mules in Delay-Tolerant Networks

Keywords: DTN, geographic routing, predictive routing, trajectory-assisted routing, mobile networks, time series analysis, ARMA process. I

In this paper, we address the problem of efficient routing in delay tolerant networks. We propose a new routing protocol dubbed as ORION. In ORION, only a single copy of a data packet is kept in the network and transmitted, contact by contact, towards the destination. The aim of the ORION routing protocol is twofold: on one hand, it enhances the delivery ratio in networks where an end-to-end path does not necessarily exist, and on the other hand, it minimizes the routing delay and the network overhead to achieve better performances. With ORION, nodes are aware of their neighborhood by the mean of actual and statistical estimation of new contacts. ORION makes use of autoregressive moving average (ARMA) stochastic processes for best contact prediction and geographical coordinates for optimal greedy data packet forwarding. Simulation results have demonstrated that ORION outperforms other existing DTN routing protocols such as PRoPHET in terms of end-to-end delay, packet delivery ratio, hop count, first packet arrival and queues occupancy.

the existing one is down. Recently, revolution movements have gained some countries in North Africa. To counteract these protestation movements, government actors have shut down network infrastructures and disconnected the country from the internet in order to prevent people from accessing social networks. Many alternatives solutions have risen in the web. These propositions (such as the OpenMesh Project [START_REF]The openmesh project[END_REF]) all agree to provide mechanisms to establish networks in ad-hoc fashion and to disseminate easily important information.

The proper functioning of such applications relies essentially on the efficiency of the routing task. However many challenges affect the routing in DTNs such as the changing network topology due to intermittent connectivity which is inherent to mobile networks as well as to static networks (in the case of low duty cycle of the nodes), and it results in low delivery ratio and high end-to-end delay. The problem of intermittent connectivity can be mitigated if the exact schedule or the dynamics of the network is known in advance. However, this is not often the case in DTNs as building this knowledge is an important issue. Thus, the efficiency of a DTN routing protocol relies essentially on the amount of network knowledge or "oracles" (information about contacts, queues or even data traffic) available to perform routing decisions.

Several routing protocols have been proposed for DTNs. These protocols differ by the amount of implemented oracles. Depending on the application, some oracles may not be used. For example, in a city bus network, it may not be possible to embed the entire schedule of contacts between buses in each node due to various reasons: [START_REF] Kevin | A delay-tolerant network architecture for challenged Internets[END_REF] the memory space needed to store such information may be of huge size for a communicating node, [START_REF] Cerf | Delay-tolerant networking architecture[END_REF] the "frozen" schedule may not reflect the actual networks dynamics since the schedule of a bus is not "certain" as it may be shifted during the day, [START_REF]The openmesh project[END_REF] the exploitation of such information (for example, computing the best end-to-end route) can be highly computational costly. Then, the challenge in designing an efficient routing protocol for such networks is to make the communicating nodes smarter by using little information about the network and in a reliable distributed fashion.

In this paper, we propose ORION, a routing protocol for mobile DTNs that capitalizes on the localization information of the nodes (geo-coordinates) and the nature of contacts between this type of nodes (buses, cars, taxis, trams) in an urban area. In our earlier work [START_REF] Medjiah | Orion routing protocol for delay tolerant networks[END_REF], we presented initial results of inter-nodes contact behavior analysis and modeling. In this paper, we provide more details about a potential target application that can benefit from our routing protocol. We also provide details about the contact model derivation steps.

Moreover, extensive simulations have been conducted and new metrics have been computed in order to efficiently prove the performances of the proposed routing protocol.

The contribution presented in this paper is twofold. First, we have investigated deeply the inter-nodes encounter behavior. Second, based on this behavior analysis, we proposed ORION, a routing protocol that relies on predicting future contacts between nodes and greedy geographic forwarding of data packets. Thus, with ORION protocol, a communicating node will incrementally build knowledge about its network regarding the inter-nodes encounters behavior and nodes positions. Thereby, it should be able to predict when it will be in contact with other nodes and for how long (i.e. duration). In this paper, we have also investigated the requirements of ORION protocol in terms of computation and memory space for time series analysis and forecasting, and storage requirements for bundle carrying in the context of a store-and-forward routing protocol.

The remainder of this paper is organized as follows. Section II presents the state of the art for DTN protocols and the use of stochastic processes and time series analysis in network communication modeling. Section III presents details about the proposed ORION protocol. In this section, we introduce the target application (Subsection III.A), and then we present our inter-nodes encounter behavior analysis (Subsection III.B). Based on these analysis' results, we define our routing protocol (Subsections III.C and III.D). Section IV provides extensive simulation results and related discussion. Finally, Section V concludes the paper and highlights our future work.

II. RELATED WORK

In order to overcome the mentioned challenges in DTNs, it is important to design an efficient routing protocol that uses small network topology knowledge to maximize the delivery ratio and minimize the delay. Several routing protocols have been proposed for DTNs. These protocols can be classified into two main categories; replication-based and prediction (forwarding)-based protocols. With replication-based protocols, the contacts are assumed to be totally opportunistic and the required topology knowledge at each node is minimal. In this case, the simplest way to deliver a message is to send a copy to each encountered node. This is repeated until the destination receives the message. The Epidemic Routing protocol [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF] envisions this strategy. With prediction-based protocols, only a single copy exists across the network at a given time. The protocol needs to be supplied with more knowledge about the network. Given the unavailability of topology information, some protocols try to use probabilities to predict the contact. However, such prediction can be at the price of reduced delivery ratio. Most of the existing prediction-based routing protocols focus mainly on whether two nodes would be in contact in the future, without paying much attention to "when" the contact will happen or "for how long" the contact will last. This lack of contact timing information degrades the contact prediction accuracy and negatively impacts the routing performance.

A. DTN Routing Protocols Taxonomy

As mentioned earlier, the replication-based routing strategy can achieve high delivery ratio while operating with minimal knowledge. This can be suitable for networks where contacts between nodes are unpredictable and random. However, this strategy is not optimal in terms of transmission and buffer size. It also suffers from the lack of scalability. Some protocols, adopting this strategy cope with this problem by bounding the number of copies in the network trading delay for buffer occupancy. To limit the replication, two solutions are used:

-Fix the number of copies and spread them through distinct nodes. Spray & Wait routing protocol [START_REF] Spyropoulos | Spray and wait: An efficient routing scheme for intermittently connected mobile networks[END_REF] uses this solution, also called quota-based DTN routing protocols. -Use metrics based on historical encounters between nodes to decide whether to send a copy or not. PRoPHET [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF] (Probabilistic Routing Protocol using History of Encounters and Transitivity) protocol uses this solution. The PRoPHET protocol utilizes an algorithm that makes use of the non-random aspect of the real world. This is done by maintaining a set of delivery success probabilities to known destinations, and by replicating messages during opportunistic contacts. Replication is done only for an encountered node which does not have a copy of the message and has a good probability to deliver the message to its final destination. Given a node i, the probability of node i to encounter another node j is denoted as P (i, j). The delivery probabilities are computed during each contact driven by the following three rules:

1) Updating:

P (i, j)new = P (i, j) old + (1 -P (i, j) old ).Lencounter
where Lencounter is an initializing constant.

2) Aging:

P (i, j)new = P (i, j) old .γ n
where γ is an aging constant and n is the number of time units elapsed since the last aging. 3) Transitivity:

P (i, k)new = P (i, k) old + (1 -P (i, k) old ).P (i, j).P (j, k).β
where β is a scaling constant.

In the prediction (forwarding) based protocols, a node is associated with a forwarding quality/probability metric for each destination, which is usually a direct (one-hop) forwarding quality such as contact frequency [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF], or time elapsed since last contact [START_REF] Spyropoulos | Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility[END_REF][9] [START_REF] Balasubramanian | DTN routing as a resource allocation problem[END_REF].

One drawback of prediction-based routing protocols for DTNs lies in the fact that good forwarding cannot be guaranteed. Indeed, the forwarding quality of a future contact should not only consider the date of the inter-nodes contact but should also takes into account other information such as the predicted contact's trajectory, its reliability, the radio link quality, etc.

B. Times Series in Network Modeling

The proposed ORION protocol makes use of time series to predict contacts. A time series is an ordered sequence of values of a variable {Y t } t∈T indexed by an ordered set T = {t 1 , t 2 , ..., t N }. The time series analysis serves two purposes: (1) Obtain an understanding of the underlying forces and structure that have produced the observed data, and (2) Fit a model and proceed to forecasting, monitoring or even feedback and feedforward control. Time series analysis is used for many applications such as economic forecasting, sales forecasting, budgetary analysis, stock market analysis, yield projections, process and quality control, etc. Recently, it starts being used in the field of computer communications. Indeed, time series have gained the attention of many researchers for the modeling of the Internet and wireless mobile networks traffic. In [START_REF] Basu | Time series models for Internet traffic[END_REF], Basu et al. have modeled the Internet traffic using ARMA process of order (p, q). Using this model, they predict the traffic generated by a TCP source using FDDI protocol. In [START_REF] Liu | Energy efficient information collection with the ARIMA model in wireless sensor networks[END_REF], Liu et al. have proposed an energy efficient technique for data collection in Wireless Sensor Networks. A sensor is hold from transmitting redundant data. The data are not sent if they can be predicted by the sink node. For prediction, they utilize ARIMA model of order (p, d, q) [START_REF] Brockwell | Time Series: Theory and Methods[END_REF] due to its outstanding model fit and small computational cost. In [START_REF] Herbert | Fault tolerant arima-based aggregation of data in sensor networks[END_REF], Herbert et al. extend this idea to the hierarchic routing protocol LEACH [START_REF] Heinzelman | An application-specific protocol architecture for wireless microsensor networks[END_REF] by providing verification at the cluster head. This approach has shown great communication cost savings. In [START_REF] Banerjee | Implementation of the behavior and structure of the multihop mobile environment as a pushdown automata and birth-and-death based statistical model[END_REF], Banerjee et al. used a birth and death process to model the network's dynamics. A node entering in the transmission range of a source node is considered as a birth. Similarly, a death refers to when it leaves this range. Finally, in [START_REF] Singh | Temporal behavior analysis of mobile ad hoc network with different mobility patterns[END_REF], Singh et al. extend this idea by using an AutoRegressive (AR) process to model the number of a node's neighbors in a mobile ad-hoc network. When dealing with stochastic processes, values of the involved random variables are taken over time forming the time series for further analysis. An important step while analyzing time series is to determine the suitable model (or class of models) fitting the observed data. A common approach to analyze time series is the use of ARMA (AutoRegressive Moving Average) analysis. An ARMA process is a combination of an autoregressive process (AR) and a moving average (MA) process. In an AR process, a random variable is "explained" by its past values rather than other variables. While with MA process, a random variable is supposed to be explained by its actual mean, augmented by a weighted sum of the errors (random shocks) that tainted the previous values. ARMA analysis was introduced by Box and Jenkins [START_REF] Box | Time Series Analysis: Forecasting and Control[END_REF] and they have identified three steps to model and forecast time series: 1) Model Identification: this step is performed to estimate a model structure by using two essential functions: the autocorrelation function (ACF) and the partial autocorrelation function (PACF). 2) Parameter Estimation: this step is performed for fitting the identified model to the observed data. This is achieved by determining the coefficients of the linear combination. 3) Forecasting: the final objective is to predict the future values of the time series based on the already observed data and the linear combination estimated at the second step. And so, ARM A(p, q) model is defined as:

y t = c + μ + p i=1 φ i .y t-i + q j=1 θ j . t-j + e t (1)
where:

• p, q non-negative integers; orders of the AR and MA processes respectively. • φ i , θ j time-invariant coefficients off the AR and MA models respectively. • μ expectation of Y (often assumed to be equal to zero) and c a constant (often omitted). • e t samples of white noise with mean zero and σ 2 and t the white noise error terms. To be considered for ARMA analysis, a time series must be stationary. To verify the stationarity two conditions must hold:

E(y i ) = μ is constant and independent of instant t (2)
Cov(y t , y t-j ) = γ j only depends on time lag j (

The first condition means that for a stationary time series, the expectance of the studied random variable is independent is constant and independent from the period of study. The second condition means that the covariance between two values of the random variable depends only on the lag size between the two instances and it is free from the time instants values.

III. ORION ROUTING PROTOCOL

A. Target Application

In this paper, we have considered a city-bus network in which the communicating nodes consist of buses, trams, cars and hotspots. The buses and trams are assumed to be "regular" mobile nodes, where the cars are assumed to be "random" mobile nodes and finally the hotspots and access points to be fixed nodes. The regular nodes move across the area along a certain trajectory (i.e. predetermined routes based on a trace file containing the set of points that describe the path), and many nodes may share the same route moving at both directions. Random nodes move freely across the urban area. In this scenario, all mobile nodes move with a non-constant speed. Indeed, for regular nodes (i.e. Buses/Trams), between every two stops, a certain speed is chosen and kept constant in this part of the route, another speed is chosen for the next route portion. All these speed values are chosen around a certain average value (e.g. 5, 10, 15 m/s). For random nodes, the mobility follows the random way-point mobility model with the same nodes' speed values. For inter-nodes contact analysis, we have used the same number of regular and random nodes for a total number of nodes of 100, 200, 300 nodes.

Each communicating node is assumed to be equipped with localization hardware. Consequently, we propose to utilize geographic addressing and achieve data packets forwarding in a greedy fashion based on distance and/or angle calculus. With geographic Routing/Greedy Forwarding, the network address of each node includes geographic coordinates (for example a node [A], at (x, y) will have the address ID-A.X.Y). Forwarding is then said greedy if we use the geographic information for choosing forwarder nodes (e.g., choosing the closest neighbor to the destination node as the next hop).

Following the Box and Jenkins steps to model the times series using ARMA model, we have conducted some simulations of our city-bus network. In these simulations, instead of using synthetic mobility models [START_REF] Alparslan | A generalized random mobility model for wireless ad hoc networks and its analysis: One-dimensional case[END_REF] [START_REF] Hyytia | A Markovian waypoint mobility model with application to hotspot modeling[END_REF][21], we studied the two time series in pseudo-realistic environment mapped on a real city map, namely Bordeaux in France. Indeed, nodes were assumed embedded in transportation vehicles and were moving across the different routes over the city map. Moreover, nodes are having the same speeds and schedules as the actual vehicles. Cars and people were, in the other hand, moving freely (random way point) across the city and with different speeds.

In the following, we explain our methodology to perform the inter-node contact prediction.

B. Contact Behavior Analysis

For our analysis and in order to use efficiently time series, we propose to discrete the time into small periods of time Δt. In the description, we further denote {1Δt, 2Δt, ..., nΔt} as the time instants {t 1 , t 2 , ..., t n }.

In networks with intermittent connectivity, a node becomes aware of an eventual contact by the mean of periodically exchanged HELLO messages. Consequently, contact (connection) duration C with a certain node is the sum of consecutive periods of time Δt over which the node received at least one HELLO message from the other node (during this period, the node is called connected neighbor). Respectively, the duration of the non-contact (disconnection) C is the sum of consecutive periods of time over which the node did not receive any HELLO messages from the other node. The duration of a contact C and a non-contact C are two random variables. In order to study the contact behavior, we construct the two times series {C t } t∈N and { Ct } t∈N , where C t denotes the duration of the i th contact (connection), and Ct represents the duration of the i th non-contact (disconnection). N is the set of natural integers.

Examples of {C t } t∈N and { Ct } t∈N chronograms are shown in Fig. 1. To apply the Box-and-Jenkins approach, we had to verify the stationarity of the two time series. Thus, we run the stationarity test (see equations 2 and 3). The results showed that the two stationarity conditions hold for almost all the time series (∼99%) obtained from the simulation (at the rate of two times series C i and Ci by contacted node at each node). Consequently, C i and Ci can be analyzed using ARMA. Based on this information, a node can predict the future value of the contact's duration (connection's duration), and also the future value of the non-contact duration (disconnections' duration). Consequently, the node will be able to predict when the next contact will be and for how long it will last. This knowledge will be extremely beneficial to perform routing decisions.

C. ORION Contact Model Construction

After running the simulation, we extracted two time series, namely the {C t } t∈N and { Ct } t∈N , for each frequently contacted node. It was interesting to notice that all the time series were quite similar in terms of pace, even if the mobile nodes were moving with different and non-constant speeds. The rest of this section describes the Box-and-Jenkins steps applied to model the proposed times series. We dubbed this model as "ORION Contact Model" as it is related to the targeted application scenario.

1) Step 1: ORION Contact Model Identification:

We have used Minitab [START_REF] Minitab | Minitab statistical software[END_REF] to analyze the obtained time series. The autocorrelation function (ACF) and the partial autocorrelation function (PACF) are plotted in Fig. 2. According to the ACF and PACF plots, the results indicate that the best fitting model is the ARM A(2, 1) since PACF presents two significant peaks (i.e. this confirms the AR(2) part), and the ACF presents one significant peak (i.e. this confirms the M A(1) part). For all the analyzed time series, this model was the most frequent (78%), followed by ARM A(2, 2) with 7%, andARM A(3, 2) with 5% and other models having higher degrees.

Based on these results, the ORION Contact Model obtained can be written as:

C i = μ + φ 1 C i-1 + φ 2 C i-2 + θ 1 i-1 + i ( 4
)
where:

• μ denotes the mean value C i .

• φ 1 , φ 2 , θ 1 denote the ORION Contact Model parameters (φ 1 , φ 2 are related to the autoregressive part and θ 1 is related to the moving average part of the process). • i , i-1 are assumed to be independent, identically distributed random variables sampled from a normal distribution with zero mean i ∼ N (0, σ 2 ) where σ 2 is the variance.

2) Step 2: ORION Contact Model Parameters Estimation:

The second step after identifying the orders of the ORION Model is to estimate its parameters. For the AR part, the parameters can be obtained by the Yule-Walker equations [START_REF] Priestley | Spectral Analysis and Time Series[END_REF]. The principle of the Yule-Walker equation relies on the fact that there is a direct correspondence between the parameters (φ i : i = 1..p) and the covariance function of the process. This correspondence can be inverted to determine the parameters from the ACF which leads to the Yule-Walker equations:

γ m = p k=1 φ k γ m-k + σ 2 δ m ( 5
)
where m = 0, .., p yielding (p + 1) equations. γ m is the autocorrelation of Y . σ is the standard-deviation of the input noise process, and the δ m is the Kronecker Delta function. This equation is usually solved by representing it as a matrix, getting the following equation solving all φ.

⎡ ⎢ ⎢ ⎢ ⎣ γ 1 γ 2 γ 3 . . . ⎤ ⎥ ⎥ ⎥ ⎦ = ⎡ ⎢ ⎢ ⎢ ⎣ γ 0 γ -1 γ -2 • • • γ 1 γ 0 γ -1 • • • γ 2 γ 1 γ 0 • • • . . . . . . . . . . . . ⎤ ⎥ ⎥ ⎥ ⎦ . ⎡ ⎢ ⎢ ⎢ ⎣ φ 1 φ 2 φ 3 . . . ⎤ ⎥ ⎥ ⎥ ⎦ (6)
This equation provides a way to estimate the AR(p) parameters by replacing the theoretical covariance with estimated values. For the MA part, the single parameter is obtained by identification based on the estimated AR parameters and the last estimation error.

3)

Step 3: Forecasting: Since the orders of the ORION Model are fixed in time due to the mobility model, the computational cost of resolving linear systems can be avoided by extracting generic formulas. The node will have to compute the model parameters based on simplified mathematical expressions. Moreover, since these formulas include only aggregated data (sums, means, standard-deviations, variances. . . ), there is no need to store all the past data; only few values are maintained at each node. The following subsection explains the different steps to derive these simplified mathematical expressions and how they will be used for forecasting. Since the model is ARM A(2, 1), it is composed of two parts: AR(2) and M A(1). For AR(2) process we have :

x t+1 = φ 1 x t + φ 2 x t-1 + ξ t+1 (7)
We multiply both sides by one lag value and take the expectation:

x t x t+1 = φ 1 x t x t + φ 2 x t x t-1 + x t ξ t+1 (8)
We eliminate the zero correlation forcing term x t ξ t+1 and we divide by N -1:

x t x t+1 N -1 = φ 1 x t x t N -1 + φ 2 x t x t-1 N -1 (9)
We then have:

c 1 = φ 1 c 0 + φ 2 c 1 (c i is the covariance of lag i ) (10)
We divide both sides by c 0 , we obtain the equation:

r 1 = φ 1 r 0 + φ 2 r 1 since r i = c i /c 0 (11)
Doing the same thing with lag 2, we find the second equation. Then we have:

r 1 = φ 1 r 0 + φ 2 r 1 r 2 = φ 1 r 1 + φ 2 r 0 (12)
Leading to the Yule-Walker equations:

r1 r2 = r0 r1 r1 r0 φ1 φ2 r R Φ
, and so Φ = R -1 r [START_REF] Brockwell | Time Series: Theory and Methods[END_REF] Knowing that r 0 = 1:

φ1 φ2 = 1 1 -r 2 1 1 -r1 -r1 1 r1 r2 (14)
Finally, we get:

φ1 = r1(1 -r2) 1 -r 2 1 and φ2 = r2 -r 2 1 1 -r 2 1 ( 15
)
Considering the M A(1) process:

x t = θξ t-1 + ξ t ( 16
)
where ξ is the white noise N (0, σ 2 ). We multiply both sides by one lag value and take the expectation:

xt-1xt = (θξt-2 + ξt-1)(θξt-1 + ξt) (17) xt-1xt = θ 2 ξt-2ξt-1 + θξt-2ξt + θξ 2 t-1 + ξt-1ξt (18)
Knowing that:

ξ i ξ j = 0 if i = j σ 2 if i = j
we eliminate the zero terms and we divide by N -1:

x t-1 x t N -1 = θξ 2 t-1 N -1 (19)
And we get:

c 1 = θσ 2 (20)
By repeating the same operations for zero lag value:

x t x t = (θξ t-1 + ξ t )(θξ t-1 + ξ t ) (21)
We obtain:

c 0 = θ 2 σ 2 + σ 2 → c 0 = σ 2 (1 + θ 2 ) ( 22
)
Knowing that, and from the two obtained equations, we have:

r 1 = c 1 c 0 = θ 1 + θ 2 (23)
By solving the quadratic equation we find :

θ = 1 2r 1 ± 1 -2r 2 1 ( 24
)
From the three formulas, we can see that the estimation of ORION Contact Model parameters relies on the estimated values of autocorrelation of order 1 and 2. (i.e. r 1 and r 2 ). Statistically, autocorrelation of order p (i.e. r p ) is estimated by the following expression:

rp ∼ = E[(Xt -μ)(Xt-p -μ)] V ar(Xt) ∼ = E[(Xt -μ)(Xt-p -μ)] E[X 2 ] -E[X] 2 (25)
where:

EX = E[X] = μ = 1 N -1 N i=1 xt-i+1 ; E X 2 = E[X 2 ] = 1 N -1 N i=1 x 2 t-i+1 ; EX,X p = 1 N -1 N i=1 (xt -μ)(xt-p -μ)
We can see that the calculus of the autocorrelation terms relies on aggregated terms (averages). Thus, these values can be incrementally computed without keeping the entire data set as follows:

EX (t) = (N -1)EX (t-1) + xt N ; E X 2 (t) = (N -1)E X 2 (t-1) + x 2 t N ; EX,X p (t) = (N -1)EX,X p (t-1) + (xt -μ)(xt-p -μ) N
Finally, in order to adaptively estimate the parameters of the ARM A(2, 1) process and in real-time, we only need to store the following variables (rather than the entire time series):

• N The number of the considered values so far [0, t).

• x t , x t-1 , x t-2
The last three values of the time series.

• E X The last average of the values (at t -1).

• E X 2 The last average of the squared values (at t -1).

• E X,X1 , E X,X2 The last values of E X,X1 and E X,X2 respectively. Since the data are evolving in time, we propose to compute these parameters in an incremental fashion. For two different instants t 1 < t 2 the estimated parameters are different because the estimation at t 1 takes into account the data up to t 1 (i.e. [0, t 1 ]) and similarly the estimation at t 2 takes into account all the data in [0, t 2 ]. This approach makes the estimation in real-time and more accurate as new data are collected. The process of model parameters' update and future value forecasting is explained with the pseudo code in Fig. 3. Fig. 4 presents, for an arbitrary time series extracted during the learning phase and which follows the identified contact model (i.e. ARM A(2, 1)), a comparison between forecasting based on "offline" parameters estimation (i.e. the parameters are estimated considering the entire data set, then the future values are computed at each index using the obtained model) and

Contact Index

Actual Data Forecasts with "online" estimation Forecasts with "offline" estimation Fig. 4. Forecasting with "online" and "offline" parameter estimation.

forecasting based on "online" estimation (i.e. the parameters are estimated for each new observation, considering the available data so far). We can clearly see that the proposed online estimation is better than the offline estimation in predicting the future data.

D. Forwarding Algorithm

The forwarding algorithm used in ORION is based on three criteria: (1) in order to forward a packet in a greedy manner, a node will look for the closest connected neighbor to the destination, (2) if such a node is not available, the forwarder node will look for the most advancing connected neighbor toward the destination, and finally (3) if there is no such a node, the forwarder node will schedule the data packet for the best future connected neighbor. The best future connected neighbor is chosen according to an objective function. This function takes into account (1) the contact frequency, (2) the expected node trajectory, and (3) the period of time until the forecasted date of contact. Based on these contact's parameters, the objective function gave a score to each forecasted contact node. The node that has the highest score will be chosen for the packet forwarding. These three contact's parameters are considered as follows:

• Contact frequency (CF) is expressed as the number of contacts during a fixed period of time. The higher this value is, the higher the score of this future contact node becomes. • Expected trajectory is expressed as the cosine of the oriented angle between the two vectors (1) the current direction of the forwarder node and (2) the expected direction of the future contact node. The expected direction of the future contact node is simply considered the opposite direction of its last known direction. The higher this value is (this value ranges from -1 "opposite direction" to +1 "same direction"), the higher the score of this future contact node becomes. • Time to the next contact is expressed as the period of time until the next contact date. The lower this value is, the higher the score of this future contact node becomes. Consequently, and after standardization of the three parameters, the score of a future contact node is given by the following function:

f obj (Ni) = α[CF N i ] * + β[cos( D, -DN i )] * + γ[TN i -T ] * (26)
where:

• N i : Neighbor i for which information has been collected and predicted. T is the current time. • α, β, γ: weight of each parameter in the objective function.

• [] * denotes the standardized value of the parameter. This objective function can be tuned by giving different weights to the three parameters. The value of each coefficient (α, β, γ) highly depends on the considered scenario. For a simple objective function, these coefficients were all set to one. A pseudo code of the algorithm is shown in Fig. 5. A detailed version is shown in Fig. 6.

IV. PERFORMANCE EVALUATION

A. Simulation Environment

For simulation purpose, we have considered a homogeneous wireless mobile network in which mobile nodes are deployed through an area of 14, 5km x 11km with nodes' transmission range up to 200m. Network nodes are composed of nodes moving according to bus/tram trace file (50% of the nodes) or random way-point model (50% of the nodes). Two nodes are selected randomly at the beginning of the simulation to act as source and destination. The source sends periodically data packets to the destination. The simulation is run for 1800 seconds (letting sufficient start-up time for PRoPHET, i.e. 600 seconds). To demonstrate and evaluate the performance of ORION, we used OMNeT++ 4 [START_REF] Varga | The OMNET++ discrete event simulation system[END_REF]. As a comparison term, we use the PRoPHET protocol. PRoPHET is similar to ORION in a way that both protocols keep track about the encountered nodes. However, ORION gathers more information than PRoPHET in order to enhance the routing performances.

For simulation, we considered different network topologies by varying (1) the number of nodes (i.e., 100, 200, and 300 nodes) and (2) the nodes speed (i.e., 5m/s, 10m/s, 15m/s and 20m/s). For each topology, we measured various parameters: (1) the average hop count from the source to the destination, (2) the packets delivery ratio, (3) the first packet arrival, and finally (4) the average end-to-end delay. Due to space limitation, results relative to the 200 nodes topology are not shown.

We also prove that ORION routing protocol does not require more space memory to perform store-carry-and-forward routing by measuring the message queue occupancy during all the simulation period.

Packet_Queue: a data structure where all the packets to be sent are stored. Connected_Neighbors_Set(CN): the set of all neighbors that are currently in contact with this node. Estimated_Neighbors_Set(EN): the set of all estimated neighbors, i.e. the nodes whose contacts we have a historical data about. Forwarder_Node(FN): the address of the next hop. f obj : This function gives a score to a neighbor based on its next contact date, contact frequency and expected moving direction. prediction error margin. Thus, packets loss will be more frequent. However, the packet delivery ratio is still higher than PRoPHET's. c) First Packet Arrival (FPA) and End-to-End Transmission Delay (EED): Because of the greedy nature of ORION, packets will always choose either the shortest, the "earliest" next hop or a next hop moving toward the destination, making packets arrive more quickly at the destination node (Fig. 9) and experiencing shorter end-to-end delay (Fig. 10) compared to PRoPHET where the next hop is chosen based on only its success delivery probability. d) Bundle Queue Occupancy: From Fig. 11 we can clearly see that ORION routing protocol does not require excessive memory space for message queue in order to achieve store-and-forward routing. In our simulations, and in small network topology (100 nodes), the average message queue occupancy is high ( 40 messages in case of 5 m/s node mobility speed) when the node mobility speed is slow. Due to the rarity of the contacts, nodes are obliged to keep messages for a long period of time. However, with higher node mobility speeds, the average queue occupancy decreases accordingly (average of 25 messages in the case of 20 m/s node mobility speed). Furthermore, as in the case of PRoPHET, packets experience higher hop count than ORION, the average queue size is higher than in the case of ORION.

V. CONCLUSION

In this paper, we have described a new routing protocol, dubbed as ORION, which is suitable for mobile delay tolerant networks. Since the network dynamics are often not so random such as in city-wide inter-hotspot network interconnected through taxis, buses and vehicles, the contacts between two communicating nodes can be analyzed and, moreover, predicted. ORION routing protocol is based on greedy geographic forwarding and contacts predictions, switching between store-and-forward and store-carry-and-forward strategies in such a way, that packet forwarding is always optimal. ORION uses ARMA model online parameter estimation to predict future contacts due to its outstanding fit to this kind of network dynamics. Simulation results show that ORION routing protocol outperforms PRoPHET in terms of different metrics such as first packet arrival delay, end-to-end transmission delay, hop count, and packet delivery ratio. Moreover, ORION routing protocol does not require excessive memory space to achieve efficient delay-tolerant routing.

Fig. 1 .

 1 Fig. 1. Variation of C i and Ci over time.

Fig. 2 .

 2 Fig. 2. Autocorrelation and Partial Autocorrelation functions' (ACF & P ACF ) plots for contact's duration.

Fig. 3 .

 3 Fig. 3. Online model parameters update, and future value forecasting.

Fig. 5 .

 5 Fig. 5. Pseudo code for ORION forwarding algorithm

Fig. 9 .Fig. 10 .

 910 Fig. 9. First Packet Arrival in 100 and 300 nodes topologies with variant speed.

Fig. 11 .

 11 Fig. 11. Average message queue occupancy in 100 and 300 nodes topologies with variant speed.

  Require: v new value of the time series Ensure: xt+1 estimated future value of the time series 1: N + +; 2: Update_Sliding_W indow(v, xt, xt-1, xt-2); 3: EX = Compute_New_Average(EX, N, xt); 4: E X 2 = Compute_New_Average(E X 2 , N, xt); 5: EX,X 1 = Compute_New_Average(EX,X 1 , N, xt, xt-1); 6: EX,X 2 = Compute_New_Average(EX,X 2 , N, xt, xt-2);

	7: r1 = Compute_AutoCorrelation(EX, E X 2 , EX,X 1 ); 8: r2 = Compute_AutoCorrelation(EX, E X 2 , EX,X 2 ); 9: φ1 = Compute_P hi_1(r1, r2);
	10: φ2 = Compute_P hi_2(r1, r2);
	11: θ = Compute_T heta(r1);
	12: xt+1 = Estimate_F uture_V alue_ARM A21(φ1, φ2, θ);


Bérénice Oger

HYPERTREE POSETS AND HOOKED PARTITIONS

Keywords: Poset, Incidence Hopf algebra, Hypertree, Moebius number

Introduction

In 1994, W. Schmitt defined in his article [START_REF] William | Incidence Hopf algebras[END_REF] the notion of incidence Hopf algebra associated to a given family of posets satisfying some closure conditions. Using the structure of Hopf algebra, one can define a convolution on characters of this algebra. The Moebius number for posets of the family can then be computed using characters on the incidence Hopf algebra.

However, the incidence Hopf algebras of W. Schmitt are only defined for bounded posets. We introduce in this article a way to compute some characters for another type of 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 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 on maps from the bialgebra B to Q 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 theorem to hypertree posets.

In the third part of the article, we recall the notion of hypertrees. Hypergraphs have been introduced in 1989 by C. Berge in [START_REF] Berge | Hypergraphs[END_REF] 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 prove the following criterion on α i and π j for the existence of a hypertree with α i vertices of valency i and π j edges of size j:

(0.1) k i=1 α i = n, l j=2 (j -1)π j = n -1 and k i=1 iα i = n + l j=2 π j -1.
Then, using this criterion, we compute the coproduct in the bialgebra B HT associated with hypertree posets h n and partition posets p n . The coproduct is given by the following formula:

Theorem. If the set P(n) is the set of tuples α = (α 1 , . . . , α k ) and π = (π 2 , . . . , π l ) satisfying Equations (0.1), the coproduct of h n in B HT is given by:

∆(h n ) = 1 n × (α,π)∈P(n) n! j≥2 (j -1)! πj π j ! × k! × n! i≥1 (i -1)! αi α i ! k i=2 p αi i ⊗ l j=2 h πj j , with k = j≥2 π j -1.
This formula is linked with the number of hypertrees of fixed valencies and edge sizes sets, which was also computed by M. Bousquet-Mélou and G. Chapuy in [START_REF] Bousquet | The vertical profile of embedded trees[END_REF] (see also [START_REF] Stanley | Enumerative Combinatorics[END_REF]), in terms of bicoloured trees, and by R. Bacher in [START_REF] Bacher | On the enumeration of labelled hypertrees and of labelled bipartite trees[END_REF] in terms of hypertrees. The first step of this computation is to show that it can be reduced to the computation of the number of ways to build a hypertree from a π-hooked partition. Then we show with a proof using a Prüfer code that this construction is encoded by words. Finally, we count these words.

The Moebius number of the poset of hypertrees on n vertices has been computed by J. McCammond and J. Meier in 2004 in the article [START_REF] Mccammond | The hypertree poset and the l 2 -Betti numbers of the motion group of the trivial link[END_REF]. F. Chapoton has computed its characteristic polynomials in [START_REF] Chapoton | Hyperarbres, arbres enracinés et partitions pointées[END_REF] and has conjectured the action of the symmetric group on the homology of the hypertree poset, which has been proven in [START_REF] Oger | Action of the symmetric groups on the homology of the hypertree posets[END_REF]. We give a new proof for the computation of the Moebius number of the hypertree posets at the end of the article. This computation gives the following enumerative formula:

Proposition. The following equality holds:

(n -1) n-2 = (α,π)∈P(n) (-1) iαi-1 n × n! j≥2 (j -1)! πj π j ! × k! × n! i≥1 α i !
, where P(n) is the set of pairs (α i , π j ) satisfying Equations (0.1).

Generalities on posets and incidence Hopf algebras

We introduce in this section 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 ≤. We called trivial 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, it is said to be a bounded poset. In this case, its least and greatest elements will be respectively denoted by 0P and 1P , or 0 and 1 if there is no ambiguity.

Let us define the following poset invariant:

Definition 1.1. The Moebius function µ is recursively defined on a poset P by

µ(x, x) = 1, ∀x ∈ P µ(x, y) = - x≤z<y µ(x, z), ∀x < y ∈ P.
The Moebius invariant, or Moebius number, of a bounded poset P is defined as:

µ(P ) := µ( 0P , 1P ).
Example 1.2. The Moebius 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 of W. Schmitt [START_REF] William | Incidence Hopf algebras[END_REF].

A family of posets 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. The isomorphism of posets is an example of order compatible relation.

Given K a commutative ring with a unit, and ∼ 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 K-coalgebra C(P) as follow:

Proposition 1.3 (Theorem 3.1 in [START_REF] William | Incidence Hopf algebras[END_REF]). Let C(P) denote the free K-module generated by P/ ∼. We define linear maps ∆ : C(P) → C(P) ⊗ C(P) and ǫ : C(P) → K by:

∆[P ] = x∈P [0 P , x] ⊗ [x, 1 P ] and ǫ[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 .
These hypotheses assure that product will be well defined on the quotient. An order compatible relation on a hereditary family P which is also a reduced congruence is called a Hopf relation on P. The isomorphism of posets is a Hopf relation.

Proposition 1.4 ([Sch87]

). Let ∼ be a Hopf relation on a hereditary family P. Then H(P) = (C(P), ×, ∆, ǫ, S) is a Hopf algebra over K.

Example 1.5. The incidence Hopf algebra generated by the family of poset of subsets of 1, n is the polynomial algebra K[x], endowed with the following coproduct:

∆(x n ) = n k=0 n k x k ⊗ x n-k .
We deal here with the field K = Q. We can consider the set of Q-linear homomorphisms of algebras between H(P) and Q, which send the trivial poset to the unit of Q. These homomorphisms are called characters. The set of characters can be endowed with a structure of group as follows. Given two characters φ and ψ, the convolution of φ and ψ is defined on any element P of H(P) by: φ * ψ(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).

Incidence Hopf algebra of triangle and diamond posets

2.1. Presentation of the triangle and diamond posets and their incidence Hopf algebra. Let us consider the family F 0 generated by posets {(d i ) i≥1 , (t j ) j≥3 }, such that d 1 is the trivial poset, d i is an interval for all i ≥ 2 and t j is a poset with a least element but without a greatest one. The (d i ) i≥1 will be called the diamond posets and the (t j ) j≥2 will be called the triangle posets. We denote by t j the augmented triangle posets, bounded by the addition of a greatest element 1. We moreover assume that:

• any closed interval in a diamond poset can be written as a product of diamond posets, (Decomposition Property 1) • any closed interval in a triangle poset can be written as a product of diamond posets, (Decomposition Property 2 a) • and any half-open interval [t, 1) in an augmented triangle poset t j can be written as a product of triangle or trivial posets. (Decomposition Property 2 b) We denote by F 1 the hereditary family generated by F 0 : due to 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 them 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 hereditary family F 2 generated by the elements of the family F 1 , augmented with a maximal element when they are not intervals: F 2 is then a hereditary family of intervals. We apply Schmitt's construction to this family taking the 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.

A smaller bialgebra constructed on triangle and diamond posets.

The family F 1 is closed under the direct product and interval closed, 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.

Taking the isomorphism of posets as a Hopf relation ∼, the set F1 = F 1 / ∼ is a monoid, with product induced by direct product of posets and identity element 1 equal to the class of any one point interval. Let us denote by V (F 1 ) the free K-module generated by F1 . The structure of monoid on F1 induces a structure of algebra on V (F 1 ), isomorphic to the monoid algebra of F1 over K. 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 . All elements of F 1 have a least element. We endow it with the following coproduct defined on d, an isomorphism class of posets with both a least and a greatest elements, and t, an isomorphism class of posets with a least element but no greatest one, by:

∆(d) = x∈d [ 0d , x] ⊗ [x, 1d ],
and

∆(t) = x∈t [ 0t , x] ⊗ [x, 1 t ).
This coproduct is a morphism of algebras, as an interval in a product of posets can be seen as a product of intervals.

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. We denote by B ⋄,▽ the obtained bialgebra.

The subalgebra D ⋄ generated by the diamond posets is also a subcoalgebra according to the first decomposition property: this is a subbialgebra of B ⋄,▽ . This subbialgebra is isomorphic as a bialgebra to the incidence Hopf algebra of diamond posets. According to the second decomposition property, the subalgebra T ▽ of B ⋄,▽ generated by the triangle posets is a right comodule over D ⋄ . Thanks to the definition of the coproduct and the structure of direct product of posets, the coproduct on T ▽ is still a homomorphism of algebras.

We show that the computation of some characters on the incidence Hopf algebra H ⋄,▽ can be reduced to some calculus on the bialgebra B ⋄,▽ .

2.3.

Results on the computation of some characters on the incidence Hopf algebra of triangle and diamond posets. We define the following linear application:

λ : B ⋄,▽ → H ⋄,▽ which sends an isomorphism class c di of a diamond poset d i in B ⋄,▽ to the isomor- phism class c di of d i in H ⋄,▽
and which sends an isomorphism class c tj of a triangle poset t j in B ⋄,▽ to the isomorphism class c tj of the augmented triangle poset t j in H ⋄,▽ . This linear application is well defined. Indeed, if two diamond posets are in the same isomorphism class in B ⋄,▽ , then they are isomorphic so they are also in the same isomorphism class in H ⋄,▽ . If two triangle posets are in the same isomorphism class in B ⋄,▽ , then they are isomorphic so 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 moreover remark that the fibre of an isomorphism class in the image of λ is made of 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.

Let us consider two characters α and β on H ⋄,▽ such that there exists two rational numbers ǫ α , ǫ β and two maps α and β from B ⋄,▽ to Q which satisfy:

α(λ(c di )) = α(c di ), α(λ(c tj )) = ǫ α α(c tj ), and
β(λ(c di )) = β(c di ), β(λ(c tj )) = ǫ β β(c tj ), for all isomorphism class c di of diamond poset d i of F 0 and c tj of triangle poset t j of F 0 .
Then, the convolution of α and β can be computed thanks to the following theorem:

Theorem 2.1. The convolution of the characters α and β on H ⋄,▽ is given by:

α * β(λ(c di )) = α(c (1) di ) β(c (2) di ),
and

α * β(λ(c tj )) = ǫ β α(c (1) tj ) β(c
(2)

tj ) + ǫ α α(c tj ),
where

∆(c di ) = c (1) di ⊗ c (2) di and ∆(c tj ) = c (1) tj ⊗ c (2) tj in B ⋄,▽ .
Proof. The isomorphism class λ(c di ) is the isomorphism class of the diamond poset d i in H ⋄,▽ by definition of λ. Moreover, the coproduct of λ(c di ) in H ⋄,▽ and of c di in B ⋄,▽ are the same by definition of the coproduct. As α, α on the one hand and β and β on the other hand are equal on λ(c di ) and c di respectively, the first equality follows.

To obtain the second equality, let us remark that the isomorphism class λ(c tj ) corresponds to the isomorphism class of the augmented triangle poset t j by definition of λ. Hence the coproduct of λ(c tj ) in H ⋄,▽ has one more term than the coproduct of c tj on B ⋄,▽ , due to the fact that the poset t j has one more element than the poset t j . This term is λ(c tj ) ⊗ 1. All the other terms can be matched by associating λ(c tj ) to the unique isomorphism class of triangle poset of its fibre c tj . Moreover, the posets on the left part of the coproduct of λ(c tj ) are of diamond type, except for the term that does not belong to the coproduct of c tj and α and α coincides on diamond posets. Therefore we have:

α * β(λ(c tj )) = α(c (1) tj )ǫ β β(c (2) tj ) + ǫ α α(c tj ).
This gives the result.

Remark that as the assumptions on α and β are the same, the previous theorem also gives the formula for β * α.

We will use these results in Section 3.3 to compute some characters on the hypertree posets.

Incidence Hopf algebra of hypertree posets and partition posets

From now on, we choose K = Q.

Incidence Hopf algebra of the 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. 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 are edges containing the vertices v i and v i+1 , for all i ∈ 0, n -1 . A hypertree is a hypergraph such that given any pair (s, f ) of vertices, there exists one and only one walk from s to f without repeated edges. We say that a hypertree is on n vertices if the set V is of cardinality n.

We can 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 HT n . This poset has a least element 0 which is the hypertree with only one edge. The poset obtained by adding to this poset a greatest element 1 is called the (n-) augmented hypertree poset and denoted by HT n . Some intervals in the hypertree posets will be described in terms of another type of posets: the partition posets. A partition poset is a poset on the set of all the partitions of a set V . A partition p 1 is smaller than another one p 2 if each part of p 1 is the union of some parts of p 2 . The partition poset on n vertices Π n is based on the set of partitions of a set of cardinality n.

{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 3.2. The poset Π 4
We need the following result of J. McCammond and J. Meier on intervals in the hypertree poset: Lemma 3.1 (Lemma 2.5, [START_REF] Mccammond | The hypertree poset and the l 2 -Betti numbers of the motion group of the trivial link[END_REF]). Let τ be a hypertree on n vertices. (a) The interval [ 0, τ ] is a direct product of partition posets, with one factor Π j for each vertex in τ with valency j. (b) The half-open interval [τ, 1) is a direct product of hypertree posets, with one factor HT j for each edge in τ with size j.

Let us consider the incidence Hopf algebra H HT = (H HT , ×, ǫ, η, ∆, S) obtained from the construction of §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 , where h n is the shorter notation for HT n , for the set of triangle posets. Indeed, p 1 , the partition poset on one element and the hypertree poset on two elements HT 2 are 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. This fact combined with Lemma 3.1 implies that this family satisfies the decomposition property and then all the requirements of Section 2.1. We will also denote by h n the augmented hypertree poset HT n .

We consider H * HT , the group of characters χ : H HT → Q. We aim at calculating the Moebius numbers for the augmented hypertree posets using the classical techniques of characters. A good reference for such a computation of characters, and Moebius numbers, for the partition posets is the article [START_REF] Speicher | Free probability theory and non-crossing partitions[END_REF] of R. Speicher. To compute the character which associates to any poset of H HT its Moebius number, we use Theorem 2.1.

We call B HT the bialgebra defined in Section 2.2. Thanks to Lemma 3.1(b), we obtain that this bialgebra is not only generated as an algebra by isomorphism classes of partition posets and isomorphism classes of intervals [τ, 1), for any 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 respectively on n and m are isomorphic if and only if m and n are equal. As every p i and h j are pairwise in different 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.

Hence, the convolution of characters α and β on H HT can be computed using the bialgebra B HT : Proposition 3.2. The convolution of characters α and β on H HT can be computed using maps α and β from B HT to Q, provided they exist and satisfy the following equations, for all i ≥ 1 and n ≥ 3:

α(p i ) = α(p i ), α( h n ) = ǫ α α(h n ), β(p i ) = β(p i ), β( h n ) = ǫ β β(h n ), with ǫ α , ǫ β ∈ Q.
This computation is given by:

α * β(p i ) = α(p (1) i ) β(p (2) i ), and α * β( h j ) = ǫ β α(h (1) j ) β(h (2) j ) + ǫ α α(h j ), where ∆(p i ) = p (1) i ⊗ p (2) i and ∆(h j ) = h (1) j ⊗ h (2) j in B HT .
Proof. This is a corollary of Theorem 2.1 for p i and h j .

Example 3.3. We consider the poset HT 3 drawn on figure 3.1. The computation of the coproducts gives:

∆( h 3 ) = 1 ⊗ h 3 + 3 p 2 ⊗ h 2 + h 3 ⊗ 1, in H HT , ∆(h 3 ) = 1 ⊗ h 3 + 3 p 2 ⊗ h 2 , in B HT .
We determine a closed expression for the coproduct in the next section.

3.2. Computation of the coproduct. We now compute the coproduct ∆ in the algebra B HT . We denote by 1 the neutral element of B HT for the product, i.e. the trivial poset.

The coproduct of isomorphism classes of partition posets p n has already been computed. It can be found for instance in the article of W. Schmitt [START_REF] William | Incidence Hopf algebras[END_REF]: Proposition 3.4 (Example 14.1 in [START_REF] William | Incidence Hopf algebras[END_REF]). : The coproduct on the isomorphism classes of partition posets is given by:

∆ p n n! = n k=1 (j1,...,jn)∈N n i=1 ji=k, n i=1 iji=n k j 1 , . . . , j n n i=1 p i i! ji ⊗ p k k! ,
where p 1 is the trivial poset.

Let us now compute the coproduct for h n . According to the structure of the hypertree posets and Lemma 3.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 . We first establish a criterion to describe the tensor products appearing in the coproduct of h n . We write the coproduct as follows:

(3.1) ∆(h n ) = (α,π)∈Pn c n α,π p α ⊗ h π ,
where P n is the set of pairs (α, π) such that c n α,π does not vanish, and for all α = (α 1 , α 2 , . . . , α k ) and π = (π 2 , π 3 , . . . , π l ), p α = 1 α1 p α2 2 . . . p α k k and h π = h π2 2 h π3 3 . . . h π l l . The coefficient c n α,π corresponds to the number of hypertrees in HT n with α i vertices of valency i and π j edges of size j, for all i ≥ 1 and j ≥ 2.

We now characterize the set P n . We consider hypertrees as 1, n -labelled bipartite trees as in [START_REF] Mccullough | Symmetric automorphisms of free products[END_REF]. 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. We denote by α i the number of labelled vertices of valency i and by π j the number of unlabelled vertices of valency j (or of edges of size j in the hypertree). We want to determine necessary and sufficient conditions on (α 1 , . . . , α l ) and (π 2 , . . . , π k ) for the existence of a hypertree with α i vertices of valency i and π j edges of size j, for all i ≥ 1 and j ≥ 2. We hence obtain the following criterion for the non-vanishing of c n α,π , expressed in terms of hypertrees: Proposition 3.5. Given two tuples α = (α 1 , . . . , α k ) and π = (π 2 , . . . , π l ), there exists a hypertree with α i vertices of valency i and π j edges of size j if and only if:

(3.2) k i=1 α i = n, l j=2 (j -1)π j = n -1 and k i=1 iα i = n + l j=2 π j -1.
We postpone the proof of this proposition to illustrate it through an example.

Example 3.6. For n = 4, the second equation of (3.2) implies that l j=2 π j ≤ 3, i.e. k i=1 iα i ≤ 6. The possible α are: • α = (4), then we obtain the condition l j=2 π j = 1 so the only possible π is π = (0, 0, 1), • α = (3, 1), then we obtain the condition l j=2 π j = 2 so the only possible π is π = (1, 1), • α = (2, 2), then we obtain the condition l j=2 π j = 3 so the only possible π is π = (3), • α = (3, 0, 1), then we obtain the condition l j=2 π j = 3 so the only possible π is π = (3).

Proof. Suppose that there exists such a hypertree. Every vertex has a fixed valency. Therefore, counting vertices, we have the first equation:

k i=1 α i = n.
By construction of the labelled tree, every unlabelled vertex is linked with a labelled vertex. This leads to the following equality by counting edges around labelled and unlabelled vertices:

(3.3) k i=1 iα i = l j=2 jπ j .
Moreover, to a bipartite tree can be associated 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.4) χ = 1 = j≥2 π j - j≥2 jπ j + i≥1 α i .
These equations are equivalent to Equations (3.2). We can also deduce from the second equation of the proposition the following expression of π 2 in terms of π j for j ≥ 3:

π 2 = n -1 - j≥3 (j -1)π j .
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, j ≥ 2, such that Equations (3.2) are satisfied. As Equation (3.3) is satisfied, we can then choose a way to associate the vertices to obtain a 1, n -labelled 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 Equation (3.4) 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 is connected, then it has no cycles: it is a tree and we have constructed a 1, n -labelled tree. The associated hypertree has fixed valency and edge sizes sets. If the graph 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 component, we can repeat it until we find a hypertree matching the required conditions.

We then want to compute the coefficient c n α,π when it does not vanish. We do it using bijections. Given a tuple π, we call π-hooked partition a partition with one block made of a vertex and with π j other blocks made of a hook and j -1 vertices, for all j ≥ 2.

Example 3.7. A π-hooked partition P , for π = (1, 2): 2 1 5 4 3 6 . Then the assembly of elements of a π-hooked partition into a hypertree can be seen as an assembly of coat-hangers and coat racks. We represent here the hypertree T of example 3.9: 2 6 1 5 4 3 . For convenience purposes, we will write X for the hook and represent the πhooked partition as:

P = (2) (X|1 5) (X|4 3) (X|6).
Rooting hypertrees in one vertex, i.e. choosing one vertex in each hypertree, gives the following equation, by replacing c n α,π by

c n• α,π
n in Equation (3.1):

∆(h n ) = 1 n (α,π)∈Pn c n• α,π p α ⊗ h π ,
where c n• α,π corresponds to the number of rooted hypertrees in HT n with α i vertices of valency i and π j edges of size j, for all i ≥ 1 and j ≥ 2.

Let us fix π and α and denote by Π HP the set of π-hooked partitions and by H p α,π , the set of rooted hypertrees with α i vertices of valency i and π j edges of size j. The cardinality of H p α,π is c n• α,π . We consider the map ϕ : H p α,π → Π HP defined by taking for every edge e the set of all vertices of e, except the closest to the root, and adding a hook to this set. If we add the singleton made of the root to this set of hooked sets, we obtain a π-hooked partition. Indeed, all sets but one of cardinality one have a hook and the size of each hooked set is one less than the size of the associated edge.

Given P in Π HP , we call F P the fibre ϕ -1 (P ). The fibres of two distinct elements of Π HP are necessarily disjoint as their images by ϕ are different. Moreover, any element in H p α,π has an image in Π HP by ϕ. The coefficient c n• α,π is then the sum of the cardinalities of the disjoint fibres. As we will see in the proof, the cardinality of a fibre is independent from the considered π-hooked partitions: we denote it by d n α,π . We will say that we can construct a hypertree H from a π-hooked partition P if ϕ(H) = P .

Let us now link hypertrees to hooked partitions:

Lemma 3.8. The coefficient c n α,π is linked with d n α,π by:

(3.5) c n α,π = 1 n × n! j≥2 (j -1)! πj π j ! × d n α,π .
Proof. We want to compute the cardinality c n• α,π of H p α,π . Let us consider the action of the symmetric group S n on H p α,π . By definition of the map ϕ, which does not depend on the labels of the vertices, this action induces an action of the symmetric group on the set Π HP . The action of the symmetric group S n on the set of all hooked partitions of type π is transitive, as it does not change the sizes of the blocks of the partitions. We call (O j ) 1≤j≤p the orbits for the action of S n on the set H p α,π . The fibre F P has a component f P j in every orbit O j . We recap all these notations on the following diagram:

ϕ Π HP H p α,π O 1 O 2 O 3 P H 3 H 2 H 1 f P 3 f P 2 f P 1 F P Figure 3.4. The map ϕ.
We consider a hypertree H j in each f P j . The orbit-stabilizer theorem applied on O j gives:

n! = |O j | × | Aut Hj |, where | Aut Hj |
is the cardinality of the automorphism group of the rooted hypertree H j .

As H p α,π = p j=1 O j , we obtain the relation:

(3.6) c n• α,π = n! × p j=1 1 | Aut Hj | .
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 P j . Indeed, if σ ∈ S n sends a hypertree H of f P k to a hypertree H ′ of f P k , then as ϕ(H) = ϕ(σ(H)) = P , σ stabilizes P . Then, the orbit-stabilizer theorem applied on f P j gives: (3.7)

|f P j | × | Stab GP H j | = |G P | = j≥2 (j -1)! πj π j !,
where

Stab GP H j = {σ ∈ G P |σ(H j ) = H j }.
We show that Stab GP H j = Aut Hj . As G P ⊆ S n , it is easily shown that Stab GP H j ⊆ Aut Hj . Let us consider σ in Aut Hj , then ϕ(σ(H j )) = ϕ(H j ) = P and ϕ(σ(H j )) = σ(P ): σ stabilizes P . Therefore, we obtain the relation Stab GP H j = Aut Hj . Combined with Equation (3.6) and Equation (3.7), we get the result, as

d n α,π = p j=1 |f P j |.
Example 3.9. consider the following π-hooked partition P :

P = (2) (X|1 5) (X|4 3) (X|6),
with π = (1, 2), where X| represents the hook of the block. For α = (4, 2), we can construct the following rooted hypertrees (and many others):

T = 6 1 5 2 4 3 and T ′ = 6 5 1 2 4
3 . We describe an example of the action of the group G P on the fibre of P . Considering T and T ′ , which are in the fibre of P , the permutation (3 4) fixes T and T ′ but the permutation (1 5) sends T to T ′ . Then 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 π-hooked partition P π This is also the cardinality of the fibre ϕ -1 (P π ). It is given by a bijection introduced by R. Bacher in [START_REF] Bacher | On the enumeration of labelled hypertrees and of labelled bipartite trees[END_REF], which we recall for self-containment of this article: Lemma 3.10. Given a pair (α, π) in P n and a π-hooked 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 all 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 π-hooked partition P π and which have α i vertices of valency i for all 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 hook instead: we obtain two blocks, the one of the root and another hooked one of size n -1. Given a π-hooked 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 can 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 by s m the size of the minimal leaf. Then 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 the 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 by one the number of occurrences of w 1 in the word associated with H ′ compared with the word associated with H. If w ′ is the word associated with H and H ′ , we obtain the relation w = w 1 w ′ .

Moreover, the hooked partition associated with H ′ can be obtain from P π by deleting the hooked 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 all i = v, v -1, α v -1 letters appear v -1 times and α v-1 + 1 letters appear v -2 times. Let us remark that the vertex w 1 is of valency v -1 in H ′ so appear v -2 times in w ′ . Then, 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 π-hooked partition and a word w satisfying the required conditions, we can build the associated rooted hypertrees by ordering the blocks with a hook 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 construction of rooted hypertrees from hooked partitions and the set of words of the lemma.

Example 3.11. Considering the hooked partition P and the hypertrees T , T ′ and T ′′ of Example 3.9, the words respectively associated to the construction of T , T ′ and T ′′ from P are: 1 6, 5 6, and 2 6.

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 π-hooked 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 3.12. The number of words on k letters, on an alphabet of size n, with α i letters repeated i -1 times is:

(3.8) d n α,π = k! × n! i≥2 (i -1)! αi α i ! .
Proof. The number of words on 1, n , of length k, with i≥2 α i different letters, where α i letters appearing i -1 times for all i ≥ 2 is:

k! × n! i≥1 (i -1)! αi α i ! .
Indeed, there are n α1,α2,... ways to choose the letters of the word. As the letters are elements of 1, n , there is a natural total order on the set of letters appearing i times. We consider letters according to their orders. Then, if p positions in the word have already been chosen, we have k-p i choices for the positions of a letter appearing i times. Combining these enumerations gives the result.

Thanks to this lemma, we obtain the following proposition: Proposition 3.13. If the tuples α = (α 1 , . . . ) and π = (π 2 , . . . ) satisfy Equations (3.2), the number of hypertrees with α i vertices of valency i and π j edges of size j, with i ≥ 1 and j ≥ 2 is given by:

(3.9) c n α,π = 1 n × n! j≥2 (j -1)! πj π j ! × k! × n! i≥1 (i -1)! αi α i ! , with k = j≥2 π j -1.
Proof. This theorem follows from Lemmas 3.8, 3.10 and 3.12.

This proposition associated with Equation (3.1) gives the coproduct:

Theorem 3.14. If the set P(n) is the set of tuples α = (α 1 , . . . , α k ) and π = (π 2 , . . . , π l ) satisfying Equations (0.1), the coproduct of h n in B HT is given by:

∆(h n ) = 1 n × (α,π)∈P(n) n! j≥2 (j -1)! πj π j ! × k! × n! i≥1 (i -1)! αi α i ! k i=2 p αi i ⊗ l j=2 h πj j , with k = j≥2 π j -1.
Example 3.15. We can now compute the coproduct of some h n . Using the values of (α, π) on which c n α,π does not vanish, computed in Example 3.6, we obtain for h 4 :

∆h 4 = 1 4 × 4! 3! × 0!4! 4! × p 4 1 ⊗ h 4 + 1 4 × 4! 2! × 1!4! 3! × p 3 1 p 2 ⊗ h 2 h 3 + 1 4 × 4! 3! × 2!4! 2!2! × p 2 1 p 2 2 ⊗ h 3 2 + 1 4 × 4! 3! × 2!4! 3!2! × p 3 1 p 3 ⊗ h 3 2 , ∆h 4 = 1 ⊗ h 4 + 12 p 2 ⊗ h 2 h 3 + 12 p 2 2 ⊗ h 3 2 + 4 p 3 ⊗ h 3 2 .
When summing the coefficients in this coproduct, we obtain as expected the total number of hypertrees on 4 vertices, which is 29.

3.3.

Computation of the Moebius number of the augmented hypertree posets. On any incidence Hopf algebra H with generators g n (which are posets), we define the characters ζ and µ for all n ≥ 1 by:

ζ : g n → 1 and µ : g n → µ(g n ),
where µ(g n ) is the Moebius number of the poset g n .

These characters are the inverse of each other. It 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 Moebius function:

µ * ζ([h, h]) = µ([h, h]) = 1 and µ * ζ([h, h ′ ]) = h≤x≤h ′ µ([h, x]) × 1 = µ(h, h ′ ) + h≤x<h ′ µ(h, x), for all intervals [h, h ′ ], h < h ′ in H.
According to the definition of the Moebius function 1.1, µ * ζ and ζ * µ vanish on any non trivial interval.

We want to compute the Moebius number of the augmented hypertree posets. We thus use Proposition 3.2. To prove that the characters satisfy the assumptions of the proposition, we need the following definition and lemma: Definition 3.16. If P is a finite poset with a unique least element, then, we define a 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 3.17 (Lemma 4.4 in [START_REF] Mccammond | The hypertree poset and the l 2 -Betti numbers of the motion group of the trivial link[END_REF]). If P i , i ∈ [k] is a list of finite posets each with a unique minimal element and

Q = k i=1 P i , then s(Q) = k i=1 s(P i ).
Then we can define the maps from B HT to Q, for any poset p of B HT with both a least and a greatest element and any 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 3.17, for all i ≥ 2 and j ≥ 3:

ζ( k i=1 p i ) = k i=1 ζ(p i ), ζ( l j=1 h j ) = l j=1 ζ(h j ), and
µ( k i=1 p i ) = k i=1 µ(p i ), µ( l j=1 h j ) = l j=1 µ(h j ).
As these maps satisfy the conditions of Proposition 3.2, we apply it in the following subsections. As partition and hypertree posets are not mixed in the coproduct of hypertree poset, the computation of the convolution of µ and ζ will be given by a computation using only the values of ζ and µ on the partition and the hypertree posets. The first part of this section will be devoted to the equation ζ * µ = ǫ and the second part will be devoted to the equation µ * ζ = ǫ.

3.3.1. Right-sided computation. In this section, we give a simplified proof of the result of J. McCammond and J. Meier on the computation of the Moebius number of the augmented hypertree poset.

Applying the Moebius function at the right side of the coproduct, we obtain:

ζ * µ( h n ) = 0,
for all n ≥ 2. Hence, applying the computation of the coproduct of Theorem 3.14 and Proposition 3.2, we obtain the following equality for n ≥ 2:

0 = - µ(h (2) n ) + 1,
where ∆(h n ) = h To obtain a closed formula, we consider the exponential generating series of hypertrees with a weight -µ( HT i ) for each edge of size i:

T (x) = -x + n≥2 h∈HTn i∈ES(h)
-µ( HT i )

x n n! ,

where ES(h) is the multiset of edge sizes of hypertree h. Using Equation (3.10), we obtain:

T (x) = -x - n≥2 (-x) n n! = 1 -e -x .
Moreover, it has been proven by Kalikow in [START_REF] Louis | Enumeration of parking functions, allowable permutation pairs, and labeled trees[END_REF] that the derivative of T satisfies the following functional equation: Theorem 3.18 (Kalikow). The generating series T satisfies the following equation:

xT ′ (x) = x × exp(y(x)) where y(x) = j≥1 -µ( HT j+1 )

x j T ′ (x) j j!

We hence obtain:

x = j≥1 µ( HT j+1 )

x j e -jx j! .

This proves the following theorem by J. McCammond and J. Meier:

Theorem 3.19 (Theorem 5.1 in [START_REF] Mccammond | The hypertree poset and the l 2 -Betti numbers of the motion group of the trivial link[END_REF]). The Moebius number of the augmented hypertree poset on n vertices is given by: µ( HT n ) = (-1) n-1 (n -1) n-2 .

As the homology of the augmented hypertree poset is concentrated in top degree, this Moebius 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 in [START_REF] Oger | Decorated hypertrees[END_REF]. Proof. This comes from the computation of the coproduct, combined with the Moebius numbers of the augmented hypertree posets and of the partition posets. Indeed, the Moebius number of the partition poset on n elements is given by (-1) n-1 (n -1)!.

Figure 2 . 1 .

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

Figure 3 . 1 .

 31 Figure 3.1. The poset HT 3

Figure 3

 3 Figure 3.3. A hypertree and its associated labelled bipartite tree.

  1, the definition of the coproduct on B HT and the multiplicativity of -µ, we thus obtain:(3.10) µ( HT n ) = h∈HTn, h> 0 i∈ES(h) -µ( HT i ) + (-1) n ,where ES(h) is the multiset of sizes of the edges of h.Computing the first terms gives:µ( HT 2 ) = -1, µ( HT 3 ) = 3 × (-µ( HT 2 )) 2 -1 = 2,and µ( HT 4 ) = 13 × (-µ( HT 3 )) + 16 × (-µ( HT 2 )) 3 + 1 = -26 + 16 + 1 = -9.

  3.3.2.Left-sided computation. Applying the Moebius function at the left side of the coproduct, we obtain:µ * ζ( h n ) = 0,for all n ≥ 2. By Proposition 3.2, this can be rewritten for all n ≥ 2 as:0 = µ(h (1) n ) ζ(h (2) n ) -µ(h n ).The formula (3.1) for the coproduct gives:µ( HT n ) = -(α,π)∈Pn c n α,π (-1) (i-1)αi (i -1)! αiUsing Theorem 3.19 and Theorem 3.14, we obtain the following proposition: Proposition 3.20. The following equality holds:(n -1) n-2 = (α,π)∈P(n) (-1) iαi-1 n × n! j≥2 (j -1)! πj π j ! × k! × n! i≥1 α i !, where P(n) is the set of pairs of tuples (α = (α 1 , . . . , α k ), π = (π 2 , . . . , π l )) satisfying:

  Example 3.21. The first terms obtained are: µ( HT 4 ) = -1 + 12 -12 -8 = -9 and µ( HT 5 ) = -1 + 20 + 12 -120 -60 + 60 + 120 + 30 = 64.

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 e-mail address: oger@math. univ-lyon1. fr. 1