Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Ad

THE HIVE MODEL AND THE POLYNOMIAL NATURE OF STRETCHED LITTLEWOOD–RICHARDSON COEFFICIENTS

R.C. KING, C. TOLLU, AND F. TOUMAZET

Abstract. The hive model is used to explore the properties of both ordinary and stretched Littlewood–Richardson coefficients. The latter are polynomials in the stretching parameter t. It is shown that these may factorise, and that they can then be expressed as products of certain primitive polynomials. It is further shown how to determine a sequence of linear factors (t + m) of the primitive polynomials, as well as bounds on their degree which are conjectured to be exact.

Résumé. Nous utilisons le modèle des ruches pour étudier les propriétés des cœfficients de Littlewood–Richardson et de leurs dilatations. Ces derniers sont des polynômes en le paramétre de dilatation t. Nous montrons que les uns et les autres peuvent se factoriser: ils s’écrivent comme des produits de coefficients (respectivement polynômes) primitifs. En outre, nous montrons comment établir une suite de facteurs linéaires (t+m) des polynômes primitifs, et proposons une borne supérieure de leur degré.

1. Introduction

Littlewood–Richardson coefficients, c_{λμ}^{ν}, are interesting combinatorial objects [LR]. They are indexed by partitions λ, μ and ν, and they count the number of Littlewood–Richardson tableaux of skew shape ν/λ and weight μ. They are therefore non-negative integers. Although it is a non-trivial matter to determine whether or not c_{λμ}^{ν} is non-zero, it turns out that this is the case if and only if |λ| + |μ| = |ν| and certain partial sums of the parts of λ, μ and ν satisfy what are known as Horn inequalities.

Multiplying all the parts of the partitions λ, μ and ν by a stretching parameter t, with t a positive integer, gives new partitions tλ, tμ and tν. The corresponding stretched Littlewood–Richardson coefficients are known to be polynomials in the stretching parameter t [DW2, R]. Such an LR-polynomial is defined by

(1.1)  P_{λμ}^{ν}(t) = c_{tλ,tμ}^{tν},

and has a generating function of the form

(1.2)  F_{λμ}^{ν}(z) = \frac{G_{λμ}^{ν}(z)}{(1 − z)^{d+1}} = ∑_{t=0}^{∞} c_{tλ,tμ}^{tν} z^{t}

where d is the degree of P_{λμ}^{ν}(t), and G_{λμ}^{ν} is a polynomial in z of degree g ≤ d.

For example, in the case λ = (4, 3, 3, 2, 1), μ = (4, 3, 2, 2, 1) and ν = (7, 4, 4, 4, 3, 2, 1) one finds c_{λμ}^{ν} = 13 and

(1.3)  P_{λ,μ}^{ν}(t) = \frac{1}{10080}(t + 1)(t + 2)(t + 3)(t + 4)(t + 5)(5t + 21)(t^{2} + 2t + 4),

with

(1.4)  F_{λμ}^{ν}(z) = \frac{1 + 4z + 12z^{2} + 3z^{3}}{(1 − z)^{9}} .

It is the intention here to try to shed some light on the nature of the LR-polynomials and their generating functions. In particular we concentrate on the possible factorisation of any particular LR-polynomial as a product of simpler LR-polynomials, the degree d of an LR-polynomial, and the number of its linear factors (t + m). We do not explore two particular conjectures [KTT1] to the effect that the non-zero coefficients of the polynomial P_{λμ}^{ν}(t) are always positive rational numbers, while those of G_{λμ}^{ν}(z) are all positive integers.

Our approach is based largely on the use of a hive model [BZ2, KT, B] which allows Littlewood–Richardson coefficients to be evaluated through the enumeration of integer points of certain rational polytopes. Before defining hives, puzzles and plans, that are the combinatorial constructs to be used in this context, it is worth recalling some definitions and properties of Littlewood–Richardson coefficients and LR-polynomials.

2. Definitions and properties

Let n be a fixed positive integer, let x = (x_{1}, x_{2}, …, x_{n}) be a vector of indeterminates, and let λ = (λ_{1}, λ_{2}, …, λ_{n}) be a partition of weight |λ| and of length ℓ(λ) ≤ n. Thus λ_{k} ∈ ℤ^{+} for k = 1, 2, …, n, with λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{ℓ(λ)} > 0 and λ_{k} = 0 for k > ℓ(λ).

Definition 2.1. For each partition λ with ℓ(λ) ≤ n there corresponds a Schur function s_{λ}(x) defined by

(2.1)  s_{λ}(x) = \begin{matrix}|x_{i}^{n+λ_{j}−j}| & 1≤i,j≤n \\ |x_{i}^{n−j}| & 1≤i,j≤n \end{matrix}

Choosing n sufficiently large, the Littlewood–Richardson coefficients may be defined by

Definition 2.2.

(2.2)  s_{λ}(x) s_{μ}(x) = ∑_{ν} c_{λμ}^{ν} s_{ν}(x).

where the summation is over all partitions ν.

The expansion (2.2) may be effected by means of the Littlewood–Richardson rule [LR] which states that c_{λμ}^{ν} is the number of Littlewood–Richardson skew tableaux T^{ν/λ} of shape ν/λ and weight μ obtained by numbering the boxes of the skew Young diagram F^{ν/λ} with μ_{i} entries i for i = 1, 2, …, n that are weakly increasing across rows, strictly increasing down columns and satisfy the lattice permutation rule. This rule states that in reading the entries of T^{ν/λ} from right to left across each row in turn from top to bottom, then at every stage the number of k’s is greater than or equal to the number of (k + 1)’s for all k = 1, 2, …, n − 1. For the sake of what is to follow, it is convenient to augment each Littlewood–Richardson skew tableau T^{ν/λ}, with a tableau obtained by numbering all the boxes of the Young diagram F^{λ} with entries 0, as in [LR] p122, thereby creating what we call an LR-tableau D of shape ν. The entries 0 contribute nothing to the weight of D, which remains that of the portion T^{ν/λ}. By way of example, for n = 3, λ = (3, 2, 0), μ = (2, 1, 0) and ν = (4, 3, 1), there exist just two LR-tableaux:

(2.3)  0 0 0 1 0 0 1 2  0 0 0 1 0 0 2 1

Hence c_{32,21}^{431} = 2.

To specify the necessary and sufficient conditions on λ, μ and ν for c_{λμ}^{ν} to be non-zero it is convenient to introduce the notion of partial sums of the parts of a partition and some other notational devices.

