Mario Macias
email: mario.macias@bsc.es

Jordi Guitart
email: jordi.guitart@bsc.es

A Risk-based Model for Service Level Agreement Differentiation in Cloud Market Providers

Cloud providers may not always fulfil the Service Level Agreements with the clients because of outages in the data centre or inaccurate resource provisioning. Minimizing the Probability of Failure of the tasks that are allocated within a Cloud Infrastructure can be economically infeasible because overprovisioning resources increases the cost and is economically inefficient. This paper intends to increase the fulfilment rate of Service Level Agreements at the infrastructure provider side while maximizing the economic efficiency, by considering risk in the decision process. We introduce a risk model based on graph analysis for risk propagation, and we model it economically to provide three levels of risk to the clients: moderate risk, low risk, and very low risk. The client may decide the risk of the service and proportionally pay: the lower the risk the higher the price.

Introduction

Cloud Computing arisen as a successful commercial solution to sell computing resources as a utility: clients dynamically size the resources according to their workloads, and pay only for what they use. Cloud resources are usually sold as Virtual Machines (VMs) that can run isolated in the same hardware as other VMs and scale at runtime. In current commercial Clouds, infrastructure providers price the resources and clients may decide to buy them or not. There is no negotiation. Our research, however, is framed in research Cloud Market implementations such as the SORMA [START_REF] Neumann | SORMA -building an open grid market for grid resource allocation[END_REF] Market Middleware. In Cloud Markets, both resource users and providers are autonomous agents that negotiate the terms of the Quality of Service (QoS) and the price that the client will pay to the provider. When the negotiation is finished, the terms of the contract are established in a Service Level Agreement (SLA) that keeps contractual information about the terms of the QoS as well as the pricing information (price and penalty to pay in case of violation of the SLA).

Cloud providers may not always fulfil the SLAs they agree with the clients because of outages in the data centre or errors in the hardware. Not fulfilling the agreed SLAs would lead to economic penalties [START_REF] Macias | Client classification policies for SLA enforcement in shared cloud datacenters[END_REF] and a loss of reputation that can cause clients with high reliability requirements to not allocate their tasks in the provider [START_REF] Macias | Client classification policies for SLA negotiation and allocation in shared cloud datacenters[END_REF]. Minimising the Probability of Failure (PoF) of the tasks that are allocated within a Cloud Infrastructure can be economically infeasible. Overprovisioning resources increases the cost and is economically and ecologically inefficient because the overbooked resources are underused most of the time.

This paper has a main goal: to increase the fulfilment rate of SLAs at the infrastructure provider side by providing risk-aware policies that maximize the economic efficiency. We introduce a risk model based on graph analysis for risk propagation, and we model it economically to provide three levels of risk to the clients: moderate risk, low risk, and very low risk. The client may decide the risk of the service and proportionally pay: the lower the risk the higher the price.

To achieve the stated goal, this paper introduces the following contributions:

1. Model of the PoF of a multi-tier service that is hosted in a Cloud data centre by means of the analysis of the links between virtual resources. 2. A new revenue model that will help providing different levels of risk at different prices, while adapting prices to the present value of the resources (that is, the rate the resources decrease their value over time).

This paper is structured as follows. After the related work section, Section 3 introduces the baseline negotiation and revenue model that is used as framework for this paper; Section 4 shows the risk model and Section 5 shows the revenue model; Section 6 describes the experiments and evaluates their results; at the end, Section 7 show the conclusions and the future work lines.

Related work

This paper extends our previous work [START_REF] Macias | Client classification policies for SLA negotiation and allocation in shared cloud datacenters[END_REF][START_REF] Macias | Client classification policies for SLA enforcement in shared cloud datacenters[END_REF], which demonstrated that differentiating SLAs according to their QoS level could lead to economic benefits in an open market with many competitors, because there is a variety in the objectives of clients. Some clients may require high QoS guarantees and other clients may prioritize lower prices. This paper extends the previous research by modelling the risk of complex cloud appliances and defining a revenue model that would allow to provide accurate prices as a function of the offered QoS level.

Bayesian networks [START_REF] Jensen | An introduction to Bayesian networks[END_REF] define a graph model for describing the probability of an event from the probabilities of the events that would cause it, in terms like "if event A happen, event B will happen". That is inaccurate for Cloud appliances, because a failure in a node would not always involve a failure in the linked node. In addition, it is difficult to express some complex relations like redundancy. Our graph model extends the Bayesian Network model with the addition of weighted links and introduces two special types of node for representing union and intersection operations. These additions ease the expression of some complex Cloud appliances and the risk propagation through their nodes.

Djemame et al. [START_REF] Djemame | Brokering of risk-aware service level agreements in grids[END_REF] described an architecture to assess risk in computing Grids that allow providers to estimate the risk of agreeing a given SLA and use management techniques to maximize its fulfilment. They use risk assessment for task scheduling. Our work intends to be an upgrade of some of their risk models to adapt them to the architecture of Clouds and using such risk assessment also for improving business objectives.

Yeo and Buyya [START_REF] Yeo | Integrated Risk Analysis for a Commercial Computing Service in Utility Computing[END_REF] provide two methods for risk analysis: separate, which only evaluates the risk over a facet, and integrated, which evaluates the risk over multiple facets. In the integrated method, they assume all the facets are independent from each other. In our model, the facets are the multiple risks of all the independent resources in a multi-tier application, but we do not consider them as independent. The risk is propagated according how such resources are linked, and the effects of such uncertainty have different impact depending on the location of the risk within the resources graph.

Sawade et al. [START_REF] Sawade | Active risk estimation[END_REF] consider that risk models may lose their validity over time for some reason (the environment changes, the inputs change, learning errors, ...). Our model can minimize these drawbacks, because it is dynamically built according to the SLA templates from the clients.

The pricing models from Becker et al. [START_REF] Becker | Using k-pricing for penalty calculation in grid market[END_REF] consider the concept of Business Value: how much a client is willing to pay for any extra unity of QoS. We also consider this concept in our model. However, our intention is not to solve the issue of calculating it but consider it as an important part of a revenue model for providing multiple pricing and risk levels. They also calculate the penalty of the execution of multiple services, while distributing the risk between the different services. Our approach considers only a single project and calculates the risk of penalties by evaluating the internal topology of such service.

Simao et al. [START_REF] Simao | Flexible slas in the cloud with a partial utility-driven scheduling architecture[END_REF] propose a pricing model that allows clients and providers to negotiate the price and penalties, but also how much service degradation the client is willing to accept and how much it will pay proportionally to such degradation. As in this paper, they define three levels of QoS and propose a depreciation strategy to control the degradation of the SLAs for each profile when the resources are overloaded. Our model does not explicitly select the SLAs to degrade, but allocates them by risk levels according to the envisioned probability of failure. Both models are complementary and may coexist simultaneously.

Wee [START_REF] Wee | Debunking real-time pricing in cloud computing[END_REF] profiles in detail the Amazon Spot Instances. He concludes that such model does not motivate enough users to move their workload to the off-peak hours. Our model provides an extra incentive to move because, in addition to the lower prices derived from the low market demand, users can benefit also of lower risks derived from the low workload.

Li and Gillam [START_REF] Li | Risk informed computer economics[END_REF] apply risk assessment to the financial aspect of the grid. They provide node granularity risk assessment to calculate prices and penalties for the SLAs. Our approach combines assessments from several nodes and links them to consider a Cloud appliance topology.

SLA negotiation model

This paper focuses two stages of the Infrastructure as a Service (IaaS) provisioning: the negotiation of SLAs between the clients and an Infrastructure Provider (IP), and the provisioning of resources to fulfil the terms of the agreement. We consider the OCCI Standard [START_REF] Metsch | Open Cloud Computing Interface -Infrastructure[END_REF] to describe the infrastructure: the client can get three types of cloud resources (compute nodes, networks, and storage nodes) and define how they are linked by means of network interfaces and storage links.

When a client wants to host a service, it calculates how many Cloud resources it needs and sends an offer to the IP to start a negotiation. Each IP owns a set of N physical hosts. Each physical machine can host several VMs. The SLA of a set of VMs is described as

SLA = { - → S , - → L , ∆t, RL, Rev(vt)}.
-→ S = (s 1 , . . . , s k ) are the Service Level Objectives (SLOs) that describe the amount of resources to be purchased by the client, and -→ L describes how the resources are linked according to its OCCI description. Each s * term represents the amount of CPUs, Memory, Disk, network bandwidth, and so on. RL is the risk level (medium, low, very low) that the client selects for its service, having an impact in the price. ∆t is the time period during which the VM will be allocated. If the IP provider has not enough free resources to allocate the SLA, it can reject it.

Current commercial Clouds do not compel to specify ∆t and sell resources at fixed price/hour. In contrast, research Cloud Market middlewares [START_REF] Neumann | SORMA -building an open grid market for grid resource allocation[END_REF] require to specify ∆t when a client and a provider negotiate a price. Market mechanisms would motivate clients to distribute their workloads across time, if possible.

Rev(vt), which was originally proposed in [START_REF] Macias | Client classification policies for SLA negotiation and allocation in shared cloud datacenters[END_REF], is a revenue function that describes the revenue of a provider after the operation of a SLA. The violation time vt is the total time during which the agreed QoS has not been provided. Let M P be the Maximum Penalty (seen as negative revenue), M R the Maximum Revenue, M P T the Maximum Penalty Threshold, and M RT the Maximum Revenue Threshold, Equation 1 describes the revenue function.

Rev(vt) = M P -M R M P T -M RT (vt -M RT ) + M R (1)
Equation 1 allows a grace period where the provider can violate the SLA without being penalized. If vt ≤ M RT , the provider will get all the negotiated revenue (M R); if vt ≥ M P T , the provider will pay the maximum penalty (M P ); for M RT > vt > M P T the money to earn or the penalty to pay will be proportionally in between M R and M P as a function of vt (see Figure 1) . The Maximum Penalty M P is defined to avoid infinite penalties. Client and provider can negotiate the values of M RT , M R, M P T , M P for establishing different QoS ranges that would report different revenues and penalties. The client can assume that vt will be normally near zero and will have to pay M R most times.