Let n be a fixed positive integer and N = {1, 2, …, n}. Then for any positive integer r ≤ n and any subset I = {i_{1}, i_{2}, …, i_{r}} of N of cardinality #I = r, the partial sum indexed by I of any partition λ = (λ_{1}, λ_{2}, …, λ_{n}) of length ℓ(λ) ≤ n is defined to be

(2.4)  ps (λ)_{I} = λ_{i_{1}} + λ_{i_{2}} + ⋯ + λ_{i_{r}} .

In the special case for which I = {1, 2, …, i} we write ps (λ)_{i} instead of ps (λ)_{I}. Quite generally, if i_{1} < i_{2} < ⋯ < i_{r}, let Ĩ = (i_{r}, …, i_{2}, i_{1}). It follows that if δ_{r} = (r, r − 1, …, 1) then α(I) = Ĩ− δ_{r} is a partition of length ℓ(α(I)) ≤ r.

With this notation, building on a connection with the Horn conjecture [H] regarding eigenvalues of Hermitian matrices, the following theorem has been established by Klyachko [K], Knutson and Tao [KT] and others. A comprehensive review of these developments has been provided by Fulton [F].

Theorem 2.3 (Horn inequalities). Let λ, μ and ν be partitions of lengths ℓ(λ), ℓ(μ), ℓ(ν) ≤ n. Then c_{λμ}^{ν} > 0 if and only if |ν| = |λ| + |μ| and for all r = 1, 2, …, n − 1

(2.5)  ps (ν)_{K} ≤ ps (λ)_{I} + ps (μ)_{J}

for all triples (I, J, K) ∈ N_{r}^{n}, where N_{r}^{n} is the set of triples (I, J, K), with I, J, K ⊂ N and #I = #J = #K = r, such that if α(I) = Ĩ − δ_{r}, β(J) = J̃ − δ_{r} and γ(K) = K̃ − δ_{r} then c_{α(I)β(J)}^{γ(K)} > 0. Moreover, not all of the Horn inequalities of type (2.5) are essential, only

those for which (I, J, K) ∈ R_{r}^{n}, where R_{r}^{n} is the subset of N_{r}^{n} for which c_{α(I)β(J)}^{γ(K)} = 1.

Unfortunately, even for comparatively small values of r it is not a trivial matter to identify all partitions α(I), β(J), γ(K), and hence (I, J, K), such that the Littlewood– Richardson coefficient c_{α(I)β(J)}^{γ(K)} = 1.

Turning to stretched Littlewood–Richardson coefficients, the fact that all the above partial sum conditions are linear and homogeneous in the various parts of λ, μ and ν ensures the validity of the following:

Theorem 2.4 (Saturation Condition). [KT, B, DW1] For all positive integers t

(2.6)  c_{tλ,tμ}^{tν} > 0 ⟺ c_{λμ}^{ν} > 0.

Furthermore, the following condition has been proved by a variety of means: Theorem 2.5 (Polynomial Condition). [DW2, R] For all partitions λ, μ and ν such that c_{λμ}^{ν} > 0 there exists a polynomial P_{λμ}^{ν}(t) in t such that P_{λμ}^{ν}(t) = c_{tλ,tμ}^{tν} for all t ∈ ℕ.

In addition, the following conjecture has been established as a theorem: Theorem 2.6 (Fulton’s Conjecture). [KTW] For all positive integers t

(2.7)  c_{tλ,tμ}^{tν} = 1 ⟺ c_{λμ}^{ν} = 1.

Thus, if c_{λμ}^{ν} = 1, the corresponding polynomial P_{λμ}^{ν}(t) = 1.

3. The hive model

The hive model arose out of the triangular arrays of Berenstein and Zelevinsky used to specify individual contributions to Littlewood–Richardson coefficients [BZ2]. The model was then taken up by Knutson and Tao in a manner described in an exposition by Buch [B].

An n-hive is an array of numbers a_{ij} with 0 ≤ i, j, i + j ≤ n placed at the vertices of an equilateral triangular graph. Typically, for n = 4 their arrangement is as shown below:

a_{13} a_{22} a_{00}  a_{10}  a_{20}  a_{30}  a_{40} a_{31} a_{03} a_{02} a_{01}  a_{04} a_{12} a_{11}  a_{21}

Such an n-hive is said to be an integer hive if all of its entries are non-negative integers. Neighbouring entries define three distinct types of rhombus, each with its own constraint condition.

α  δ b a  α c δγ  β  b  d cδ γ γ  d R1:  R2:  R3:a a  β α β  b  d c

In each case, with the labelling as shown, the hive condition takes the form:

(3.1)  b + c ≥ a + d

In what follows we make use of edge labels more often than vertex labels. Each edge in the hive is labelled by means of the non-negative difference, ϵ = q − p, between the labels, p and q, on the two vertices connected by this edge, with q always to the right of p. In all the above cases, with this convention, we have α + δ = β + γ, and the hive conditions take the form:

(3.2)  α ≥ γ and β ≥ δ,

where, of course, either one of the conditions α ≥ γ or β ≥ δ is sufficient to imply the other.

In order to enumerate contributions to Littlewood–Richardson coefficients, we require the following:

Definition 3.1. An LR-hive is an integer n-hive, for some positive integer n, satisfying the hive conditions (3.1), or equivalently (3.2), for all its constituent rhombi of type R1, R2 and R3, with border labels determined by partitions λ, μ and ν, for which ℓ(λ), ℓ(μ), ℓ(ν) ≤ n and |λ| + |μ| = |ν|, in such a way that a_{00} = 0, a_{0,i} = ps (λ)_{i}, a_{j,n−j} = |λ| + ps (μ)_{j} and a_{k,0} = ps (ν)_{k}, for i, j, k = 1, 2, …, n.

Schematically, we have

|λ| 0  |ν| = |λ| + |μ| ⋯ λ_{1}  ν^{1}  ν^{1} + ν^{2}  |λ| + μ_{1} + μ_{2} |λ| + μ_{1}⋯ λ_{1} + λ_{2}  ⋯

Alternatively, in terms of edge labels we have:

ν^{n} ⋯ ν^{1}  μ_{1} μ_{2}  ⋯ μ_{n} ν^{2} ⋯ λ_{n} λ_{2} λ_{1}

There exists a bijection between LR-tableaux D, of shape determined by ν/λ and of weight μ and LR-hives H, with border labels specified by λ, μ and ν. An illustration of this bijection is given below for a typical LR-tableau D in the case n = 3, λ = (3, 2), μ = (2, 1) and ν = (4, 3, 1). In D, which has overall shape ν, the portion of shape λ has been signified by entries 0, while the other entries correspond to the parts of the weight μ arranged in accordance with the Littlewood–Richardson rules. The first step is to form what might be called a generalised Gelfand–Tsetlin pattern G by writing down a list of partitions describing the shapes of sub-tableaux of D formed by restricting the entries to be no more than k for k = 3, 2, 1, 0. Then one adds a diagonal of zeros and forms cumulative row sums to arrive at an array Z. The lower right triangular portion of Z is then reoriented to give an LR-hive H, where for display purposes the hive edges have been omitted.