When the client wants to acquire resources from the IP, it starts the next negotiation: it sends to the IP an SLA template with values for ( -→ S , -→ L , ∆t, RL). According to its envisioned status for ∆t, if the IP has enough resources, it returns a complete SLA that specifies the values for M RT , M R, M P T and M P as a function of the number of resources, the market status, and the risk level requested by the client. A lower risk level would entail higher prices (M R), but higher penalties (lower M P and less tolerance to SLA violations (lower M RT Fig. 1: Revenue of a SLA as a function of the violation time (Equation 1) and M P T )). If the client agrees the terms proposed by the IP, it confirms the SLA or, otherwise, rejects it and looks for another provider in the market.

Risk Management

This paper considers risk as the effect of uncertainty on objectives [START_REF] Guitart | Risk-driven proactive fault-tolerant operation of iaas providers[END_REF]. Risk depends on two facets: the probability of an unwanted event and how it deviates the desired outcomes. Given a time frame, an unwanted event may occur. This may impact or not in the desired outcomes. For example, if a single disk fails within a storage system with redundancy, an unwanted event occurred but its impact is low (cost of replacement, but no data has been loss). In our work, the impact of risk will be economically determined by the penalties that are specified in the SLA. Calculating the risk is calculating the PoF of a complex system, and calculating how the failure can impact the fulfilment of the SLA.

Measuring risk in individual components. For each component based on OCCI types, we identify as failure each incident that causes this component to not work correctly. Although real computing resources may have multiple degrees of malfunction, our model adopts a binary definition of malfunction for single resources: working/failure. Our model does not care about the grade of performance for each individual component, but whether the propagation and aggregation of all the errors/misbehaviours of the individual resources will lead the system to fulfil the SLA or not.

The quantitative risk assessment for each component is based on the process proposed by Guitart et al. [START_REF] Guitart | Risk-driven proactive fault-tolerant operation of iaas providers[END_REF], which divides the risk assessment into the following stages: [START_REF] Becker | Using k-pricing for penalty calculation in grid market[END_REF] Identify what weaknesses could prevent a component from functioning properly. In this paper we identify two: overload of resources and age of resources.

(2) Identify which situations can exploit system vulnerabilities. Information from vulnerabilities and threats can be gathered from experts, historical databases and files. (3) The monitoring information is retrieved at different levels. We basically consider information from physical and virtual hosts. (4) Identify the likelihood of a threat acting over a vulnerability. This information is retrieved from historical facts that take place in a specific context. And (5) calculate the PoF of a single component as a function of the current monitoring status, given a time frame (e.g. calculate the PoF of a network during the next 24 hours). In this paper, we use statistical information from monitoring history (e.g. check the historic of failures when resources reach a given load). In our future work, we will explore alternative methods: machine learning, non-linear regressions, etc.

Measuring risk in complex appliances. In compliance to OCCI, our risk model is composed by nodes that have dependencies between them. A node n x is failing when it is not providing the agreed QoS (e.g. a disk is not able to read or write data, a compute resource is not providing all the promised computation power, a network fails...). The PoF of n x is notated as P (n x ) and it can be measured according to the steps as previously described.

Let n x and n y be two nodes that are linked to work together as a composite system. We consider that n x has a risk link of weight ω xy to n y when the failure of n y prevents n x to work correctly (for example, n x is an application server that uses n y as a database). The weight ω xy ∈ [0, 1] is the probability that a failure in n y is propagated to n x . In consequence, n x can fail because an internal failure on n x or a failure in n y that is propagated to n x with probability ω xy . Equation 2defines P (n x ) as the propagated probability of failure of n x .

P (n x ) = P (n x ) + ω xy P (n y ) -ω xy P (n x )P (n y ) (2)
Equation 2 is based on the formula for union of probabilities, which assumes that P (n x ) and P (n y ) are independent (unlike P (n x ) that depends on both P (n x ) and P (n y )). The graphical notation for such risk relation is the next:

n x n y ω xy
The aforementioned notation is used as a primitive for calculating the risk of complex systems. For example, let ws be a web server that handles requests from clients and contacts the application server as. We measured that the 30% of the times that as is invoked it accesses a database (db). If the database fails, the error will be propagated to as and, in consequence, to ws. In this example we assume P (ws) = 0.05, P (as) = 0.01, and P (db) = 0.03. ws as db 0.3 If the arrow between nodes does not show any number, we assume a weight value = 1 between risk nodes. From the client side, if the node ws fails, the complete web application is failing. The PoF of the complete super system is P (ws), which is calculated as shown in equation 3. Resolving it, the probability that the complete system fails (that is, the client cannot access ws) is ∼ 0.068. It is always true that P (n x ) ≥ P (n x ). P (ws) = P (ws) + P (as) -P (ws)P (as) P (as) = P (as) + 0.3P (db) -0.3P (as)P (db)

(3)

In the previous example, the probability of failure of node as that will be propagated to ws is actually the probability of failure of the subsystem formed by as and db. By this reason, Equation 3 calculates P (ws) as a function of P (as) instead of P (as). Our model allows simplifying complex systems by grouping many of their nodes and treats them as a single node.

In our model, a node can also have risk dependencies to many other nodes. We introduce two types of meta nodes to represent unions and intersections between risk probabilities. The next system is interpreted as follows: the system headed by n x will fail when there is a failure in n x OR there is a failure in n y (with probability w xy ) OR there is a failure in n z (with probability w xz ).

n x n y n z ∪ ω xy ω xz
The node labelled as '∪' (union operator) is a meta node to which P (∪) = 0. It is used to allow grouping the subsystem formed by n y and n z and treating it as a single node when calculating the risk propagation to n x (calculated in P (∪)). In consequence, calculating P (n x ) is solving the next equations:

P (n x ) = P (n x ) + P (∪) -P (n x )P (∪) P (∪) = ω xy P (n y ) + ω xz P (n z ) -ω xy P (n y )ω xz P (n z ) (4)
As example, imagine n x is a VM that executes a disk-intensive task against a RAID-0 disk system which distributes the data chunks within two disks (n y and n z ) for improving performance. If only one disk fails in a RAID-0 system, the complete system will fail, since there is no redundancy for recovering the data.

Our model also introduces the intersection operator '∩' to model redundancy in fault tolerant systems:

n x n y n z ∩ ω xy ω xz
The probability of failure of the subsystem headed by the node '∩' is the intersection of probabilities of failure for nodes n y and n z , assuming that they are independent: P (∩) = ω xy ω xz P (n y )P (n z ). For example, imagine a RAID-1 disk system that mirrors two disks.

The combination of the union and intersection operators may also be used to model systems to which the redundancy is partial. For example, a master node M sends tasks to slave nodes A, B, and C. If one of the slave nodes fails, the other two nodes can handle the work; if two slave nodes fail, the complete system will fail.

Although we focus on the hardware failures at infrastructure level, our model allows also expressing software components as nodes within the graph, or simply considering the software failure within the PoF in the hardware node.

Risk-aware cloud operation. Risk must be considered during the allocation and operation of cloud appliances. For example, a client that needs high availability would negotiate SLAs with a high penalty for the provider in case of SLA violation. In such scenario, the Cloud provider has to minimise the PoF of the application according to two complementary strategies:

-For each node n x , minimizing P (n x ), which is caused by risk in the node (not propagated). This paper considers two factors that influence in P (n x ): hardware lifetime and workload [START_REF] Schroeder | A large-scale study of failures in high-performance computing systems[END_REF]. The failure rate of hardware resources is high both at the beginning and the end of the components lifetime. There is also direct correlation between the workload and the failure rate, being higher during peak hours and lower during off-peak hours. We use statistical analysis based on historical data to calculate P (n x ). -Consider decreasing P (n x ) for each node n x . Analysing risk graphs and providing redundancy in the critical points of the graph would noticeably reduce the risks of the system with reasonable economical performance.

Analysing the risk propagation graphs is itself a large research field that would require to deep within the research of machine learning and pattern recognition algorithms, and how to apply them to this problem. The aim of this paper is to keep the focus in the risk and revenue model. We simplify the graph analysis by experimenting only with one template of application. The graph analysis has been done off line and the risk minimization policies always apply the same action with the graph: to add redundancy to the nodes whose failures would entail a failure to the rest of the application.

Both strategies for minimizing risk would entail an increment in the cost of operation. Next section describes a model for the management of the revenue during both SLA negotiation and operation that would allow providers providing differentiated risk levels consistently according to its business objectives.

Revenue Modelling

This paper uses Equation 5to establish the price of a set of Cloud resources, given a time frame. M R is the price for a service (Maximum Revenue, as previously defined in Equation 1).

M R = RP + DO + BV (5)
In Equation 5, RP is the Reservation Price: the minimum price the provider can sell a resource without losing money. DO and BV are subjective terms that may depend on several conditions. DO is the demand/offer overprice: a client may be willing to pay more when there is more demand than offer. DO will tend to 0 when the demand is much lower than the offer. BV is the Business Value: the amount of money a client is willing to pay for an extra unit of QoS.

Our model calculates RP as the cost of amortization of all the resources that the client will use during a given period: the more amortized is a resource the lower is RP . Equation 6shows how to calculate the amortization cost of a single Cloud resource that is allocated within a physical resource. The RP for a cloud appliance is the addition of the amortization costs for all its resources.

Cost Am = (T CO -Amort) ∆t (LT total -LT now )H ρ ( 6
)
T CO is the Total Cost of Ownership, the cost of the initial investment plus the common expenses in electricity and maintenance during the whole lifetime of a resource. Amort is the sum of all the income associated to the provisioning of virtual resources for the given physical resource. ∆t is the time that the client is willing to use the resource. LT total is the Life Time that is planned for a group of resources: the time since it is provisioned until it is disengaged from the data centre. LT now is the Life Time since a resource is provisioned until now. Finally ρ = [0, 1] is a density function that indicates the proportion of a group of resources to which the cost is being calculated. For example, if a VM requires 4 CPUs from a node with 16 CPUs, ρ = 0.25. Finally, H is the percentage of usage of the resources as envisioned by the provider to this time. If H = 1, the provider would consider that all the resources that are assigned to a VM are at full occupation during this time. If the resources are underutilized, the value H would proportionally increase the reservation price that is needed for actually amortizing completely a resource at the end of its lifetime.