(3.3)  \begin{aligned}& D = 0 0 0 1 0 0 2 1 & ⟺ & G = 4 3 1 4 3 1 4 2 1 3 2 0 \\ ⟺ & Z = 0 4 7 8 0 4 7 8 0 4 6 7 0 3 5 5 & ⟺ & H = 5 5 7 3 6 8 0 4 7 8 \end{aligned}

More detailed considerations of the maps illustrated in this example lead to: Proposition 3.2. [B] The Littlewood–Richardson coefficient c_{λμ}^{ν} is the number of LR-hives with border labels determined as in Definition 3.1 by λ, μ and ν.

The above sequence of maps is such that for all (i, j) with 0 ≤ i, j, i + j ≤ n the entries of the LR-hive H are given by

(3.4)  a_{ij} = # of entries ≤ i in first (i + j) rows of D .

As far as the boundary labels are concerned, it should be noted, firstly, that a_{0j} is the number of entries equal to 0 in the first j rows of D. That is to say, a_{00} = 0 and a_{0j} = ps (λ)_{j} for j = 1, 2, …, n. Secondly, a_{i0} is the number of entries less than or equal to i in the first i rows of D. However, by virtue of their weakly increasing order across rows and the lattice permutation rule, all entries in the first i rows of D are no greater than i. It follows that a_{i0} = ps (ν)_{i} for i = 1, 2, …, n. Thirdly, a_{i,n−i} is the total number of entries less than or equal to i in D. Thus a_{0,n} = |λ| and a_{i,n−i} = |λ| + ps (μ)_{i} for i = 1, 2, …, n. Thus the boundary labels of the LR-hive H are given by the partial sums of the partitions λ, μ and ν, as required.

A further consequence of (3.4) is that the hive decrements Δ = b+c−a−d = α−γ = β−δ arising from the rhombi of type R1, R2 and R3 with a in position(i, j) are given by:

(3.5)  R1 : Δ = # of entries (i + 1) in first (i + j) rows of D

− # of entries (i + 2) in first (i + j + 1) rows of D;

(3.6)  R2 : Δ = # of entries (i + 1) in the (i + j)th row of D;
(3.7)  R3 : Δ = # of entries ≤ i in (i + j + 1)th row of D

− # of entries ≤ (i + 1) in (i + j + 2)th row of D .

Since for each k = 1, 2, …, n the number of entries k in each row of D is non-negative, we have Δ ≥ 0 for each rhombus of type R2. The fact that the non-zero entries in D are weakly increasing across rows and strictly increasing down columns then ensures that Δ ≥ 0 for each rhombus of type R3. Finally, in the case of each rhombus of type R1, the hive condition Δ ≥ 0 is implied directly by the lattice permutation rule. It follows that each H obtained from any LR-tableau D is indeed an LR-hive.

Conversely, the inverse of the above maps from any LR-hive H always yields an LRtableau D. The positions of the 0’s are determined by the border labels a_{0,j} = ps (λ)_{j}. Then the R2 hive condition Δ ≥ 0 is just the condition that the number of entries of each type in each row of D is a non-negative integer. If these entries are arranged in weakly increasing order across the rows of D, then the R3 hive condition Δ ≥ 0 implies that, apart from the possibility of consecutive 0s, the entries are strictly increasing down columns. The fact that the R1 hive condition Δ ≥ 0 is precisely the lattice permutation rule, then ensures that each D obtained from an LR-hive H is an LR-tableau.

Thus the maps described above are bijective, and Proposition 3.2 follows. □

As an example of the application of this Proposition, if n = 3, λ = (3, 2, 0), μ = (2, 1, 0) and ν = (4, 3, 1) then the corresponding LR-hives take the form

(3.8)  \begin{aligned}& & & 5 \\ & & 5 & & 7 \\ & 3 & & a & & 8 \\ 0 & & 4 & & 7 & & 8 \end{aligned}

The LR-hive conditions for all the constituent rhombi then imply that 6 ≤ a ≤ 7. Thus there are just two LR-hives with the given boundary labels, namely those with a = 7 and a = 6. Thus c_{32,21}^{431} = 2 in accordance with the result established earlier by enumeration of the LR-tableaux of (2.3).

It might be pointed out here, that when expressed in terms of edge labels, the hive conditions (3.2) for all constituent rhombi of types R1, R2 and R3 imply that in every LR-hive the edge labels along any line parallel to the north-west, north-east and southern boundaries of the hive are weakly decreasing in the north-east, south-west and easterly directions, respectively. This can be seen from the following 5-vertex sub-diagrams.

β  α  γ  α  β  γ  α  γ  β

The edge conditions on the overlapping pairs of rhombi (R1,R2), (R1,R3) and (R2,R3) in the above diagrams give in each case α ≥ β and β ≥ γ, so that α ≥ γ as claimed. This is of course consistent with the fact that edges of the three north-west, north-east and southern boundaries of each LR-hive are specified by partitions λ, μ and ν, respectively.

4. Factorisation

It was noted in the work of Berenstein and Zelevinsky [BZ1] that some Kostka coefficients may factorise. Although rather easy to prove using semistandard tableaux, this factorisation property may also be established through the use of K-hives [KTT2]. Analogous methods may be used to show that some Littlewood–Richardson coefficients may also factorise. Following the use of similar terminology in the case of Kostka coefficients [KTT2], we propose the following

Definition 4.1. Let λ, μ and ν be partitions such that |ν| = |λ| + |μ|, ℓ(λ), ℓ(μ), ℓ(ν) ≤ n and c_{λμ}^{ν} > 0. Then the Littlewood–Richardson coefficient c_{λμ}^{ν} is said to be primitive if ps (ν)_{K} < ps (λ)_{I} + ps (μ)_{J} for all (I, J, K) ∈ R_{r}^{n} and all r = 1, 2, …, n − 1. Conversely, c_{λμ}^{ν} is not primitive if there exists any (I, J, K) ∈ R_{r}^{n} with 1 ≤ r < n such that ps (ν)_{K} = ps (λ)_{I} + ps (μ)_{J}.