To avoid inequalities in the amortization of individual resources with the same age, we group all resources from the same type and age into an accounting group. Then the values T CO, Amort, ρ and LT apply to the total of resources instead of individual ones. Equation 6 differs from the traditional way to calculate the amortization cost, T CO/LT total , because this formula assumes full load and does not consider how the value of a resource decreases over time.

To calculate DO overprice, our previous work [START_REF] Macias | Client classification policies for SLA negotiation and allocation in shared cloud datacenters[END_REF] demonstrated that the DO must be low when the offer/demand ratio is high enough to allow users to choose from a big enough set of providers, and high only in peak hours, when most resources are busy.

Calculating BV is difficult because it may rely on several hidden variables that depend on the client, the market status, the reputation of the provider, etc. Instead of trying to synthesize them in a mathematical formula, Machine Learning techniques can allow providers estimating this value. However, those techniques are out of the scope of this paper. We apply a fixed overprice for the SLAs in our experiments, according to their level of QoS and Risk.

We account DO and BV within the total of amortized cost, which are overprices that accelerate the amortization of the resource and cause Cost Am value to decrease over time. That will allow the provider using different prices depending on the age of the resources that are being sold.

In our experiments, we used a Cloud Market simulator (available online [START_REF]Risk-aware cloud market simulator[END_REF]) that adopts the simulation architecture and methodology from our previous works [START_REF] Macias | Client classification policies for SLA negotiation and allocation in shared cloud datacenters[END_REF][START_REF] Macias | Client classification policies for SLA enforcement in shared cloud datacenters[END_REF]. We simulate 36 months of a IaaS provider that initially owns 50 hosts with 16 CPUs each one. The number of deployed services initially oscillates between 5 and 60 services/hour, according to a web workload that varies as a function of the hour of the day and the day of the week. To simulate the consolidation of the business of the provider, the average number of requests is linearly increased until it doubles its initial number at the end of the simulation. Because of the increase of the number of requests, the Cloud provider doubles its number of resources at month 18. From the point of view of Equation 6, there is initially an accounting group of resources and at the end of the simulation there are two accounting groups: the initial bunch of resources, and the new resources that were introduced at month 18. The clients can deploy several types of applications. In our experiments, the clients deploy web services according to the structure in Figure 2: a web frontend (f e) balances the job across a set of n application servers (as 1 , . . . , as n ) that use a database node (db) as persistence layer. The number of application servers varies from 2 to 4. The number of CPUs of each node follows a folded normal distribution [START_REF] Leone | The folded normal distribution[END_REF] with both minimum value and variance equal to 1. The same distribution is used to determine the duration of the deployments, with minimum value and variance of 1 hour.

The allocation process of the SLA is the same as described in Section 3. The IP considers three different SLA allocation strategies, which offer three levels of risk for the SLA, from medium to lowest risk:

-Cost Minimization (CMin). The provider prioritizes the allocation of VMs in the hosts given two equally-weighted criteria: high consolidation, to save energy costs in hosts that are already running tasks and keep switched off those hosts that are idle [START_REF] Guitart | Risk-driven proactive fault-tolerant operation of iaas providers[END_REF]; and amortization, to allow lower prices according to the model in Equations 5 and 6. Because of high consolidation and resources age, SLAs allocated according this policy have the higher risk.

-Node Risk Minimization (NRMin). The provider prioritizes the allocation of VMs in the hosts according to two equally-weighted criteria: low consolidation, to lower the risks derived from overload in resources that would entail to not provide the agreed QoS; and resource age, trying to avoid the resources that are new and those resources that are near the end of their lifetime [START_REF] Schroeder | A large-scale study of failures in high-performance computing systems[END_REF]. Figure 3 shows the used distribution of failures as a function of the age of the resource. -Graph Risk Minimization (GRMin). The provider applies Node Risk minimization but, in addition, it analyses the OCCI links to try to detect single point of failures. Given the model in Section 4, the provider would detect that a failure in the database node would entail a failure in the whole application, so it decides to replicate it. The client selects the type of risk minimization strategy as a function of the risk needs of its application. When the IP calculates the price, it applies a fixed overprice of 50% to the NRMin SLAs and 100% to the GRMin SLAs. In addition to the overprice, that determines the M R value of Equation 1, the risk level also determines M P , M P T and M RT . Lower values for M P , M P T and M RT imply that there is less tolerance to failures for low-risk SLAs (see Table 1), because vt will reach M RT sooner (see Figure 1). These fixed values, as well as the other constants that the simulation relies on, are not intended to reflect real market data but to evaluate the model in terms of relative results and tendencies.

Evaluating risk minimization policies. The graphics of this section show weekly average values to make them more clear and understandable, because hourly or daily averages are highly influenced by the workload oscillations. The weekly granularity for the values is also accurate enough because the simulation is long-term enough (36 months) to show clearly the tendencies of the metrics used to evaluate the effectiveness of the policies. Figure 4a shows the behaviour of the policies with respect to the age of the selected resources. In the first half of the experiment all the resources are the same age. When a new bunch of resources is introduced at month 18 (week 77), the CMin policy still selects the older resources, which have the highest amortization rates. NRMin and GRMin progressively move their workloads to the new resources, after a short period in which new resources have higher risks than older resources (as shown in Figure 3). As explained before, the number of requests linearly increases over time. Around week 115 resources are highly loaded because of the high number of requests, and the provider has less possibility to choose resources for the different risk levels. This will influence the risk of the SLAs, as shown in Figures 4b and4c.

Figure 4b shows the weekly average PoF of the SLAs, differentiated by the three different allocation policies (CMin, NRMin and GRMin). While CMin is near to constant over time, NRMin keeps much lower risk than CMin while is noticeably influenced by the load of the resources. The PoF for NRMin SLAs increases linearly over time as the number of application executions also increases because the possibility to choose is reduced. When the number of resources is doubled, the PoF of NRMin is reduced again, while the PoF of CMin is kept constant, because the policy still chooses the older resources. GRMin SLAs are also sensible to the load of resources because the allocation policy is the same as NRMin, but the elimination of the single point of failure causes the system keeping much lower risk rates.

The PoF has a direct impact in the economic penalties as consequence of the violations of the SLAs. Figure 4c shows the strict correlation of the economic penalties with the probability of failure. The economic impact of failures is higher in SLAs allocated with low-risk policies (NRMin and GRMin), because both the prices and the penalties are higher for these SLAs (see Table 1). Figure 4c, as well as the rest of figures with economic information in our evaluation, does not show absolute economic values, but values divided by CPU hours to facilitate the comparison of data from appliances with different size and different time. Evaluating the modelling of the revenue. Figure 5a shows the average price per CPU hour for the different types of SLAs. During the initial part of the experiment, the price decreases because the resources are being amortized which, applying the pricing model of Equation 5, reduces RP . Figure 5b shows that during this period the profit (the revenue minus the reservation price minus the penalties) for CMin policy can be improved because the market allows higher profit margin: RP decreases but DO and BV may increase in a lower proportion to decrease prices while increasing the profit margin. On the other side, profit for risk minimization policies keeps near constant during this period (despite the price reduction) because the business value (BV ) of low-risk SLAs is higher (the users are willing to pay more for this extra QoS). In consequence, the provider has more room to increase its margin profit with risk minimization policies.

Figure 5a shows that, when the resources are doubled at the half of the experiment, prices increase for risk minimization policies because they tend to allocate tasks in newer resources with a lower amortization rate than older resources. CMin policy keeps constant prices because this policy still allocates the services in the older resources.

Although the penalty rate increases for minimization policies in the first half of the experiment (from week 1 to week 77), as shown in Figure 4c, the impact of penalties in the net profit is proportionally low because of the different scaling of Figures 5b and4c. For this reason, the profit of NRMin and GRMin policies slightly decreases over time. However, when new resources are added, the incurred price increment and the reduction of SLA penalties have some positive impact in the net profit. The influence of penalties in CMin SLAs remains quite stable during the whole simulation.

Conclusions and future work

This paper introduces a model to differentiate SLAs as a function of multiple risk levels and adapt the provisioning of resources to multiple client profiles in a Cloud Market. We introduce three policies for each differentiated risk profile that we present in the paper: cost minimization, risk minimization at individual node level, and risk minimization at graph level. In addition, we introduce an accounting model that allows the provider adjusting prices to the risk as a function of the amortization of the resources. Our model also helps adapting prices at the long-term, allowing the provider to estimate how the price of the resources decays over time.

The risk propagation model will be improved in the future with bidirectional dependencies and allowing cyclic graphs. The node-level risk analysis will also be improved by exploring alternative methods to the statistical analysis: machine learning, non-linear regressions, etc.

The other main line for future research is related to the automated analysis of graphs. New pattern recognition techniques must be introduced to allow the provider to automatically identify critical points of failure and suggest corrective actions that would minimize the risk only in the required points of the graph to avoid soaring the costs due to the excess of redundancy.

Regarding revenue modelling, we will work on techniques to discover the Business Value of resources. In other words, it is important that the provider estimates accurately how clients are willing to pay the additional QoS to maximize the profit of the provider without losing clients.

Fig. 2 :

 2 Fig. 2: Basic architecture of a web application

Fig. 3 :

 3 Fig. 3: Probability of Failure of resources over time

Fig. 4 :

 4 Fig. 4: Evaluation of risk metrics for different SLA policies

  Fig.5

Table 1 :

 1 Revenue function values for each group of SLAs

Acknowledgement

This work is supported by the Ministry of Science and Technology of Spain and the European Union (FEDER funds) under contract TIN2012-34557 and by the Generalitat de Catalunya under contract 2009-SGR-980.


A NATURAL GENERALIZATION OF BALANCED TABLEAUX

We introduce the notion of "type" of a tableau, that allows us to define new families of tableaux including both balanced and standard Young tableaux. We use these new objects to describe the set of reduced decompositions of any permutation. We then generalize the work of Fomin et al. by giving, among other things, a new proof of the fact that balanced and standard tableaux are equinumerous, and by exhibiting many new families of tableaux having similar combinatorial properties to those of balanced tableaux.

Introduction

Since the fundamental paper of Stanley [START_REF] Stanley | On the number of reduced decompositions of elements of Coxeter groups[END_REF], it is well-known that standard Young tableaux interact with the weak order, providing and important tool to enumerate the reduced expressions of any permutation (see also [START_REF] Edelman | Balanced tableaux[END_REF][START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF][START_REF] Lascoux | Schubert polynomials and the Littlewood-Richardson rule[END_REF][START_REF] Little | Combinatorial aspects of the Lascoux-Sch à 1 4 tzenberger tree[END_REF]). Another important family of tableaux called balanced tableaux has been defined in [START_REF] Edelman | Balanced tableaux[END_REF] by Edelman and Greene to study this enumerative problem. The surprising feature of balanced tableaux is that they are equinumerous with standard tableaux of the same shape λ. This was showed in the original paper [START_REF] Edelman | Balanced tableaux[END_REF] with a quite involved proof. The notion of balanced tableaux was further generalized in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF], with the introduction of the set of balanced tableaux of shape D(σ), where D(σ) denotes the Rothe diagram of the permutation σ. By using this new family, the authors gave in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF] a new interpretation of the set of reduced expressions of any permutation, and derived from this a new and more accessible proof of the fact that balanced and standard tableaux are equinumerous.

In this article, we give a wide generalization of the previous result using the results from [START_REF] Viard | A new family of posets generalizing the weak order on some Coxeter groups[END_REF]. Namely, we give a new interpretation of the set of reduced expressions of a permutation from which we define many families of tableaux having similar combinatorial properties as those of balanced tableaux. As a corollary of our method, we provide an alternative proof that balanced and standard tableaux are equinumerous.

In order to do so, we deal with a bigger class of tableaux which are not required to be standard or balanced. To each tableau T of shape S, where S is any finite subset of N × N, we associate a combinatorial object T called the type of T . This allows us to split the set of tableaux of shape S into different classes: two tableaux being in the same class if and only if they have same type. Let us denote by Tab(T ) the set of all the tableaux having type T . In particular, both sets of standard and balanced tableaux are special instances of this classification. We also provide an algorithmic process allowing us to construct all tableaux having a given type, and in particular this allows us to easily obtain all balanced tableaux of a given shape.

In Section 4.1, we associate each permutation σ ∈ S n with a type T σ such that we have a one-to-one correspondence between Tab(T σ ) and Red(σ), where Red(σ) is the set of reduced expressions of σ. This gives a new combinatorial interpretation of reduced expressions of any permutation (not fundamentally different from the one given in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF], but maybe more natural with respect to the results in [START_REF] Viard | A new family of posets generalizing the weak order on some Coxeter groups[END_REF]). Then, we focus on the case of vexillary permutations, namely permutation being 2143-avoiding, which are one of the main objects studied in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF]. It is well-known [START_REF] Stanley | On the number of reduced decompositions of elements of Coxeter groups[END_REF] that each vexillary permutation σ is associated with a partition λ(σ) such that |Red(σ)| equals the number of standard tableau of shape λ(σ). We then introduce a transformation on types called the exchange algorithm (see Section 4.3), and we use it to prove the following theorem.

Theorem 4.14. Let σ ∈ S n be a vexillary permutation and T E σ be the type obtained by performing the exchange algorithm on T σ . Then, |Tab(T E σ )| equals the number of balanced tableaux of shape λ(σ), and each element of Tab(T E σ ) is of shape λ(σ).

This result provides a generalization of Edelman and Greene result. Indeed, we have the following two facts:

• from Theorem 4.14 can be deduced that balanced and standard tableaux are equinumerous (see Section 4.5); • for any vexillary permutations σ ∈ S n and ω ∈ S m , we have T E σ = T E ω if and only if σ can be obtained from ω by adding or deleting some fix points at its end and beginning (see Section 4.6). We finish our study with exhibiting some combinatorial properties of the types T E σ (see Section 5). We explain how a new combinatorial description of Schur functions arise from them, and we enumerate the elements of Tab(T E σ ) such that the integers 1, . . . , k appear in given fixed positions. This last proposition provides a direct proof of [START_REF] Edelman | Balanced tableaux[END_REF]Equation (2.4)] as asked by Edelman and Greene.

Definitions, notations and background

In this section, we recall some basic definitions and background about standard and balanced tableaux.

A partition λ of a nonnegative integer n ∈ N is a nonincreasing sequence of nonnegative integers

λ 1 ≥ λ 2 ≥ • • • such that λ i = n.
The integers λ i = 0 are called parts of the partition λ. The Ferrers diagram of λ is a finite collection of boxes, or cells, arranged in left-justified rows of lengths given by the parts of λ. By flipping this diagram over its main diagonal, we obtain the diagram of the conjugate partition of λ, denoted by λ . We usually identify a partition with its Ferrers diagram.

More generally, in this article we work with diagrams of arbitrary shape, namely finite subsets of N × N, without any constrain: let S ⊂ N × N such that |S| = n (where |S| denote the cardinal of S). We identify S with a set of boxes in the plan, using the English convention for the coordinates of each box (i.e. we use "matrix-like coordinates"). A tableau T of shape S is a bijective filling of S (seen as a set of boxes) with entries in [n] := {1, 2, . . . , n}. Given a tableau we denote its shape by Sh(T ). If we require Sh(T ) to be a partition λ, then T will be what is usually called a Young tableau. Moreover, if we consider Young tableaux satisfying the conditions that the filling is (1) increasing from left to right across each row;

(2) increasing down each column; we obtain the set of standard Young tableaux of shape λ, denoted by SYT(λ). Definition 2.1. Let S be a diagram and c = (a, b) be a box of S. We define the following sets,

L S (a, b) = {(k, b) | k ≥ a, (k, b) ∈ S}, A S (a, b) = {(a, k) | k > b, (a, k) ∈ S}, (1) H S (a, b) = A S (a, b) L S (a, b), (2)
respectively called the leg, the arm, and the hook based on (a, b). We will denote by l S (a, b), a S (a, b), and h S (a, b) their respective cardinalities.

This notion of hook allows us to enumerate standard Young tableaux, thanks to the well-known hook-length formula (see [START_REF] Stanley | Enumerative combinatorics[END_REF] for more details about this formula).

Theorem 2.2. Let λ be a partition of the integer n, seen as a diagram. Then, we have

|SYT(λ)| = n! (a,b)∈λ h λ (a, b)
.

In [START_REF] Edelman | Balanced tableaux[END_REF], Edelman and Greene introduced the concept of balanced tableaux, defined as follows. We denote by Bal(S) the set of all balanced tableaux of shape S.

In [START_REF] Edelman | Balanced tableaux[END_REF] the authors proved the following result about combinatorics of balanced tableaux.

Theorem 2.4 ([3], Theorem 2.2). Let λ be a partition of n. Then, we have

|Bal(λ)| = |SYT(λ)| = f λ .
The original proof is quite involved, and an alternative one is given in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF], which we now detail. In order to do so, we need to introduce the notion of reduced decomposition of a permutation and of vexillary permutation. It is classical that the symmetric group S n is generated by the simple transpositions s i = (i, i + 1), i ∈ [n -1], exchanging the positions of the integers i and i + 1. We denote by (σ) the minimal integer such that σ can be written as a product of (σ) simple transpositions, and we define the reduced decompositions of any σ ∈ S n to be the elements of the set of word on {s 1 , . . . , s n-1 }

Red(σ) := {s i1 • • • s (σ) | s j ∈ S and s i1 • • • s (σ) = σ}.
Reduced decompositions are closely related to a partial order on S n , called the (right) weak order and denoted by ≤ R . The weak order is defined as the transitive and reflexive closure of the covering relations for all σ, ω ∈ S n , σ R ω if and only if there exists i ∈ [n -1] such that σ = ω.s i and (ω) = (σ) + 1. In this context, there is a clear one-to-one correspondence between reduced decompositions of σ and maximal chains from Id to σ in the poset (S n , ≤ R ). There is also an alternative description of this poset in terms of inversion sets. For all σ ∈ S n , we define its inversion set to be

Inv(σ) := {(a, b) | 1 ≤ a < b ≤ n and σ -1 (a) > σ -1 (b)}.
It is classical that for any σ, ω ∈ S n , we have that σ ≤ R ω if and only if Inv(σ) ⊆ Inv(ω) (see, for instance, [START_REF] Bjorner | Combinatorics of Coxeter groups[END_REF]).

We now define vexillary permutations.

Definition 2.5. Let σ ∈ S n , we denote by (d i (σ)) i and (g i (σ)) i the finite sequences defined by

• d i (σ) := |{j > i | σ(j) < σ(i)}|, • g i (σ) := |{j < i | σ(j) > σ(i)}|.
We denote by µ(σ) and λ(σ) the partitions obtained by rearranging in a nonincreasing order the sequences (d i ) i and (g i ) i , respectively. We say that σ is vexillary if and only if λ(σ) = µ (σ).

In [START_REF] Stanley | On the number of reduced decompositions of elements of Coxeter groups[END_REF], Stanley proved the following result using symmetric functions, giving an explicit formula to compute the number of reduced decompositions of any vexillary permutation.

Theorem 2.6 (Stanley, [START_REF] Stanley | On the number of reduced decompositions of elements of Coxeter groups[END_REF]). Let σ ∈ S n , if σ is vexillary then

|Red(σ)| = f λ(σ) .
We are now able to explain the proof of Theorem 2.4 that can be found in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF], which uses Theorem 2.6 as fundamental tool. The first step consists in associating a diagram to each permutation. As it is shown in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF], the balanced tableaux whose shape is the Rothe diagram of a given permutation σ (also called balanced labellings of D(σ)) are intimately related to the reduced decompositions of σ.