With this definition, we conjecture that if c_{λμ}^{ν} is positive but not primitive, then c_{λμ}^{ν} factorises. In order to specify the manner in which such a non-primitive Littlewood– Richardson coefficient factorises it is convenient to introduce some further notation. As usual, let n be a fixed positive integer and let N = {1, 2, …, n}. Then for any I = \{i_{1}, i_{2}, …, i_{r}\} ⊆ N, with i_{1} < i_{2} < ⋯ < i_{r} and 1 ≤ r ≤ n, let \overline{I} = N\I be the complement of I in N. In addition, for any partition or weight κ = (κ_{1}, κ_{2}, …, κ_{n}) let κ_{I} = (κ_{i_{1}}, κ_{i_{2}}, …, κ_{i_{r}}). With this notation we make the following:

Conjecture 4.2. Let λ, μ and ν be partitions of lengths ℓ(λ), ℓ(μ), ℓ(ν) ≤ n. If c_{λμ}^{ν} > 0 and there exists proper subsets I, J, K of N with (I, J, K) ∈ R_{r}^{n} such that ps (ν)_{K} = ps (λ)_{I} + ps (μ)_{J} then

(4.1)  c_{λμ}^{ν} = c_{λ_{I}μ_{J}}^{ν_{K}} c_{λ\overline{I}μ\overline{J}}^{ν\overline{K}} .

This means that if any one of Horn’s essential inequalities (2.5) is an equality for 1 ≤ r < n then c_{λμ}^{ν} factorises. Repeated use of the above conjecture would allow any non-vanishing Littlewood–Richardson coefficient to be written as a product of primitive Littlewood– Richardson coefficients. Furthermore, since the partial sum conditions are preserved under scaling by any positive number t, we have the following:

Conjecture 4.3. Let λ, μ and ν be partitions of lengths ℓ(λ), ℓ(μ), ℓ(ν) ≤ n. If c_{λμ}^{ν} > 0 and there exists proper subsets I, J, K of N with (I, J, K) ∈ R_{r}^{n} such that ps (ν)_{K} = ps (λ)_{I} + ps (μ)_{J} then

(4.2)  P_{λμ}^{ν}(t) = P_{λ_{I}μ_{J}}^{ν_{K}} (t) P_{λ\overline{I}μ\overline{J}}^{ν\overline{K}} (t).

The origin of these conjectures can be exposed through a study of the properties of certain puzzles introduced by Knutson et al. [KTW]. These are triangular diagrams on a hive lattice consisting of three elementary pieces: a dark triangle, a light triangle and a shaded rhombus with its edges either dark or light according as they are to the right or left, respectively of an acute angle of the rhombus, when viewed from its interior:

The puzzle is to put these together, oriented in any manner, so as to form a hive shape with all the edges matching. For example, one such puzzle takes the form shown below:

As pointed out by Danilov and Koshevoy [DK], such a puzzle can be simplified, without loss of information, to give a labyrinth or hive plan by deleting all interior edges of the three types of region: corridors in the form of shaded parallelograms consisting of rhombi of just one type, either R1, or R2 or R3, and dark rooms and light rooms that are convex polygons consisting solely of just dark-edged triangles and just light-edged triangles, respectively.

It is a remarkable fact [KTW] that for each positive integer r < n and triple (I, J, K) ∈ R_{r}^{n}, there exists a unique puzzle, and correspondingly a unique hive plan of the above type. In this hive plan the dark edges on the boundary are those specified by I, J and K. In connection with the above Conjecture 4.2, the thick edges on the boundary of each LR-hive are then labelled by the parts of λ_{I}, μ_{J} and ν_{K}, and the thin edges by the parts of λ\overline{I}, μ\overline{J} and ν\overline{K}.

In the example illustrated, for which n = 5, r = 3, I = {1, 2, 4}, J = {2, 3, 4}, K = {2, 3, 5}, we have α(I) = (1, 0, 0), β(J) = (1, 1, 1) and γ(K) = (2, 1, 1). The fact that (I, J, K) ∈ R_{3}^{5} then follows from the observation that c_{1,111}^{211} = 1. Superposing the corresponding hive plan on the LR-hives with boundaries specified by λ, μ and ν then gives

0  0 1 1  1 ν^{2}  ν^{3} ν^{1}  μ_{2}  μ_{4}  μ_{5} μ_{3} ν^{4}  ν^{5} λ_{3} λ_{2} λ_{1}  λ_{4}  λ_{5}  μ_{1}

The validity of Conjecture 4.2 would imply that if

(4.3)  ν_{2} + ν_{3} + ν_{5} = λ_{1} + λ_{2} + λ_{4} + μ_{2} + μ_{3} + μ_{4}.

then c_{λμ}^{ν} must factorise as follows

(4.4)  c_{λμ}^{ν} = c_{(λ_{1},λ_{2},λ_{4}),(μ_{2},μ_{3},μ_{4})}^{(ν_{2},ν_{3},ν_{5})} c_{(λ_{3},λ_{5}),(μ_{1},μ_{5})}^{(ν_{1},ν_{4})}

To see how this comes about one just deletes the corridors from the initial LR-hive and glues together all the dark rooms, labelled 0, and all the light rooms, labelled 1, to create two smaller LR-hives, as shown below:

0  0 ν^{2}  ν^{3}  ν^{5} μ_{2} μ_{3} λ_{1}  1  1 1  ν_{4} λ_{4} λ_{2}  μ_{4}  ν_{1}  μ_{1}  μ_{5} λ_{5} λ_{3}

To prove the validity of such a factorisation, one has to show that the Horn equality (4.3) leads to a bijection between all the large LR-hives and all pairs of small LR-hives obtained by the deletion and glueing processes. As a first step one observes that the application of the LR-hive conditions to any puzzle leads directly to a Horn inequality.

To continue with our example, interior edge labels may be introduced as shown below.

ν^{2}  ν^{3} ν^{1}  μ_{2}  μ_{4}  μ_{5} μ_{3} ν^{4}  ν^{5} λ_{3} λ_{2} λ_{1}  λ_{4}  λ_{5}  μ_{1} α_{3}  α_{4} β_{3} β_{4} γ_{1} γ_{2}  γ_{4} γ_{3} α_{1}  β_{2}  α_{5} β_{5} β_{1} α_{2}

The successive application of the LR-hive conditions to each shaded sub-rhombus of the above puzzle gives in the case of dark edge inequalities:

ν_{2} + ν_{3} + ν_{5} ≤ (ν_{2} + ν_{3}) + γ_{4} = (α_{1} + α_{2} + β_{1} + β_{2}) + γ_{4} (4.5)

≤ λ_{1} + α_{2} + β_{1} + β_{2} + γ_{4} ≤ λ_{1} + λ_{2} + β_{1} + β_{2} + γ_{4}

≤ λ_{1} + λ_{2} + β_{3} + β_{2} + γ_{4} ≤ λ_{1} + λ_{2} + (β_{3} + β_{4} + γ_{4})
= λ_{1} + λ_{2} + (α_{4} + μ_{2} + μ_{3} + μ_{4}) ≤ λ_{1} + λ_{2} + λ_{4} + μ_{2} + μ_{3} + μ_{4} ,

where the intermediate equalities are just expressions of the fact that sums of any combination of positive edge lengths between any two fixed points are always the same. The result, as claimed quite generally, is a Horn inequality. In fact [KTW] all Horn inequalities, both essential and inessential, may be derived in this way from puzzles.

The same procedure applied to light edge inequalities gives

ν_{1} + ν_{4} ≥ γ_{1} + ν_{4} = γ_{1} + (α_{5} + β_{5}) (4.6)

≥ γ_{1} + α_{3} + β_{5} ≥ (γ_{1} + α_{3}) + μ_{5} = (λ_{3} + γ_{2}) + μ_{5}
≥ λ_{3} + γ_{3} + μ_{5} = λ_{3} + (λ_{5} + μ_{1}) + μ_{5} .

This is the complement of the Horn inequality (4.5) with respect to the identity |ν| = |λ| + |μ|.

Clearly, if any Horn inequality is saturated, that is to say becomes an equality, then all of the individual inequalities arising in its derivation are also saturated, as well as the individual inequalities in its complement. In our example, this means that if the condition (4.3) is satisfied then we must have ν_{5} = γ_{4}, α_{1} = λ_{1}, α_{2} = λ_{2}, β_{1} = β_{3}, β_{2} = β_{4} and α_{4} = λ_{4}, from (4.5),and ν_{1} = γ_{1}, α_{5} = α_{3}, β_{5} = μ_{5} and γ_{2} = γ_{3}, from (4.6).The degrees of freedom are thereby greatly reduced, as shown in the following diagram:

ν^{2}  ν^{3} ν^{1}  μ_{2}  μ_{4}  μ_{5} μ_{3} ν^{4}  ν^{5} λ_{3} λ_{2} λ_{1}  λ_{4}  λ_{5}  μ_{1} α_{3}  λ_{4} β_{1} β_{2} ν_{1} γ_{2}  ν_{5} γ_{2} λ_{1}  β_{2}  α_{3} μ_{5} β_{1} λ_{2}

In this example, it is not difficult to see that the corridors, that is the shaded parallelograms, are completely redundant, and that the enumeration of all possible large LR-hives is accomplished by enumerating pairs of small LR-hives corresponding to the diagrams:

ν^{2}  ν^{3}  ν^{5} μ_{2} μ_{3}  ν_{4} λ_{4}  μ_{4}  ν_{1}  μ_{1} β_{2}  α_{3} β_{1}  γ_{2} λ_{2}  λ_{3}  μ_{5} λ_{5} λ_{1}

This proves the factorisation of not only the corresponding Littlewood–Richardson coefficients, but also the corresponding LR-polynomials, since simultaneous stretching of the partitions, λ, μ and ν, always preserves the saturation of the Horn inequality.

An explicit illustration of the above factorisation is provided by the case λ = (9, 7, 6, 2, 0), μ = (13, 5, 3, 1, 0) and ν = (14, 12, 11, 5, 4) for which λ_{I} = (9, 7, 2), μ_{J} = (5, 3, 1) and ν_{K} = (12, 11, 4) with λ\overline{I} = (6, 0), μ\overline{J} = (13, 0) and ν\overline{K} = (14, 5). In this case

(4.7)  c_{9762,13 531}^{14 12 11 54} = c_{972,531}^{12 11 4} c_{6,13}^{14 5} = 2 · 1 = 2,

while

(4.8)  P_{9762,13 531}^{14 12 11 54}(t) = P_{972,531}^{12 11 4}(t) P_{6,13}^{14 5}(t) = (t + 1) · 1 = t + 1.

More generally, to complete the proof of the Conjecture 4.2 it is necessary to show that the corridors R_{n} of an LR-hive, H_{n}, are redundant; that the removal of R_{n} yields dark rooms and light rooms that constitute LR-hives H_{r} and H_{n−r}, respectively; and that any LR-hives H_{r} and H_{n−r} that are first subdivided and then joined by corridors R_{n} constitute some LR-hive H_{n}.

The redundancy of the corridors is rather easily established by showing that the corresponding Horn equality is sufficient to ensure that all their interior edge labels are fixed by those on their boundary. It is then not difficult to show that the LR hive conditions for H_{n} imply the validity of the LR hive conditions for any rhombus of either H_{r} or H_{n−r} that is split by a corridor in H_{n}. To complete the proof it is necessary to show, conversely, that the LR hive conditions of H_{r} and H_{n−r} are sufficient to imply the LR hive conditions of H_{n} for all rhombi that are split by a redundant corridor. It is believed that this may be accomplished, under the hypotheses of the Conjecture, by a generalisation of the arguments used elsewhere [KTT2] in proving factorisation of some Kostka coefficients. However, in the present context, it should be noted that the required result is not true in the case of all rhombi of H_{n} that are split by a redundant corridor arising from a puzzle associated with the saturation of an inessential Horn inequality. This is connected with the fact that in such cases the puzzle itself is not unique [KTW]. It is for this reason that the Conjecture 4.2 applies only to the saturation of an essential Horn inequality, for which the corresponding puzzle is known to be unique [KTW], and the corresponding Littlewood–Richardson coefficient is not primitive.

5. Degrees of stretched polynomials

Even given a certain amount of factorisation that reduces the evaluation of stretched Littlewood–Richardson polynomials to that of calculating these LR-polynomials in the primitive case, their evaluation may be combinatorially formidable. In any given case a knowledge of the degree of the polynomial would be extremely advantageous. Here we establish an upper bound on this degree by means of the following rather innocuous looking observation.

Taking α = γ in each of the 5-vertex diagrams encountered earlier, gives

β  α  α  α  β  α  α  α  β

In each case the rhombus constraints give α ≥ β ≥ α so that we must have β = α. This result can be displayed more simply by suppressing all the labels on the vertices of the hives and inserting an edge between pairs of vertices whose labels differ by the same integer α. This gives the diagrams:

α  α  α  α  α  α  α  α  α

where in each case the equality of neighbouring differences α in a linear sequence of three vertices forces an identical difference α between two vertices in the neighbouring line.