Theorem 2.8 ([4], Theorem 2.4). Let σ ∈ S n and D(σ) be its Rothe diagram. Then, there is a bijection between the set of the reduced decompositions of σ and the set of the balanced tableaux of shape D(σ). Thus, a balanced tableau corresponds to an ordering [(a 1 , b 1 ), . . . , (a (σ) , b (σ) )] of the inversions of σ. Furthermore, the authors proved in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF] that {(a 1 , b 1 ), . . . , (a i , b i )} is the inversion set of a permutation σ i ∈ S n for all 1 ≤ i ≤ (σ). Therefore, we have

Id R σ 1 R σ 2 R . . . R σ (σ) = σ,
i.e., a balanced tableau of shape D(σ) corresponds to a maximal chain from Id to σ in the weak order on S n . Thus, it corresponds to a reduced decomposition of σ, and it is proved in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF] that this correspondence is bijective.

Eventually, this correspondence leads to a proof of Theorem 2.4.

Theorem 2.9 ([4], Theorem 3.4). Let λ be a partition of n. Then, there exists a vexillary permutation σ ∈ S k for some k ∈ N such that • λ(σ) = λ;

• the shape of D(σ) is λ (up-to the deletion of some empty columns).

Combining Theorem 2.6 and Theorem 2.9, Theorem 2.4 follows immediately. In the sequel of this article, we will generalize Theorem 2.4 by exhibiting many families of tableaux having similar combinatorial properties as those of balanced tableaux.

Type of a tableau, definition and general properties

In this section, we introduce a natural generalization of balanced tableaux. We then study some of the properties of these generalizations and and mention some of the questions that naturally arise from this concept.

3.1. Definition of types and filling algorithm. In this section, S will denote a diagram without any constraint on its shape. Definition 3.1. A type of shape S is a filling of S with integers (θ(c)) c∈S satisfying the following condition: for all c ∈ S,

0 ≤ θ(c) ≤ h c (S) -1.
We denote by Type(S) the set of all the type being of shape S.

In the following definition, we explain how one can associate a type to each tableau of a given shape.

Definition 3.2. Let T = (t c ) c∈S be a tableau of shape S. The type of T is the type T = (θ(c)) c∈S such that for all c ∈ S, θ(c) = |{d ∈ H S (c) | t d < t c }|.
We denote by Tab S (T ) the set of all tableaux of shape S whose type is T . When there is no ambiguity, we simply denote this set by Tab(T ).

Example 3.3. Both balanced and standard tableaux are special instances of this classification: let B = (a c (S)) c∈S be the type whose each box is filled by its arm length, and St ∈ Type(S) be the type whose each box is filled by the integer 0. By definition, we clearly have that Tab(B) = Bal(S). Moreover, if T ∈ Tab(St), then each integer appearing in T is minimal in its associated hook. Thus, the entries in T are increasing from left to right along each row and decreasing from top to bottom along each column, so that Tab(St) is the set of standard tableaux of shape S. Definition 3.2 provides a way to classify all tableaux according to their type. However, at this stage it is unclear if Tab(T ) is empty or not for any given type T . In what follows, we give a combinatorial way to construct all the elements of Tab(T ), which will implies that Tab(T ) = ∅ for any T ∈ Type(S). We begin with a useful definition. Definition 3.4. Let T = (θ(c)) c∈S ∈ Type(S) and c ∈ S. We say that c is erasable in T if and only if the following two conditions are satisfied:

(1) θ(c) = 0;

(2) for all d ∈ S \ {c} such that c ∈ H S (d), we have θ(d) = 0.

Clearly, if we consider an erasable box c of a type T of shape S, if we suppress the box c and we decrease by one the integer in each box d ∈ S \ {c} such that c ∈ H S (d), then what we obtain is a type of shape S \ {c}. This fact allows us to construct all the elements of Tab(T ), as it is explained after the following technical lemma.

Lemma 3.5. Let T = (θ(c)) ∈ Type(S). Then, there exists a box c which is erasable in T .

Proof. Since S is finite, there exists a box d such that H S (d) = {d}. Thus, we have θ(d) = 0. Let us now construct a sequence (d i ) i≥1 of pairwise distinct boxes of S such that d 1 = d, θ(d j ) = 0 for all j ≥ 1, and d j ∈ H S (d j+1 ), and assume that the length k of this sequence is maximal. By maximality, for all c such that d k ∈ H S (c) we have θ(c) = 0. Consequently, d k is erasable in T , and this concludes the proof. Definition 3.6 (Filling process). Let T ∈ Type(S) and L = [c 1 , . . . , c |S| ] be a sequence of pairwise distinct boxes of S. We say that L is filling sequence of T if and only if there exists a sequence of types (T i ) 1≤i≤|S| such that

• T 1 = T ; • for all 1 ≤ i ≤ |S|, c i is erasable in T i ; • for all 1 ≤ i < |S|, T i+1 is obtained from T i by suppressing c i in T i and decreasing by one the valuation in each box d ∈ S := S \ {c 1 , . . . , c i-1 } such that c i ∈ H S (d). We associate each filling sequence L = [c 1 , . . . , c |S| ] with a tableau T L = (t c ) c of shape S defined by t ci = i for all 1 ≤ i ≤ |S|.
Remark 3.7. Note that the filling process is a special instance of the peeling process introduced in [START_REF] Viard | A new family of posets generalizing the weak order on some Coxeter groups[END_REF].

T = P 0 P 1 P 2 P 3 P 4 P 5 1 1 2 1 2 3 1 3 2 4 2 5 4 3 1 T L Figure 2.
Thanks to the previous proposition and Lemma 3.5, we also have the following result which concludes this section. Proposition 3.10. For all T ∈ Type(S), we have Tab(T ) = ∅.

3.2. Some results about the enumeration of Tab(T ). Now that we have a classification of all the tableaux of a given shape according to their type and a way to construct all tableaux in a given class, the following natural questions arise. Question 3.11.

(1) Is it possible to find a formula to compute |Tab(T )| For any type T ?

(2) At least, can we exhibit some family of types for which the number of corresponding tableaux can be computed?

Even if the general case seems to be quite difficult, we have some basic properties in that direction that we now detail. First, note that if λ = (n) or λ = (1 n ), then for any T ∈ Type(λ) there exists a unique tableau of type T . This is clear, since at each iteration of the filling process there is only one (i, j) ∈ λ which is erasable. This basic fact leads us to our first enumerative proposition, generalizing Lemma 3.2 from [START_REF] Edelman | Balanced tableaux[END_REF]. Proposition 3.12. Let k and p be two integers and T be a type of shape λ = (k, 1 p ). Then, we have

|Tab(T )| = f λ .
Proof. First, note that for any tableau T = (t c ) c∈λ of type T , we have t 1,1 = θ(1, 1) + 1 by definition. Thus, if we set S := λ \ {(1, 1)} (see Figure 3) and T := (G S , θ), then we have

|Tab λ (T )| = |Tab S (T )|.
Moreover, when we perform the filling process on T , the only thing we have to chose at each step is an element in the leg or in the arm of S, and this is independent of the choice of T . This concludes the proof.

In general, finding an explicit formula for the number of tableaux of a given type T seems to be a quite complicated problem (note that an approach similar to that of [START_REF] Greene | A probabilistic proof of a formula for the number of Young Tableaux of a given shape[END_REF][START_REF] Novelli | A direct bijective proof of the hook-length formula[END_REF] has not been tried yet). However, a probabilistic approach might be possible, as suggested by the following result. Proof. Set H S = c∈λ h S (c), it is clear that the number of types of shape S is precisely H S . Then, because of the uniform choice, the probability for a type T to be chosen is exactly 1 H S . Thus, the expected value for |Tab(T )| is

T ∈Type(S) |Tab S (T )| H S ,
and the numerator clearly equals n!. The result follows.

This last proposition leads us to the following natural question.

Question 3.14. Is it possible to find an explicit formula for the variance ?

This last question is open, and it seems that the value of the variance heavily depends on the shape of the considered diagram: for instance, some tests suggest that the variance is maximal when we consider a square shape.

Types and reduced decompositions of permutations

In this section, our objective is twofold: we give a positive answer to Question 3.11 (2), and we provide a wide generalization of Theorem 2.4. More precisely, we explain how to associate each vexillary permutation σ with a type T E σ of shape λ σ (we will explain in Section 4.3 what the index "E" stands for) such that:

• |Tab(T E σ )| = f λ(σ) ; • the map σ → T E
σ is injective up-to an explicit and simple equivalence relation (see Section 4.6); • elements of Tab(T E σ ) share many combinatorial properties similar to those of balanced tableaux (see Section 5).

4.1.

Type associated with a permutation. We first explain how one can associate any permutation σ with a type T σ such that |Tab(T σ )| = |Red(σ)|, using the results from [START_REF] Viard | A new family of posets generalizing the weak order on some Coxeter groups[END_REF].

Let λ n denote the staircase partition (n -1, n -2, . . . , 1). We identify the Ferrers diagram of λ n with the set {(a, b) ∈ N|1 ≤ a < b ≤ n}, by choosing new coordinates for each box of λ n , as depicted on Figure 4. Thanks to these coordinates, we associate to each box (a, b) ∈ λ n the integer θ(a, b) = ba -1, and this defines a type A n of shape λ n , as depicted on the right of Figure 4.

Using the type A n , we can associate each permutation with a type, thanks to the following definition and proposition. The coordinates of this box are [START_REF] Bjorner | Combinatorics of Coxeter groups[END_REF][START_REF] Greene | A probabilistic proof of a formula for the number of Young Tableaux of a given shape[END_REF].

Type associated with λ 5 . Remark 4.3. Notice that it is possible to construct a one-to-one correspondence between elements of Tab(T σ ) and balanced tableaux of shape D(σ), by swapping positions of some rows in elements of Tab(T σ ). Therefore, it is possible to reformulate what follows in terms of Rothe diagram and their labbelings. However, using Rothe diagrams instead of types T σ would require to rewrite most of the results from [START_REF] Viard | A new family of posets generalizing the weak order on some Coxeter groups[END_REF], without major modification. Furthermore, the use of the types T σ seems to be more natural, since they have similar properties as those of Rothe diagrams, and provide a natural description of the weak order and its combinatorics.

4.2.