Applying these notions to our LR-hives with boundaries of length n and with border labels determined by λ, μ and ν, it follows from the above that any equalities of successive parts of these partitions propagate as equalities of differences in hive entries within each LR-hive. To be more precise let all the λ-boundary edges be labelled by the parts of λ. If any sequence of parts of λ share the same value, say α, then we can identify an equilateral sub-hive having the sequence of equally labelled edges as one boundary, with its other boundaries parallel to the μ and ν-boundaries of the original hive. Within this sub-hive all the vertices along lines parallel to the λ-boundary are to be connected by edges indicating that in any LR-hive the differences in values between neighbouring entries along these lines are all α. This process is to be repeated first for all sequences of equal edge labels along the λ-boundary, and then for all sequences of equal edge labels along the μ and ν boundaries.

In some cases it will be found that some sequence of equal edge labels, say α parallel to the λ-boundary, will intersect some sequence of equal edge labels, say β parallel to the μ-boundary. In such a case, by virtue of the condition α + β = γ that applies to each of the triangles

α  γ  β

there must exist sequences of equal edge labels γ = α + β parallel to the ν-boundary. Depending on the lengths of the intersecting α and β sequences, either a triangular or a quadrilateral region will be formed in which each edge label is either α, β or γ. By virtue of the previous arguments, any sequence of equal edge labels γ on the boundary of such a region will give rise to a further triangular region traversed by equal edge labels γ. This is exemplified by:

α α α α  β β β α γ  γ γ  α α

Clearly, different orientations of such regions may occur and there may be several such intersections with which one has to contend. However, the process of equal edge identification will terminate. Finally, when this has happened, one connects with edges all neighbouring vertices on all three boundaries of the hive. In this way we arrive at a skeletal graph G_{n;λμν} of the hive.

In the case of the example quoted in the Introduction, we have n = 7, λ = (4, 3, 3, 2, 1, 0, 0), μ = (4, 3, 2, 2, 1, 0, 0) and ν = (7, 4, 4, 4, 3, 2, 1), and the corresponding skeletal graph G_{n;λμν} takes the form:

4 7 3  3 4 2  1 4 0  0 4 4  3 3 2  2 2 1  0 1 0

The importance of such skeletal graphs is that they indicate constraints on LR-hive entries that are implied by the specification of the boundary labels. These constraints on the interior vertex labels reduce the total number of degrees of freedom of such labels. This leads to the following:

Proposition 5.1. Let λ, μ and ν be partitions such that c_{λμ}^{ν} > 0. Let deg(P (t)) be the degree of the corresponding stretched LR-polynomial P (t) = c_{tλ,tμ}^{tν}. Let d(G_{n;λμν}) be the number of connected interior components of the graph G_{n;λμν} that are not connected to the boundary. Then

(5.1)  deg(P (t)) ≤ d(G_{n;λμν}).

Proof. The application of the stretching parameter t leaves G_{n;λμν} unaltered, so that the number of degrees of freedom in assigning entries to the stretched LR-hives is still d(G_{n;λμν}). For each interior connected component that is not connected to the boundary we can select any one convenient vertex. The value a_{ij} of each such selected interior vertex label may or may not be fixed by the hive constraints. However, it will be subject to linear inequalities of the form p ≤ a_{ij} ≤ q arising from the hive conditions. As the boundary vertex and edge labels are scaled by t, then all the parameters specifying these linear inequalities are also scaled by t to give tp ≤ a_{ij} ≤ tq. Hence, in enumerating all possible LR-hives in the stretched case, the freedom in assigning a_{ij} gives rise to a contribution to P_{λμ}(t) that is at most linear in t. It follows that the degree of this polynomial is at most d(G_{n;λμν}). □

Unfortunately, the intersection of sequences of equal edges that arise from equal parts in λ, μ and ν and the resulting new interior sequences of equal edges make it difficult to arrive at an explicit formula for d(G_{n;λμν}).

In the above example for n = 7 with λ = (4, 3, 3, 2, 1, 0, 0), μ = (4, 3, 2, 2, 1, 0, 0) and ν = (7, 4, 4, 4, 3, 2, 1) we have d(G_{n;λμν}) = 8. The corresponding LR-polynomial P_{λμ}^{ν}(t) is given explicitly in (1.3), and can be seen to have degree 8. Thus, in the case of this example, the above bound (5.1) on the polynomial degree is saturated.

Similarly, in the case n = 6 and λ = (7, 6, 5, 4, 0, 0), μ = (7, 7, 7, 4, 0, 0) and ν = (12, 8, 8, 7, 6, 4, 2), the graph G_{n;λμν} takes the form:

12  7 6  5 7  4 0 0 4  0  7  7  7  4  0  0  0 6 8  8  2

As can be seen, there are 5 connected interior components of the above graph that are not connected to the boundary. It follows that d(G_{n;λμν}) = 5. It can be checked that in the case of this example c_{λμ}^{ν} = 12 and [NTB]:

(5.2)  P_{λμ}^{ν}(t) = \frac{1}{30}(t + 1)(t + 2)(t + 3)(3t^{2} + 7t + 5) .

Thus once again we have deg(P_{λμ}^{ν}(t)) = d(G_{n;λμν}).

On the other hand, in the case n = 5 and λ = (9, 7, 3, 0, 0), μ = (9, 9, 3, 2, 0) and ν = (10, 9, 9, 8, 6), the graph G_{n;λμν} takes the form:

10  8 7  3 9  0  6 9  9 0  9  9  3  2  0

This time there are 3 connected interior components that are not connected to the boundary. Hence d(G_{n;λμν}) = 3. However, in this case it is found that c_{λμ}^{ν} = 2 and P_{λμ}^{ν}(t) = t + 1. Hence deg(P_{λμ}^{ν}(t)) < d(G_{n;λμν}). However, this case is not primitive. The corresponding hives factorise:

10  9  8 9  2 9  0 7  0  6 3  3  0  9 9

leading to a corresponding factorisation of the LR-polynomial:

(5.3)  P_{97300,99320}^{10 9986}(t) = P_{970,920}^{10 98}(t) P_{3,3}^{6}(t) P_{0,9}^{9}(t) = (t + 1) · 1 · 1 = t + 1.

Encouraged by these results, and many other examples, we conjecture that in the primitive case the bound in Proposition 5.1 is saturated, and that this is true only in such cases. That is we have:

Conjecture 5.2. If c_{λμ}^{ν} is primitive and P_{λμ}^{ν}(t) = c_{tλ,tμ}^{tν} then

(5.4)  deg(P (t)) = d(G_{n;λμν}),

and conversely, if deg(P_{λμ}^{ν}(t)) < d(G_{n;λμν}) then c_{λμ}^{ν} is not-primitive.

6. Linear factors

It will have been noted that in our illustrative examples (1.3) and (5.2) the stretched Littlewood–Richardson polynomials P_{λμ}^{ν}(t) contain factors (t + m) for some sequence of values m = 1, 2, …, M for some positive integer M. This is no accident since P_{λμ}^{ν}(t) is nothing other than an Ehrhart quasi-polynomial i(P, t) of a rational complex polytope P defined by the set of linear inequalities corresponding to the LR-hive conditions. This quasi-polynomial is actually a polynomial [DW2, R], but whether this is the case or not, the reciprocity theorem for Ehrhart quasi-polynomials [S] states that i(P, t) is defined for all integers t and that for t = −m with m a positive integer i(P, −m) = (−1)^{d} \overline{i}(P, m), where d is the dimension of the polytope P, and \overline{i}(P, m) is the number of integer points inside mP. This number of integer points may be zero, thereby giving rise to a zero of P (t) = i(P, t) at t = −m. Moreover, if this number is zero for m = M and non-zero for m = M + 1 it follows from its geometric interpretation that it is zero for m = 1, 2, …, M and non-zero for all m > M. In such a case P_{λμ}^{ν}(t) necessarily contains (t + 1)(t + 2) ⋯ (t + M) as a factor.

In this section we describe one particular approach to the determination of M, based on a conjecture regarding the continuation of P_{λμ}^{ν}(t) to negative integer values t = −m. For t a positive integer, we certainly have

(6.1)  s_{tλ}(x_{1}, x_{2}, …, x_{n}) = \frac{|x_{i}^{tλ_{j}+n−j}|}{|x_{i}^{n−j}|}.

This may be readily extended to the case t = −m with m a positive integer, to give

(6.2)  s_{−mλ}(x_{1}, x_{2}, …, x_{n}) = \frac{|x_{i}^{−mλ_{j}+n−j}|}{|x_{i}^{n−j}|} = \frac{|x_{i}^{−mλ_{n−k+1}−n+k}|}{|x_{i}^{−n+k}|},

where first x_{i}^{n−1} has been extracted as a common factor from the ith row of each determinant for i = 1, 2, …, n and cancelled from numerator and denominator, and then j replaced by k = n − j + 1 with an appropriate reversal of order of the columns in both determinants. If we now set \overline{x}_{i} = x_{i}^{−1} for i = 1, 2, …, n, this gives

(6.3)  s_{−mλ}(x_{1}, x_{2}, …, x_{n}) = \begin{matrix}| & \overline{x} & {mλ_{n−k+1}+n−k \atop i} & | \\ | & \overline{x} & {n−k \atop i} & | \end{matrix} = s_{mλ_{n},...,mλ_{2},mλ_{1}}(\overline{x}_{1}, \overline{x}_{2}, …, \overline{x}_{n}).

To simplify the notation, for any partition λ = (λ_{1}, λ_{2}, …, λ_{n}) let λ̃ = (λ_{n}, …, λ_{2}, λ_{1}) be the vector obtained by reversing the order of its parts. Then reverting to the indeterminates x = (x_{1}, x_{2}, …, x_{n}) we have:

(6.4)  s_{mλ̃}(x) = s_{mλ_{n},...,mλ_{2},mλ_{1}}(x_{1}, x_{2}, …, x_{n}) = \frac{|x_{i}^{mλ_{n−k+1}+n−k}|}{|x_{i}^{n−k}|}.

This allows us to make the following definition, which amounts to an extension of stretched Littlewood–Richardson coefficients to the domain of a negative stretching parameter t = −m:

Definition 6.1. For any λ, μ and ν such that c_{λμ}^{ν} > 0, let c_{−mλ,−mμ}^{−mν} = c_{mλ̃,mμ̃}^{mν̃}, for any positive integer m, where

(6.5)  s_{mλ̃}(x) s_{mμ̃}(x) = ∑_{ν} c_{mλ̃,mμ̃}^{mν̃} s_{mν̃}(x).

It transpires that in the following we need to refine the notion of primitivity. If c_{λμ}^{ν} > 0 is not only primitive but satisfies the stronger constraint that all the Horn inequalities, both essential and inessential, are strict inequalities, then c_{λμ}^{ν} is said to be simple.

With this definition, the consideration of numerous examples, suggests the validity of the following:

Conjecture 6.2. Let c_{λμ}^{ν} > 0 be simple and let the corresponding LR-polynomial be P_{λμ}^{ν}(t). Then the value of this LR-polynomial at negative integer values t = −m coincides with the corresponding negatively stretched Littlewood–Richardson coefficients, that is to say

(6.6)  P_{λμ}^{ν}(−m) = c_{−mλ,−mμ}^{−mν}.

To exploit this it is necessary that Schur functions such as s_{mλ̃}(x), as defined by (6.4), be standardised. This may be carried out by reordering the columns of the numerator determinant. However there are two quite different possible outcomes: either s_{mλ̃}(x) = 0 or s_{mλ̃}(x) = η_{ρ} s_{ρ}(x) for some partition ρ with η_{ρ} = ±1. Similar results apply to s_{mμ̃}(x) and s_{mν̃}(x). The validity of the above conjecture would then imply that

(6.7)  P_{λμ}^{ν}(−m) = η_{λμ}^{ν}c_{ρσ}^{τ}

where η_{λμ}^{ν} = 0 if any one of s_{mλ̃}(x), s_{mμ̃}(x) or s_{mν̃}(x) is identically zero, and is ±1 in all other cases, while ρ, σ and τ are defined by the identities s_{mλ̃}(x) = η_{ρ} s_{ρ}(x), s_{mμ̃}(x) = η_{σ} s_{σ}(x) and s_{mν̃}(x) = η_{τ} s_{τ}(x).

It follows that we can expect two types of zero of P_{λμ}^{ν}(t) for t = −m: type (i) associated with η_{λμ}^{ν} = 0 and type (ii) associated with the vanishing of c_{ρσ}^{τ}.

To see this in an example consider the case n = 7, λ = (4, 3, 3, 2, 1), μ = (4, 3, 2, 2, 1) and ν = (7, 4, 4, 4, 3, 2, 1) for which c_{λμ}^{ν} is simple, and P (t) = P_{λμ}^{ν}(t) has already been given in (1.3). Here we find that s_{mλ̃}(x) = 0 for m = 1, 2, s_{mμ̃}(x) = 0 for m = 1, 2 and s_{mν̃}(x) = 0 for m = 1, 2, 3. This accounts for the three zeros associated with the factors (t + 1), (t + 2) and (t + 3). For all m ≥ 4 we have s_{mλ̃}(x) = s_{ρ}(x), s_{mμ̃}(x) = s_{σ}(x) and s_{mν̃}(x) = s_{τ}(x) for some partitions ρ, σ and τ. It then remains to be seen whether or not c_{ρσ}^{τ} = 0.