A transformation on types. At this point, we already have a way to associate each vexillary permutation σ with a type T σ such that |Tab(T σ )| = f λ(σ) . However, in general the shape of T σ is not the Ferrers diagram of λ(σ). In the sequel, we introduce a combinatorial transformation on types that will allow us to turn T σ into a type of shape λ(σ) whenever σ is vexillary. Let us begin this section with introducing two notations. Let us consider a type T of shape S and let a be the index of a row of S. In general, the set A = {T ↓ a | T ∈ Tab(T )} does not correspond to a class of our classification. That is, in general there is no type T of shape S↓ a such that A = Tab(T ). However, we will prove in the sequel of this section that such a type T exists in a specific case. Definition 4.6. Let S be a diagram, T ∈ Type(S) and "a" be the index of a row of T . We say that the row a is dominant if and only if

• for all (a, y) ∈ N × N, if (a, y) ∈ S, then (a + 1, y) ∈ S;

• for all (a, y) ∈ S we have θ(a, y) > θ(a + 1, y). We have a similar definition of dominant column (see Figure 5) for a graphical representation of these two notions). Before moving to the combinatorial study of the types having a dominant row or column, let us introduce one last notation. Definition 4.7. Let T be a type of shape S and "a" be the index of a dominant row of T . We denote by T ↓ a the type of shape S↓ a being obtained from T by first decreasing by one all the integers in the row a of T , then by swapping rows a and a + 1 (resp. columns b and b + 1) of T , and keeping all other entries unchanged (see Figure 6).

0 0 1 3 1 2 2 1 0 1 1 Dominant row 0 0 1 3 1 1 1 0 0 1 1 -1 0 1 1 1 1 0 1 3 1 0 0 T T ↓ 1 Figure 6. From T to T 1 .
Our aim is now to prove that for any dominant row a of a type T we have

{T↓ a | T ∈ Tab(T )} = Tab(T ↓ a ). (3)
For that purpose, we first prove a technical lemma.

Lemma 4.8. Let T = (G S , θ) ∈ Type(S) and a be the index of a dominant row of T . Then, for any T = (t c ) ∈ Tab(T ), we have t a,y > t a+1,y for all (a, y) ∈ S.

Proof. Let T = (t (x,y) ) (x,y)∈S ∈ Tab(T ), and assume by contradiction that the lemma is not true and consider y maximal such that t (a,y) ≤ t (a+1,y) . Let c ∈ H S (a, y) \ {(a, y)} such that t c < t (a,y) , and let us split our study into two cases.

• If c ∈ L S (a, y), then we have that c ∈ H S (a+1, y) and t c < t (a,y) ≤ t (a+1,y) .

• If c ∈ A S (a, y), then there exists z > y such that c = (a, z), and we have by maximality of y t (a+1,y) ≥ t (a,y) > t (a,z) > t (a+1,z) .

This is enough to show that θ(a, y) ≤ θ(a + 1, y), and this contradicts the fact that a is dominant. This concludes the proof.

We now prove that (3) holds. Proof. Let T ∈ Tab(T ), and denote by T = (θ (c)) c∈S↓a the type of the tableau T := T↓ a = (t x,y ). We will prove that T = T ↓ . Let (x, y) be a box of S↓ a and let us define the following set

H x,y (T ) := {t a,b | (a, b) ∈ H x,y (Sh(T )) }.
We split our study into three cases.

• If x / ∈ {a, a + 1}, then we have H x,y (T ) = H x,y (T ), so that θ (x, y) = θ(x, y).

• If x = a, then we have H a,y (T ) = H a+1,y (T ) ∪ {t a,y }. However, by Lemma 4.8 we have t a,y = t a+1,y < t a,y , so that θ (a, y) = θ(a + 1, y). • If x = a+1, then we have H a+1,y (T ) = H a,y (T )\{t a+1,y }, so that θ a+1,y = θ a,y -1. Then, we have T = T ↓ a , hence T → T ↓ a send an element of Tab S (T ) to an element of Tab S↓a (T ↓ a ). Similar arguments show that T → T ↓ a also sends an element of Tab S↓a (T ↓ a ) to an element of Tab S (T ), but ↓ a is an involution, so that it is bijection. This concludes the proof for rows. The proof of the same property for columns is similar.

We finish this section with a useful definition. Definition 4.10. Let T be a type of shape S and a be the index of a row of T . The row a is called dethroned if and only if

• for all (a, y) ∈ N × N, if (a, y) ∈ S, then (a -1, y) ∈ S;

• for all (a, y) ∈ S we have θ(a -1, y) ≤ θ(a, y). We have a similar notion of dethroned column.

Obviously, if a is a dominant row of T , then a + 1 is a dethroned line of T ↓ a and conversely. The same holds for dominant columns. If a + 1 is a dethroned line of T , we denote by T ↑ a+1 the unique type such that (T ↑ a+1 )↓ a = T . 4.3. The exchange algorithm. In this section, we explain how one can turn the type T σ (where σ ∈ S n is vexillary) into a type of shape λ(σ) using recursively Proposition 4.9 on lines and columns. Definition 4.11 (Line-exchange algorithm). Let T be a type of shape S, the lineexchange algorithm is the algorithm described below.

(1) Erase all the empty rows of T .

(2) Set i := 1.

(a) If i is a dominant row of T , then set T := T ↓ i and go back to step [START_REF] Bjorner | Combinatorics of Coxeter groups[END_REF]. Otherwise, go to step (2-b). (b) If there is no row below i, then the algorithm stops. Otherwise, set i := i + 1 and go back to step (2-a). We denote by T L the type obtained after we perform the line-exchange algorithm.

There is an obvious analogous column-exchange algorithm, and we denote by T C the type obtained after we perform this algorithm on a type T . Lemma 4.12. For any type T , we have

|Tab(T )| = |Tab(T L )| = |Tab(T C )|.
Proof. It is clear by Proposition 4.9. Definition 4.13. For all type T , we denote by T E the type (T L ) C obtained by first performing the line exchange algorithm on T , and then performing the column exchange algorithm on T L . We now state the main result of this section, whose proof is detailed in Section 4.4 Theorem 4.14. Let σ ∈ S n be a vexillary permutation and T σ be its associated type. Then, we have:

(1) |Tab(T E σ )| = f λ(σ) = f λ(σ) ; (2) The shape of T E σ is λ(σ) .
l i (T σ ) := |{j | (j, i) ∈ Inv(σ)}|, c i (T σ ) := |{j | (i, j) ∈ Inv(σ)}|.
The following lemma is immediate by Definition 2.5. Lemma 4.16. Let σ ∈ S n , then the partition obtained by rearranging the sequence (l i (T σ )) i (resp. (c i (T σ )) i ) in a non-increasing order is µ(σ) (resp. λ(σ)). Let us now consider σ ∈ S n , we begin with putting the diagram Inv(σ) in a grid as depicted on Figure 8. We first push all the boxes of Inv(σ) against the Y -axes, and we then push all the boxes against the X-axes, obtaining by this way a Ferrers diagram (see Figure 9). The partition obtained after this Y X-process is Y -process X-process µ(σ). Indeed, when we packed all the boxes against the Y -axes we obtain a diagram whose rows are left-justified, and row i contains exactly l i (T σ ) boxes. Therefore, when we push everything on the X-axes, we are just rearranging these rows in a non-increasing order. Thus, thanks to Lemma 4.16 the resulting diagram is precisely µ(σ). Clearly, if we first stack on the X and then on the Y -axes (this process is called the XY -process), then the resulting partition is precisely λ(σ) .

The following proposition is an immediate consequence of the observation made in the previous paragraph. Proposition 4.17. Let σ ∈ S n . Then, σ is vexillary if and only if the partitions obtained after we perform the XY -process and Y X-process on Inv(σ) are the same.

We now prove an intermediate lemma.

Lemma 4.18. Let σ ∈ S n be a vexillary permutation and i, j be two integers. Then, we have the following two properties.

• If l i (T σ ) ≤ l j (T σ ), then we have that for all (i, a)

∈ N × N, if (a, i) ∈ Sh(T σ ), then (a, j) ∈ Sh(T σ ). • If c i (T σ ) ≤ c j (T σ ), then we have that for all (a, i) ∈ N × N, if (i, a) ∈ Sh(T σ ), then (j, a) ∈ Sh(T σ ).
Proof. We prove this lemma only for lines, since the proof for columns is similar, and we simply denote by l i the integer l i (T σ ). We denote by n the number of nonempty rows in the diagram Sh(T σ ) and we set i 1 , . . . , i n a sequence of indices such that:

• l i k = 0 for all k ∈ [n];
• the sequence (l i1 , . . . , l in ) is non-increasing. We will prove by induction on k ∈ [n] that the property holds for the row i k . First, notice that we have l i1 ≥ l iq for all 1 < q ≤ n. Let us fix such a q, and consider a box c = (i q , p) ∈ Sh(T σ ).

Assume by contradiction that (i 1 , p) ∈ Sh(T σ ), then we have the configuration depicted on Figure 10. Therefore, if we push the boxes against the X-axes, then in

(i q , p) i 1 l i1 boxes in this row Figure 10. Configuration when (i q , p) ∈ Sh(T σ ) and (i 1 , p) / ∈ Sh(T σ )
the first row there must be strictly more than l i1 boxes as represented on Figure 11. Thus, there are strictly more than l i1 boxes in the first row of the partition obtained i 1 More than l i1 + 1 boxes in this row Figure 11. Configuration after we pushed the boxes of Sh(T σ ) against the X-axes.

after we perform the XY -process on Sh(T σ ). However, by maximality of i1 , the first row of the partition obtained we perform the Y X-process on Sh(T σ ) contains l i1 boxes. Thus, λ(σ) = µ(σ) , and this contradicts the fact that σ is vexillary. Consequently, we have (i 1 , p) ∈ Sh(T σ ) and the lemma is true for row i 1 .

Let k be such that the lemma is true for rows i 1 , . . . , i k , and let λ(σ) = (λ 1 , . . . , λ m ). By induction, if we delete rows i 1 , . . . , i k in Sh(T σ ) and then perform the XY or Y X stacking process on the obtained diagram, then the resulting partition is (λ k+1 , . . . , λ m ) in both cases. Then, the same argument as for i 1 proves that the lemma holds for row i k+1 , and this ends the proof.