Starting with m = 4 it is found that ρ = (10, 9, 9, 8, 6, 5, 5), σ = (10, 8, 7, 7, 6, 5, 5) and τ = (22, 14, 14, 14, 14, 12, 10). Since ρ_{1} + σ_{1} = 20 < 22 = τ_{1} it follows that c_{ρσ}^{τ} = 0. This accounts for a factor of (t + 4) in P (t). Similarly with m = 5 it is found that ρ = (14, 12, 12, 10, 7, 5, 5), σ = (14, 12, 9, 9, 7, 5, 5) and τ = (29, 18, 18, 18, 17, 14, 11). This time since ρ_{1} + σ_{1} = 28 < 29 = τ_{1} it again follows that c_{ρσ}^{τ} = 0, thereby accounting for a factor of (t + 5) in P (t). On the other hand for m = 6 it is found that ρ = (18, 15, 15, 12, 8, 5, 5), σ = (18, 14, 11, 11, 8, 5, 5) and τ = (36, 22, 22, 22, 20, 16, 12). This time it is found that c_{ρσ}^{τ} = 3. This implies that there is no factor (t + 6) in P (t). Indeed it is easy to check from (1.3) that P (−6) = 3. In the same way we can derive the fact that P (−7) = 39 and P (−8) = 247, in perfect agreement with (1.3).

Although Conjecture 6.2 cannot be extended as it stands to cover all primitive cases, both simple and non-simple, numerous examples lead us to

Conjecture 6.3. If c_{λμ}^{ν} > 0 is primitive, then the LR-polynomial P_{λμ}^{ν}(t) = c_{tλ,tμ}^{tν} contains a factor (t + m) if and only if either η_{λμ}^{ν} = 0 or c_{ρσ}^{τ} = 0.

It can be shown that for sufficiently large m both η_{λμ}^{ν} and c_{ρσ}^{τ} in (6.7) are positive, provided that the original c_{λμ}^{ν} is primitive. Moreover, it can be shown in such a case that if η_{λμ}^{ν}c_{ρσ}^{τ} = 0 for some positive integer m, then the same is true for all smaller positive integers. This means that it is possible to identify M such that the right hand side of (6.7) is zero for all m ≤ M and non-zero for all m > M. This is entirely consistent with the remarks made at the beginning of this section regarding the zeros of Ehrhart quasi-polynomials.

As a final conjecture we offer

Conjecture 6.4. Let λ, μ and ν be partitions such that c_{λμ}^{ν} > 0. Then c_{λμ}^{ν} is primitive if and only if c_{−mλ,−mμ}^{−mν} is non-zero for some positive integer m.

References

[BZ1] A.D. Berenstein and A.V. Zelevinsky, When is the multiplicity of a weight equal to 1?, Funct. Anal. Appl. 24 (1990), 259–269.

[BZ2] A.D. Berenstein and A.V. Zelevinsky, Triple multiplicities for sl(r + 1) and the spectrum of the exterior algebra of the adjoint representation, J. Alg. Comb. 1 (1992), 7–22.

[B] A.S. Buch, The saturation conjecture (after A. Knutson and T. Tao). With an appendix by W. Fulton, Enseign. Math. 46 (2000), 43–60.

[DK] V.I. Danilov and G.A. Koshevoy, Diskretnaya vognutost’ i ermitovy matritsy, Trudy Math. Inst. Steklova 241 (2003), 68–90, in Russian. Title translation: Discrete convexity and Hermitian matrices.

[DW1] H. Derksen and J. Weyman, Semi-invariants of quivers and saturation for Littlewood–Richardson coefficients, J. Amer. Math. Soc. 13 (2000), 467–479.

[DW2] H. Derksen and J. Weyman, On the Littlewood–Richardson polynomials, J. Algebra. 255 (2002), 247–257.

[H] A. Horn, Eigenvalues of sums of Hermitian matrices, Pacific J. Math. 12 (1962), 225–241.

[F] W. Fulton, Eigenvalues, invariant factors, highest weights, and Schubert calculus, Bull. Amer. Math. Soc. 37 (2000), 209–249.

[KTT1] R.C. King, C. Tollu and F. Toumazet, Stretched Littlewood–Richardson and Kostka coefficients, CRM Proceedings and Lecture Notes, Vol. 34, Amer. Math. Soc, 2004, pp. 99–112.

[KTT2] R.C. King, C. Tollu and F. Toumazet, The hive model and the factorisation of Kostka coefficients, Proc. FPSAC’05, 2005.

[K] A.A.Klyachko, Stable bundles, representation theory and Hermitian operators, Selecta Math. New Ser. 4 (1998), 419–445.

[KT] A. Knutson and T. Tao, The honeycomb model of GL_{n}(ℂ) tensor products. I: Proof of the saturation conjecture, J. Amer. Math. Soc. 12 (1999), 1055–1090.

[KTW] A. Knutson, T. Tao and C. Woodward, The honeycomb model of GL_{n}(ℂ) tensor products. II: Puzzles determine facets of the Littlewood–Richardson cone, J. Amer. Math. Soc. 17 (2004), 19–48.

[LR] D.E. Littlewood and A. Richardson, Group characters and algebra, Phil. Trans. Roy. Soc. London A 233 (1934), 99–141.

[NTB] J. Nzeutchap, F. Toumazet and F. Butelle, Kostka numbers and Littlewood–Richardson coefficients: distributed computation, in Proceedings of the Brian Wybourne Commemorative Meeting, Eds: R.C.King, J. Karwowski and M. Bylicki, to appear.

[R] E. Rassart, A polynomial property of Littlewood–Richardson coefficients, J Comb. Theo. Ser. A 107 (2004), 161–179.

[S] R.P. Stanley, Enumerative Combinatorics, Vol. I, Cambridge University Press, Cambridge, 1999.

School of Mathematics, University of Southampton, Southampton SO17 1BJ, U.K.

  E-mail address: R.C.King@soton.ac.uk

Laboratoire d’Informatique de Paris-Nord, CNRS UMR 7030, Université Paris 13, 93430 Villetaneuse, France

  E-mail address: ct@lipn.univ-paris13.fr

Laboratoire d’Informatique de Paris-Nord, CNRS UMR 7030, Université Paris 13, 93430 Villetaneuse, France

  E-mail address: ft@lipn.univ-paris13.fr