Eventually, we can now provide a proof of Theorem 4.14.

Proof of Theorem 4.14. Point (1): this is an immediate consequence of Theorem 2.6 together with Proposition 4.9.

Point (2): first, note that by definition of the line-exchange algorithm, we have for all T ∈ Type(S), we have (T

L ) L = T L and (T C ) C = T C . (4)
Let us denote by θ the valuation associated with T L σ and by l i the number of boxes in row i of Sh(T L σ ). Assume by contradiction that there exists an integer k such that l k < l k+1 . Then, thanks to Lemma 4.18 we have that Sh(T L σ ) is as represented on Figure 12. However, by construction for all (a, k) ∈ Sh(T L σ ) we have

Row k

Row k + 1 θ(a, k) > θ(a + 1, k). Therefore, if we perform the line-exchange algorithm on T L σ , then these two rows are exchanged, so that we have

(T L σ ) L = T L σ , contradicting (4)
. Thus, the sequence (l i ) i is non-increasing. Using a similar argument, we prove that the sequence (c i ) i is non-increasing, where c i is the number of boxes in column i of Sh(T E σ ) = Sh((T L σ ) C ). Eventually, the same arguments as for the proof of Lemma 4.18 prove that Sh(T E σ ) is a partition, which is necessarily equal to λ(σ) . 4.5. Link with balanced tableaux. Let us now explain how the construction made in the previous sections can be use to provide an alternative proof of Theorem 2.4 (but not fundamentally different from the one in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF]). Let λ be a partition of an integer n that we identify with its Ferrers diagram. A box c = (a, b) of λ is called a corner of λ if and only if there is no boxes on the right and below c, i.e. both (a + 1, b) and (a, b + 1) are not in λ.

Let c = (a, b) be a corner of λ such that k = λ a + λ b -1 is maximal (such a corner is not necessarily unique). Then, we can place λ in the staircase partition λ k+1 as shown on Figure 13.

Let us look at the corners (u, v) of λ which are on the diagonal boundary of the staircase partition. For each such corner, we set R (u,v) = {(x, y) ∈ λ | x ≤ u, y ≤ v} and we consider the union R of the R (u,v) . Then we let each connected component of λ \ R fall in the staircase tableau as shown on Figure 14. We repeat the same procedure for each connected component of the resulting diagram, while it is possible. At the end, we get a sub-diagram of λ k+1 , which we denote by S(λ). Lemma 4.19. There exists σ λ ∈ S k+1 such that Sh(T σ(λ) ) = S(λ). Moreover, σ λ is vexillary and λ(σ) = λ.

Proof. The proof of this lemma requires the use of some results and notations from [START_REF] Viard | A new family of posets generalizing the weak order on some Coxeter groups[END_REF], which we first recall. Let us consider the type A k+1 (see Section 4.1) together with its associated valuation θ. We consider the set IS(A k+1 ) made of all the sets (

A ⊂ λ k+1 = {(a, b) ∈ N 2 | 1 ≤ a < b ≤ k + 1} such that: (1
) for all c ∈ λ k+1 \ A, θ(c) ≥ |A ∩ H (λ k+1 ) (c) \ {c} |. 2
Thanks to [START_REF] Viard | A new family of posets generalizing the weak order on some Coxeter groups[END_REF]Prop. 3.1] and [START_REF] Viard | A new family of posets generalizing the weak order on some Coxeter groups[END_REF]Theorem 4.1], a subset A of λ k+1 is the inversion set of a permutation in S k+1 if and only if A ∈ IS(A k+1 ).

Our aim is now to prove that S(λ) ∈ IS(A k+1 ). Let z = (x, y) ∈ λ k+1 .

• If z / ∈ S(λ), then for all z ∈ H λ k+1 (z) ∩ S(λ), z is in the same column and strictly below z. Moreover, by definition θ(z) equals the number of boxes strictly below z. Thus, we have θ(z) ≥ |H λ k+1 (z) ∩ S(λ)|;

• If z = (x, y) ∈ S(λ), then by construction of S(λ) there exists z = (x , y ) ∈ S(λ) such that: x ≥ x, y ≥ y, θ(z ) = 0, and for all x ≤ u ≤ x and y ≤ v ≤ y , we have (u, v) ∈ S(λ).

Thus, we have

θ(z) = (x -x) + (y -y) ≤ |H S(λ) (z)| -1.
Therefore, we have S(λ) ∈ IS(A k+1 ), so that there exists σ λ such that Sh(T σ λ ) = S λ . Moreover, if we perform the stacking process on S(λ), it is clear that both XY and Y X processes end with the partition λ(σ). Thus, σ λ is vexillary and this concludes the proof.

We get T σ by translating T ω along the diagonal.

Figure 15. The types T σ and T ω seen as subsets of λ n .

(1) Erase all the empty rows of T .

(2) Set i := r, where r is the number of non-empty rows of T . (a) If i is a dethroned row of T , then set T := T ↑ i and go back to step [START_REF] Bjorner | Combinatorics of Coxeter groups[END_REF]. Otherwise, go to step (2-b). (b) If there is no row above i, then the algorithm stops. Otherwise, set i := i -1 and go back to step (2-a). We denote by L T the type obtained after we perform the reverse line-exchange algorithm. We also denote by T the type obtained from T deleting empty rows. In general, the type L (T L ) is different from the type T . However, it is clear that L (T L ) = T whenever there is no dethroned lines in T , and by construction there is no dethroned lines in T σ for any σ ∈ S n .

Therefore, for all vexillary permutations σ, ω ∈ S n , if T E σ = T E ω then we have T σ = T ω , and this implies that T σ = T ω . Then, we have Inv(σ) = Inv(ω) implying that σ = ω, i.e. ω ∼ v σ. This concludes the proof.

Combinatorial properties of types T E σ

We finish this article by studying two combinatorial properties of types T E σ , relative respectively to Schur functions and partial fillings of tableaux. 5.1. Semi-standard tableaux of type T E σ and Schur function. As explained in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF], one can define a notion of "semi-standard balanced tableaux" of a given shape λ n, thanks to the concept of column-strict balanced labelling of a diagram, that we now detail by adapting it to our terminology. Let λ be a partition and B be the type associated with Bal(λ) (see Example 3.3). Let T = (t c ) c∈λ be a filling of λ with integer, which is not necessarily a tableau (for instance, a given integer can appear several times in T ). We say that T is a column-strict balanced labelling of λ if and only if there exists a filling sequence L = [c 1 , . . . , c n ] such that:

• for all i < j, t ci ≤ t cj ;

• for all i < j, if c i and c j are in the same column of λ, then t ci < t cj . Let us denote by SST(B) the set of all column-strict balanced labellings of λ (the SST stands for "semi-standard tableau of type B"). To each element T = (t c ) c∈λ of SST(B), we can associate a monomial x T = c∈λ x tc , and thanks to [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF] we have:

s λ (x 1 , x 2 , . . .) = T ∈SST (B)
x T , where s λ is the Schur function of shape λ.

All these definitions admit a straightforward generalization for all type, and we associate each type T with a set SST(T ) of semi-standard tableaux of type T . We then have the following property. Proposition 5.1. Let σ be a vexillary permutation. Then, we have

s λ(σ) = T ∈SST (T E σ )
x T .

Proof. We have a one-to-one correspondence between the elements of SST(T E σ ) and the elements of SSF(Inv(σ)) introduced in [12, Section 5]. More precisely, we go from one set to the other just by swapping column and lines according to the line and column exchange process. Therefore, the result follow immediately from [12, Theorem 5.10].

Partial fillings of tableaux of type T E

σ . It is classical that the number standard tableaux of a given shape λ satisfy the following relation:

|SYT(λ)| = λ - |SYT(λ -)|,
where the sum ranges on the set of all the partition λ -obtained from λ by suppressing a corner of its Ferrers diagram. Thanks to Theorem 2.4, (5.2) also holds for balanced tableaux. In fact, proving (5.2) for balanced tableaux is clearly equivalent to proving Theorem 2.4, and this approach naturally leads to study the number of balanced tableaux such that the integers 1, 2, . . . , k appear at given fixed positions. The study of this problem has been started in [START_REF] Edelman | Balanced tableaux[END_REF], but was only solved in some specific cases. In this section, we give a complete solution to this problem in the general case of the type T E σ with σ vexillary, and this can be applied to balanced tableaux as well. Before moving to the statement and the proof of our results, let us make two important remarks.

(1) The results presented here are implicit in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF] in the case of balanced tableaux, and can be deduced with the same arguments as the ones used here. (2) Our approach gives a more direct proof that (5.2) holds for balanced tableaux, as required in [3, Section 2]. However, our current proof does not lead to a satisfactory combinatorial proof of 2.4 since it still uses Theorem 2.6 as fundamental compound. Nevertheless, the concepts developed in the current article might be a first step toward such a proof. We begin with introducing a useful notation. Proof. Let us assume that N σ,U is not empty. By construction, there exists a bijection Ψ between the set of boxes of T σ and the inversion set of σ such that for any sequence L = [x 1 , . . . , x n ], we have that L is a filling sequence of T E σ if and only if [Ψ(x 1 ), Ψ(x 2 ), . . . , Ψ(x n )] is a filling sequence of T σ . Consequently, thanks to [START_REF] Viard | A new family of posets generalizing the weak order on some Coxeter groups[END_REF]Theorem 4.1], Ψ({z 1 , . . . , z k }) is the inversion set of a permutation τ ∈ S m , and we have a one-to-one correspondence between N σ,U and the set of the maximal chains from τ to σ in (S m , ≤ R ). Thanks to [2, Prop. 3.1.6, p. 69], the set of maximal chains from τ to σ in (S m , ≤ R ) is in one-to-one correspondence with Red(τ -1 ω), and this concludes the proof. This theorem applies in particular to balanced tableaux. Moreover, this result is constructive: the permutation ω can be computed. We cannot provide a systematic description of the associate permutation, however we have the following combinatorial result. Proof. We keep the notations introduced in the proof of Theorem 5.3. Let τ be the permutation whose inversion set is given by {Ψ(x 1 ), . . . , Ψ(x k )}. Since ω = τ -1 σ with τ ≤ R σ, we have Inv(ω) = τ -1 (Inv(σ) \ Inv(τ )) = τ -1 (Sh(T σ ) \ {Ψ(x 1 ), . . . , Ψ(x k )}).

Thus, if we denote by l i (resp. c i ) the number of boxes in row (resp. column) i of λ(σ) \ {z 1 , . . . , z k }, we have that the sequences (l i ) i and (g i (ω)) i (resp. (c i ) i and (r i (ω)) i ) are equal up to re-ordering. Therefore, ω is vexillary and µ(ω) = µ. This concludes the proof.

Notice that the results of the current section apply to balanced tableaux. Let T be a balanced tableau of shape λ n. By definition, we have that the integer 1 appears in the upper right corner of a block (see Figure 16). Then, thanks Then, the number of balanced tableaux of shape λ such that 1 is in the box c equals the number of standard tableaux of shape λ -, where λ -n -1 is obtained from λ by suppressing the corner of the block B.

The previous proposition directly implies that for all partition λ,

|Bal(λ)| = λ - |Bal(λ -)|,
where the sum range on all partitions obtained from λ by suppressing a corner.

Definition 2 . 3 .

 23 Let S be a diagram such that |S| = n. A balanced tableau T = (t a,b ) (a,b)∈S of shape S is a Young tableau satisfying the following condition: for all (a, b) ∈ S, a a,b = |{(x, y) ∈ H S (a, b) | t x,y < t a,b }|.

Definition 2 . 7 .

 27 Let σ ∈ S n , the Rothe diagram D(σ) of σ is the subset of [n] × [n] defined by D(σ) := {(a, σ(b)) ∈ [n] × [n] | a < b and σ(a) > σ(b)}.

Figure 1 .

 1 Figure 1. Rothe diagram of the permutation σ = [5, 3, 2, 1, 4] (on the left) and a balanced tableau of shape D(σ) (on the right).

  Let us briefly explain how this bijection is constructed. By definition of the Rothe diagram of a permutation σ ∈ S n , it is clear that (a, σ(b)) ∈ D(σ) if and only if (a, b) ∈ Inv(σ).

Proposition 3 . 8 .

 38 For any filling sequence L, we have T L ∈ Tab(T ), and the map L → T L is a bijection. Proof. This is clear by induction on |S|. Example 3.9. Consider the type T on the top-left of Figure 2 and the filling sequence L = [(1, 3); (1, 1); (1, 2); (2, 2); (2, 1)] (since we represent Ferrers diagrams with the English convention, we use the matrix coordinates for each box). The types on the top of the figure are the types obtained after each iteration of the filling process.

Figure 3 .

 3 Figure 3. Proposition 3.13. Let S be a diagram, if we choose uniformly a type T in Type(S), then the expected value for |Tab S (T )| is n! c∈S h S (c).

Figure 4 .Proposition 4 . 2 .

 442 Figure 4. Representation of the type A n . Definition 4.1. We denote by T σ the sub-diagram of λ n made of the boxes whose coordinates are the elements of Inv(σ), and such that each box c ∈ Inv(σ) is filled with the integer θ(c) coming from the definition of A n . Proposition 4.2. Let σ ∈ S n . Then, T σ is a type and we have |Tab(T σ )| = |Red(σ)|.Proof. This is an immediate reformulation of[START_REF] Viard | A new family of posets generalizing the weak order on some Coxeter groups[END_REF] Theorem 4.1].

Definition 4 . 4 .

 44 Let S be a diagram and "a" (resp. "b") be a row (resp. a column) of S. We denote by S↓ a (resp.-→ S b ) the diagram obtained by swapping rows a and a + 1 (resp. columns b and b + 1) of S. Definition 4.5. Let T be a tableau of shape S and a (resp. b) a row (resp. a column) of S. We denote by T ↓ a (resp. -→ T b ) the tableau of shape S↓ a (resp. -→ S b ) obtained from T by exchanging rows a and a + 1 (resp. columns b and b + 1).

Figure 5 .

 5 Figure 5. A dominant row (on the left) and a dominant column (on the right).

Proposition 4 . 9 (

 49 Exchange property). Let T be a type and "a" (resp. b) be a dominant row (resp. column) of T . Then, the map T → T↓ a (resp. T → -→ T b ) is a bijection between T ab(T ) and T ab(T ↓ a ) (resp. Tab( -→ T b )).

Figure 7 . 4 . 4 .

 744 Figure 7. This is the type T E σ obtained considering the vexillary permutation σ =[START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF][START_REF] Little | Combinatorial aspects of the Lascoux-Sch à 1 4 tzenberger tree[END_REF][START_REF] Novelli | A direct bijective proof of the hook-length formula[END_REF][START_REF] Greene | A probabilistic proof of a formula for the number of Young Tableaux of a given shape[END_REF][START_REF] Lascoux | Schubert polynomials and the Littlewood-Richardson rule[END_REF][START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF][START_REF] Bjorner | Orderings of Coxeter groups[END_REF][START_REF] Edelman | Balanced tableaux[END_REF][START_REF] Bjorner | Combinatorics of Coxeter groups[END_REF]

Figure 8 .

 8 Figure 8. Diagram associated with σ = [7, 8, 4, 5, 1, 2, 6, 9, 3] ∈ S 9

Figure 9 .

 9 Figure 9.

Figure 12 .

 12 Figure 12. Rows k and k + 1 of Sh(T L σ ).

  ) for all c ∈ A, θ(c) ≤ |A ∩ H (λ k+1 ) (c) \ {c} |; Corner c = (a, b) such that λ a + λ b -1 is maximal.

Figure 13 .

 13 Figure 13. The partition (8, 7, 7, 7, 3, 3, 1) in λ 11 .

Definition 5 . 2 .

 52 Let σ ∈ S m be a vexillary permutation such that λ(σ) n and U = [z 1 , . . . , z k ] be a sequence of boxes of the Ferrers diagram of λ(σ). We denote by N σ,U the set defined byN σ,U := {T = (t c ) c∈λ ∈ Tab(T E σ ) | t zi = i for all i ∈ [k]}.Theorem 5.3. Let σ ∈ S m be a vexillary permutation such that λ(σ) n and U = [z 1 , . . . , z k ] be a sequence of boxes of the Ferrers diagram of λ(σ). Then, we have that either N σ,U is empty, or there exists ω ∈ S m such that |N σ,U | = |Red(ω)|.

Theorem 5 . 4 .

 54 Let σ ∈ S m be a vexillary permutation such that λ(σ) n and U = [z 1 , . . . , z k ] be a sequence of boxes of the Ferrers diagram of λ. If there exists a partition µ (nk) such that the resulting partition of the XY and Y X processes applied on the diagram λ(σ) \ {z 1 , . . . , z k } is µ, then |N σ,U | = f µ .

Definition 5 . 5 .

 55 Let λ = (λ 1 , . . . , λ k ) be a partition of n and (a, b), (c, d) ∈ λ, we say that (a, b) and (c, d) are in the same block if and only if λ a = λ c . Let B be a block of λ and let i be the minimal integer such that (i, λ i ) ∈ B, then the box (i, λ i ) is called the upper right corner of B.

1

  Figure 16. Possible positions of the integer 1 in a ballanced tableau.

Proposition 5 . 6 .

 56 Let B be a block of λ n and c be the upper right corner of B.

Proposition 4.20. Let σ λ be the permutation whose inversion set is S(λ). Then, we have Tab(T L σ λ ) = Bal(λ). Proof. First, note that we have Sh(T L σ λ ) = λ by construction of S(λ). We denote by θ and θ the valuations associated with the types T σ λ and T L σ λ , respectively. Let c = (a, b) ∈ S(λ) such that all boxes in the same row and on the right of c are not in S(λ). Then, by construction of S(λ) and by definition of θ we have:

• θ(c) equals the number of indices k < a such that row k of S(λ) contains more boxes than row a;

Therefore, when we perform the line-exchange algorithm on T σ λ we have that the row a of T σ λ is swapped with exactly θ(c) rows below it. Thus, we have that for all d ∈ λ, θ (d) = a λ (d), hence the elements of Tab(T σ λ ) are the balanced tableaux of shape λ, and reciprocally. This ends the proof.

The previous proposition, together with Proposition 4.9, immediately imply Theorem 2.4. 4.6. An equivalence relation between vexillary permutations. At this point, a natural question arises: given two vexillary permutation σ and ω, when do we have T E σ = T E ω ? In this section we answer this section by exhibiting an equivalence relation ∼ v on the set of vexillary permutations with the property that, for any two vexillary permutations σ ∈ S n and ω ∈ S m , T E σ = T E ω if and only if σ ∼ v ω. We first introduce a notation. Let σ ∈ S n , p ≤ n be the lowest integer such that σ(p) = p and q ≤ n be the biggest integer such that σ(q) = q. We define

Note that σ is an element of S n+1-p-q because of the choice of p and q. Definition 4.21. We say that σ ∼ v ω if and only if σ = ω. Theorem 4.22. Let σ and ω be two vexillary permutations, then T E σ = T E ω if and only if σ ∼ v ω.

Proof.

Step 1: we begin with giving a combinatorial interpretation for the relation ∼ v . Let σ ∈ S n and ω ∈ S m such that σ ∼ v ω. Without loss of generality, we can assume that n is larger than m. Then, we can see ω as a permutation of S n by adding (nm) fixed points at the end of ω. Let us denote by p σ (resp. p ω ) the smallest integer such that σ(p σ ) = p σ (resp. ω(p ω ) = p ω ). By definition, we have Inv(σ) = Inv(ω) and

Thus, if we look at T σ and T ω , we have the situation described on Figure 15. Then, we have T E σ = T E ω by construction.

Step 2: in order to prove the converse implication, we define two algorithms: one which reverses the Line-exchange Algorithm and another which reverse the Column-exchange Algorithm. Since these two algorithms are similar, we only give the definition of the algorithm on lines. Let T be a type of shape S, the reverse line-exchange algorithm is the algorithm described below.