Plane partitions and characters of the symmetric group

Ernesto Vallejo^{1}

Instituto de Matemáticas Universidad Nacional Autónoma de México Area de la Inv. Cient., 04510 México, D.F., MEXICO e-mail: evallejo@matem.unam.mx

Abstract

In this paper we show that the existence of plane partitions, which are minimal in a sense to be defined, yields minimal irreducible summands in the Kronecker product χ^{λ} ⊗ χ^{μ} of two irreducible characters of the symmetric group S(n). The minimality of the summands refers to the dominance order of partitions of n. The multiplicity of a minimal summand χ^{ν} equals the number of pairs of Littlewood-Richardson multitableaux of shape (λ, μ), conjugate content and type ν. We also give lower and upper bounds for these numbers.

1 Introduction

The Kronecker product χ^{λ} ⊗ χ^{μ} of two irreducible characters of the symmetric group S(n) is in general a reducible character of S(n). The multiplicity c(λ, μ, ν) of an irreducible character χ^{ν} in the product χ^{λ} ⊗ χ^{μ} can be described by a simple formula which follows from the orthogonality relations, and goes back at least to Murnaghan [15, p.765]

c(λ, μ, ν) = \frac{1}{n!} ∑_{σ∈S(n)} χ^{λ}(σ)χ^{μ}(σ)χ^{ν}(σ).

This formula has the virtue of showing the symmetry of c(λ, μ, ν) in λ, μ, ν. However, it doesn’t help too much when one wants to compute c(λ, μ, ν) explicitly, or even to decide whether c(λ, μ, ν) is different from zero for some particular choices of λ, μ, ν. Methods for computing c(λ, μ, ν) are described in [15, 13, 11, 10, 5, 6, 27]. Explicit formulas for c(λ, μ, ν) can be obtained, basically from the Littlewood-Richardson rule, for arbitrary λ, μ, and the simplest choices of ν, see for example [15, 13, 23, 28, 27]. Other formulas have been found when each of λ and μ is either a hook partition or a partition with two parts, and ν is arbitrary by Remmel and Whitehead [17, 18, 19]; and when λ, μ, ν are rectangular partitions by Clausen and Meier [2]. They also described an algorithm that produces the maximal sumand of χ^{λ} ⊗ χ^{μ} in the lexicographic order, either by rows or by columns.

1Supported by DGAPA IN103397

In this paper we show that the existence of plane partitions which are minimal in a certain sense yields minimal summands of χ^{λ} ⊗ χ^{μ} in the dominance order. The multiplicity of the minimal summands has a combinatorial description in terms of pairs of Littlewood-Richardson multitableaux. More precisely:

Let λ, μ be partitions of n. We denote by M(λ, μ) the set of matrices A with non-negative integer coefficients of size ℓ(λ) × ℓ(μ) such that its i-th row sums λ_{i}, and its j-th column sums μ_{j}. Given A ∈ M(λ, μ), we denote by π(A) the partition of n obtained from A by ordering its entries decreasingly. We recall that a matrix with non-negative integer coefficients is called a plane partition if its rows and columns are weakly decreasing. For any partition ν of n we define

a(λ, μ; ν) := |{A ∈ M(λ, μ) | π(A) = ν}|

and

p(λ, μ; ν) := |{A ∈ M(λ, μ) | π(A) = ν and A is a plane partition}|.

We denote by ⊴ the dominance order of partitions, see [1, 11, 22]. We say that a matrix A is minimal in M(λ, μ) if A ∈ M(λ, μ), and it does not exist B ∈ M(λ, μ) with π(B) ⊲ π(A). We also say that ν is minimal for χ^{λ} ⊗ χ^{μ} if c(λ, μ, ν) ≠ 0 and c(λ, μ, γ) = 0 for all γ ⊲ ν. Finally let lr^{∗}(λ, μ; ν) denote the number of pairs of Littlewood-Richardson multitableaux of shape (λ, μ), conjugate content and type ν, see (7). Then we have

1.1. Theorem. Let M be a minimal matrix in M(λ, μ), and let ν = π(M). Suppose M is a plane partition. Then

(1) ν is minimal for χ^{λ} ⊗ χ^{μ}.

(2) c(λ, μ, ν) = lr^{∗}(λ, μ; ν′).

(3) p(λ, μ; ν) ≤ c(λ, μ, ν) ≤ a(λ, μ; ν).

(4) c(α, β, γ) = 0 for all α ⊵ λ, β ⊵ μ, and γ ⊲ ν.

(5) c(λ, μ, ν) = a(λ, μ; ν), if and only if c(α, β, ν) = 0 for all α ⊵ λ, β ⊵ μ such that (α, β) ≠ (λ, μ).

The paper is organized as follows. In section 2 we review the definitions and results needed to prove our theorem. Section 3 contains a sequence of results which lead to the proof of Theorem 1.1; some of them may be of interest by themselves. In section 4 we go back to the origins of this work: we show how a notion comming from discrete tomography, that of set of uniqueness, yields information about some c(λ, μ, ν)’s.

2 Definitions and known results

Let λ be a partition of n, in symbols λ ⊢ n. We denote by |λ| the sum of its parts, by ℓ(λ) the number of its parts, and by λ′ its conjugate partition. We use the notation λ⊵μ to indicate that λ is greater or equal than μ in the dominance order of partitions, see [1, 11, 22]. Let H be a subgroup of a group G. If χ is a character of H, we denote by Ind_{H}^{G}(χ) the character induced from χ. For any partition λ of n, let S(λ) denote a Young subgroup of S(n) corresponding to λ, χ^{λ} the irreducible character of S(n) associated to λ, and ϕ^{λ} = Ind_{S(λ)}^{S(n)}(1_{λ}) the permutation character associated to λ. They are related by the Young’s rule

ϕ^{λ} = ∑_{α⊵λ}K_{αλ} χ^{α},  (1)

where K_{αλ} is a Kostka number, that is, the number of semistandard tableaux of shape α and content λ, see [11, 2.8.5], [22, §2.11]. Remember that if α ⊵ λ, then K_{αλ} > 0 and that K_{λλ} = 1. We use the symbol < · , · > for the inner product of characters.

Let λ, μ, ν be partitions of n. We denote by M(λ, μ) the set of matrices with nonnegative integer coefficients of size ℓ(λ)×ℓ(μ), with row sum vector λ, and column sum vector μ; by M^{∗}(λ, μ) the subset of M(λ, μ) formed by all matrices whose coefficients are zeros or ones; and by M^{∗}(λ, μ, ν) the set of all 3-dimensional matrices A = (a_{ijk}) of size ℓ(λ) × ℓ(μ) × ℓ(ν), whose entries are zeros or ones, and have plane sum vectors λ, μ, ν, that is,

∑_{jk} a_{ijk} = λ_{i}, 1 ≤ i ≤ ℓ(λ),
∑_{ik} a_{ijk} = μ_{j}, 1 ≤ j ≤ ℓ(μ),
∑_{ij} a_{ijk} = ν_{k}, 1 ≤ k ≤ ℓ(ν).

Finally let m^{∗}(λ, μ) := |M^{∗}(λ, μ)|, and m^{∗}(λ, μ, ν) := |M^{∗}(λ, μ, ν)|. These numbers can be expressed as inner products of characters:

m^{∗}(λ, μ) = ⟨ϕ^{λ} ⊗ ϕ^{μ}, χ^{(1^{n})}⟩ ,  (2)
m^{∗}(λ, μ, ν) = ⟨ϕ^{λ} ⊗ ϕ^{μ} ⊗ ϕ^{ν}, χ^{(1^{n})}⟩ ,  (3)

see [3, 4, 11, 24]. The Gale-Ryser theorem gives a characterization for the existence of matrices in M^{∗}(λ, μ):

m^{∗}(λ, μ) > 0 ⟺ λ′ ⊵ μ,  (4)

see [9, 20, 21]. We also have a characterization for uniqueness:

m^{∗}(λ, μ) = 1 ⟺ λ′ = μ,  (5)

see [21, 24, 12]. For any matrix A with non-negative integer coefficients, let π(A) denote the partition obtained from A by ordering its entries decreasingly. Then

ϕ^{λ} ⊗ ϕ^{μ} = ∑_{A∈M(λ,μ)} ϕ^{π(A)},

see [4, 11]. We will denote a(λ, μ; δ) := |{A ∈ M(λ, μ) | π(A) = δ}|, and so we rewrite the preceding formula in the following way

ϕ^{λ} ⊗ ϕ^{μ} = ∑_{δ⊢n} a(λ, μ; δ) ϕ^{δ}.  (6)

For any tableau T (a skew diagram filled with positive integers) there is a word w(T) associated to T given by reading the numbers in T from right to left, in succesive rows, starting with the top row. Let ν be a partition of n of length r. Let ρ(i) ⊢ ν_{i}, 1 ≤ i ≤ r. A sequence T = (T_{1}, …, T_{r}) of tableaux is called a Littlewood-Richardson multitableau of shape λ, content (ρ(1), …, ρ(r)) and type ν if

(i) There exists a sequence of partitions

0 = λ(0) ⊂ λ(1) ⊂ ⋯ ⊂ λ(r) = λ,

such that |λ(i)/λ(i − 1)| = ν_{i} for all 1 ≤ i ≤ r, and

(ii) for all 1 ≤ i ≤ r, T_{i} is a semistandard tableau of shape λ(i)/λ(i−1) and content ρ(i) such that w(T_{i}) is a lattice permutation, see [11, 2.8.13], [14, I.9], [22, §4.9].

For each partition λ of n let c_{(ρ(1),...,ρ(r))}^{λ} denote the number of Littlewood-Richardson multitableaux of shape λ and content (ρ(1), …, ρ(r)). Let

lr^{∗}(λ, μ; ν) := ∑_{ρ(1)⊢ν_{1},...,ρ(r)⊢ν_{r}} c_{(ρ(1),...,ρ(r))}^{λ} c_{(ρ(1)′,...,ρ(r)′)}^{μ}  (7)

be the number of pairs (S, T) of Littlewood-Richardson multitableaux of shape (λ, μ) and type ν, such that S and T have conjugate content, that is, if S has content (ρ(1), …, ρ(r)), then T has content (ρ(1)′, …, ρ(r)′). Then by applying Frobenius reciprocity to ⟨χ^{λ} ⊗ χ^{μ}, ϕ^{ν} ⊗ χ^{(1^{n})}⟩ we obtain

lr^{∗}(λ, μ; ν) = ∑_{γ⊴ν′} K_{γ′ν} c(λ, μ, γ),  (8)

compare with [11, 2.9.17], [27, Section 3].

Plane partitions. We conclude this section by recalling some facts about plane partitions which will be used in the proof of Theorem 3.4. For a positive integer m, let [ m] := {1, …, m}. A subset S of the 3-dimensional box B(p, q, r) := [ p] × [ q] × [ r] is called pyramid if for all (a, b, c) ∈ S and for all (x, y, z) ∈ B(p, q, r) the conditions x ≤ a, y ≤ b and z ≤ c imply (x, y, z) ∈ S. Pyramids were used in [26] to give examples of sets of uniqueness. We will say more about them in Section 4. A plane partition with at most p rows, at most q columns, and largest part ≤ r is a matrix A = (a_{ij}) with non-negative integer coefficients of size p × q, such that 0 ≤ a_{ij} ≤ r, and whose rows and columns are weakly decreasing, see [16, Section 421]. There is a simple well-known one-to-one correspondence between pyramids S ⊆ B(p, q, r) and plane partitions A = (a_{ij}) with at most p rows, at most q columns, and largest part ≤ r, see [16, Section 423]. For this reason a pyramid is also called the graph or the diagram of its associated plane partition. The correspondence is given by S ⟼ Z(S) = (z_{ij}), where z_{ij} := |{k ∈ [ r] | (i, j, k) ∈ S}|; its inverse is A ⟼ S(A), where S(A) := {(i, j, k) ∈ B(p, q, r) | 1 ≤ k ≤ a_{ij}}. If we start with a pyramid S ∈ B(p, q, r) there are other two obvious ways of associating to S a plane partition: Y (S) = (y_{ki}), where y_{ki} := |{j ∈ [ q] | (i, j, k) ∈ S}|, and X(S) = (x_{jk}), where x_{jk} := |{i ∈ [ p] | (i, j, k) ∈ S}|. The plane partitions X(S), Y (S), Z(S) are related in the following way: For all 1 ≤ i ≤ p, column i of Y (S) is the conjugate partition of row i of Z(S), in symbols, r_{i}(Z(S)) = c_{i}(Y (S))′; and similarly for all 1 ≤ k ≤ r, r_{k}(Y (S)) = c_{k}(X(S))′, and for all 1 ≤ j ≤ q, r_{j}(X(S)) = c_{j}(Z(S))′. The slice vectors λ, μ, ν of any subset S of the box B(p, q, r) are formed by the cardinalities of its slices parallel to the coordinate planes:

λ_{i} := |{x ∈ S | x_{1} = i}|, 1 ≤ i ≤ p,
μ_{j} := |{x ∈ S | x_{2} = j}|, 1 ≤ j ≤ q,  (9)
ν_{k} := |{x ∈ S | x_{3} = k}|, 1 ≤ k ≤ r.

If S is a pyramid, then λ, μ, and ν are partitions of |S|, and the correspondence S ⟼ Z(S) satisfies: Z(S) ∈ M(λ, μ), and π(Z(S)) = ν′. Conversely, if λ, μ, ν are partitions of n, and A ∈ M(λ, μ) is a plane partition with π(A) = ν, then its associated pyramid S(A) has slice vectors λ, μ, ν′.

3 Minimal matrices and plane partitions

In this section we give a proof of Theorem 1.1. It is divided in several steps. We have tried to show which consequences follow only from the minimality of M, and which use the fact that M is a plane partition. Proposition 3.1 and Theorem 3.4 may be of interest by themselves. We also give an example showing that the inequalities in Theorem 1.1.3 may be strict.

3.1. Proposition. Let M be a matrix in M(λ, μ), and let ν = π(M). Then M is minimal if and only if m^{∗}(λ, μ, ν′) = a(λ, μ; ν).

Proof. It follows from (3), (6) and (2) that for any partitions λ, μ, ν

m^{∗}(λ, μ, ν′) = ∑_{δ⊢n} a(λ, μ; δ) m^{∗}(δ, ν′) .

If M is minimal in M(λ, μ) and ν = π(M), then a(λ, μ; δ) = 0 for all δ⊲ν. Moreover, it follows from (4) that m^{∗}(δ, ν′) = 0 for all δ ⊳ ν. These two equalities and (5) imply m^{∗}(λ, μ; ν′) = a(λ, μ; ν). The converse is similar. □

3.2. Proposition. Let M be a minimal matrix in M(λ, μ), and let ν = π(M). Then

c(α, β, γ) = 0

for all α ⊵ λ, β ⊵ μ, and γ ⊲ ν.

Proof. It follows from (6) and (1) that for any partitions λ, μ, ν

⟨ϕ^{λ} ⊗ ϕ^{μ}, χ^{ν}⟩ = ∑_{δ⊢n} a(λ, μ; δ) K_{νδ}.

If M is minimal in M(λ, μ) and ν = π(M), then one proves, in a similar way as in Proposition 3.1, that ⟨ϕ^{λ} ⊗ ϕ^{μ}, χ^{ν}⟩ = a(λ, μ; ν). But, then by Proposition 3.1

⟨ϕ^{λ} ⊗ ϕ^{μ}, χ^{ν}⟩ = ⟨ϕ^{λ} ⊗ ϕ^{μ} ⊗ ϕ^{ν′}, χ^{(1^{n})}⟩ .

The claim now follows from (1), the fact that χ^{α} ⊗ χ^{(1^{n})} = χ^{α′} for any α, and the positivity of the Kostka numbers. □

3.3. Corollary. Let M be a minimal matrix in M(λ, μ), and let ν = π(M). Then (1) c(λ, μ, ν) = lr^{∗}(λ, μ; ν′).

(2) a(λ, μ; ν) = c(λ, μ, ν) + ∑ K_{αλ}K_{βμ}c(α, β, ν). Here the sum is over all pairs (α, β) such that α ⊵ λ, β ⊵ μ and (α, β) ≠ (λ, μ). □

Under the assumptions of Proposition 3.2 we know that c(λ, μ, γ) = 0 for all γ ⊲ ν, but still c(λ, μ, ν) could be zero. For example if λ = μ = (3^{2}), the minimal matrices in M(λ, μ) are [ \begin{matrix}2 & 1 \\ 1 & 2 \end{matrix} ] and [ \begin{matrix}1 & 2 \\ 2 & 1 \end{matrix} ]. However, for ν = (2^{2}, 1^{2}), we have c(λ, μ, ν) = lr^{∗}(λ, μ; ν′) = 0. Therefore, we need to impose an extra condition in M in order to assure the positivity of c(λ, μ, ν). One such condition, as we shall see below, is that M is a plane partition.

3.4. Theorem. Let λ, μ, ν be partitions of n. Then

p(λ, μ; ν) ≤ lr^{∗}(λ, μ; ν′).

Proof. Let r = ℓ(ν′). We construct an injective map from the set of plane partitions A ∈ M(λ, μ) with π(A) = ν to the set of pairs (S, T) of Littlewood-Richardson multitableaux of shape (λ, μ), and type ν′, such that if S has content (ρ(1), …, ρ(r)), then T has content (ρ(1)′, …, ρ(r)′). Let S be the pyramid associated to A, so that A = Z(S), see Section 2. Let B = Y (S), and C = X(S). Then B ∈ M(ν′, λ), C ∈ M(μ, ν′), and for all 1 ≤ k ≤ r, r_{k}(B) = c_{k}(C)′. From B we construct a filtration

0 = λ(0) ⊂ λ(1) ⊂ ⋯ ⊂ λ(r) = λ

as follows. Let λ(k) := ∑_{1≤α≤k} r_{α}(B), for 1 ≤ k ≤ r. Then λ(k) is a partition and |λ(k)/λ(k − 1)| = ν′_{k}. The skew diagram λ(k)/λ(k − 1) has a natural filling S_{k}, which is obtained by putting l’s on row l. Since B is a plane partition, S_{k} is a Littlewood-Richardson tableau of content r_{k}(B). In this way we have constructed a Littlewood-Richardson multitableau S = (S_{1}, …, S_{r}) of shape λ, type ν′ and content (r_{1}(B), …, r_{r}(B)). Now using C^{T} we construct in a similar way a Littlewood-Richardson multitableau T = (T_{1}, …, T_{r}) of shape μ, type ν′ and content (c_{1}(C), …, c_{r}(C)). The correspondence A ⟼ (S, T) yields the map we are looking for. □

3.5. Corollary. Let M be a minimal matrix in M(λ, μ), and let ν = π(M). Then (1) p(λ, μ; ν) ≤ c(λ, μ, ν) ≤ a(λ, μ; ν).

(2) If M is a plane partition, then ν is minimal for χ^{λ} ⊗ χ^{μ}. □

3.6. Proof of Theorem 1.1. Statements (1)-(4) have already been proved. And (5) follows from Corollary 3.3.2. □

3.7. Example. Let λ = (8, 7, 4, 2), μ = (11, 6, 4). With the aid of a computer we generated all minimal matrices in M(λ, μ). They are

A = [\begin{matrix}3 & 3 & 2 \\ 3 & 2 & 2 \\ 3 & 1 & 0 \\ 2 & 0 & 0 \end{matrix}] , B = [\begin{matrix}4 & 2 & 2 \\ 3 & 2 & 2 \\ 2 & 2 & 0 \\ 2 & 0 & 0 \end{matrix}] , C = [\begin{matrix}4 & 2 & 2 \\ 4 & 2 & 1 \\ 2 & 1 & 1 \\ 1 & 1 & 0 \end{matrix}] ,

D = [\begin{matrix}4 & 2 & 2 \\ 3 & 2 & 2 \\ 3 & 1 & 0 \\ 1 & 1 & 0 \end{matrix}] , D_{1} = [\begin{matrix}3 & 3 & 2 \\ 4 & 2 & 1 \\ 2 & 1 & 1 \\ 2 & 0 & 0 \end{matrix}] , D_{2} = [\begin{matrix}4 & 2 & 2 \\ 3 & 3 & 1 \\ 2 & 1 & 1 \\ 2 & 0 & 0 \end{matrix}] , D_{3} = [\begin{matrix}4 & 3 & 1 \\ 3 & 2 & 2 \\ 2 & 1 & 1 \\ 2 & 0 & 0 \end{matrix}] .

Since A, B, C and D are plane partitions, then by Theorem 1.1.1 the partitions π(A) = (3^{4}, 2^{4}, 1), π(B) = (4, 3, 2^{7}), π(C) = (4^{2}, 2^{4}, 1^{5}), π(D) = (4, 3^{2}, 2^{4}, 1^{3}) are minimal for χ^{λ} ⊗ χ^{μ}. If ν is any of the first three partitions, then 1 = p(λ, μ; ν) = c(λ, μ, ν) = a(λ, μ; ν). If ν = π(D), then 1 ≤ c(λ, μ, ν) ≤ 4, by Theorem 1.1.3, and c(λ, μ, ν) = lr^{∗}(λ, μ; ν′), by Theorem 1.1.2. Using (7) we get easily that c(λ, μ, ν) = 3. This shows that the inequalities in Theorem 1.1.3 may be strict. Of course Theorem 1.1.4 applies to our four partitions. In particular, for σ = (9, 6, 4, 2) and ν = π(D) we have c(σ, μ, γ) = 0 for all γ ⊲ ν; therefore c(σ, μ, ν) = lr^{∗}(σ, μ; ν′). This last number is easily seen to be 1. Then, it follows from Corollary 3.3.2 that c(α, β, ν) = 0 for all α ⊵ λ, β ⊵ μ such that (α, β) ≠ (λ, μ), (σ, μ).

3.8. Remark. We consider again the example after Corollary 3.3: let λ = μ = (3^{2}), then no minimal matrix in M(λ, μ) is a plane partition, so we cannot apply Theorem 1.1 to obtain minimal summands in χ^{λ} ⊗ χ^{μ}. The only partition associated to minimal matrices in M(λ, μ) is ν = (2^{2}, 1^{2}) and we have c(λ, μ, ν) = 0. It turns out that the partitions covering ν, namely σ = (2^{3}) and τ = (3, 1^{3}) are the only partitions corresponding to minimal summands in χ^{λ} ⊗ χ^{μ}. This leads us to the following natural questions: When does all minimal summands in χ^{λ} ⊗ χ^{μ} come from minimal plane partitions? How do we determine all minimal summands not comming from a minimal plane partition? These are questions we will address in a future paper.

4 Sets of uniqueness and minimal matrices

In this section we show that the existence of sets of uniqueness puts severe restrictions on some c(λ, μ, ν)’s.

Let S be a subset of B(p, q, r). Its slice vectors λ = (λ_{1}, …, λ_{p}), μ = (μ_{1}, …, μ_{q}), and ν = (ν_{1}, …, ν_{r}) are compositions of |S|, that is, vectors of non-negative integers whose coordinates sum |S|, see (9). The set S is called a set of uniqueness if it is the only set with slice vectors λ, μ, ν. Sets of uniqueness were introduced in [8], where a geometric characterization of them was given by the absence of certain configurations in B(p, q, r). Note that, as long as we are concerned with properties of S which depend on the cardinalities of its slices, we may and will assume that λ, μ, and ν are weakly decreasing, namely, that they are partitions of |S|. If this were not the case, we just permute some slices of S. Thus a set S is a set of uniqueness if and only if m^{∗}(λ, μ, ν) = 1.

The starting point of this work was the attempt to use identities (3) and (1), and some knowledge on the numbers c(λ, μ, ν) in order to find conditions on λ, μ, ν which would imply that S is a set of uniqueness. However, these numbers are hard to compute; it proved more fruitful to try to get information about the c(λ, μ, ν)’s from the existence of sets of uniqueness. This is the content of Corollary 4.2 which eventually developed into Theorem 1.1. In [25] an algebraic characterization of sets of uniqueness was given. Here, we need only one implication, which can be reformulated in the following way:

4.1. Theorem. Let S be a set of uniqueness and suppose that its slice vectors λ, μ, ν are partitions of |S|. Then S is a pyramid, its associated plane partition Z(S) is minimal in M(λ, μ), and a(λ, μ; ν′) = 1. □

From this and from Theorem 1.1 we obtain

4.2. Corollary. Let S be a set of uniqueness and suppose its slice vectors λ, μ, ν are partitions of |S|. Then

(1) ν′ is minimal for χ^{λ} ⊗ χ^{μ}.

(2) c(λ, μ, ν′) = 1.

(3) For all α⊵λ, β ⊵μ, γ ⊴ν′ such that (α, β, γ) ≠ (λ, μ, ν′), we have c(α, β, γ) = 0. □

4.3. Examples. The simplest example of set of uniqueness is the box B(a, b, c). It has slice vectors λ = ((bc)^{a}), μ = ((ac)^{b}), and ν = ((ab)^{c}). Then from the previous corollary we recover Satz 2.3 in [2]: c(λ, μ, ν′) = 1 and obtain new identitites c(α, β, γ) = 0 for all α ⊵ λ, β ⊵ μ, γ ⊴ ν′ such that (α, β, γ) ≠ (λ, μ, ν′). Another simple example of set of uniqueness is the hook set H = H(a, b, c) associated to the plane partition of size (a + 1) × (b + 1)

Z(H) = [\begin{matrix}c + 1 & 1 & ⋯ & 1 \\ 1 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 1 & 0 & ⋯ & 0 \end{matrix}] ,

see Section 1 in [25]. It has slice vectors λ = (b + c + 1, 1^{a}), μ = (a + c + 1, 1^{b}), and ν = (a + b + 1, 1^{c}). Then the previous corollary yields c(λ, μ, ν′) = 1, and c(λ, μ, γ) = 0 for all γ ⊲ ν′, which are contained in [17], as well as some new identities.

4.4. Remark. The notion of minimal matrix seems to be important. It was used in [25] to caracterize sets of uniqueness, and in this paper to obtain information about some c(λ, μ, ν)’s. Proposition 3.1 provides a characterization for minimal matrices. It would be desirable, however, to have more practical ways for deciding whether a given matrix M is minimal in M(λ, μ). This is a problem we propose for further study.

Note added in proof: After submitting this manuscript I learned from M. Kapranov that the inequality p(λ, μ; ν) ≤ c(λ, μ, ν) in our Theorem 3.1.3 was proved for all λ, μ, ν by L. Manivel (see Proposition 3.1 in Ann. Inst. Fourier (Grenoble) 47 (1997), no. 3, 715-773). Note, however, that p(λ, μ; ν) is not in general a good lower bound for c(λ, μ, ν); for example if λ = μ = ν = (4, 2, 1^{2}), then it follows from the tables in [11, p. 458] that c(λ, μ, ν) = 17, but one easily finds that p(λ, μ; ν) = 0 and a(λ, μ; ν) = 2. This and Example 3.7 seems to indicate that p(λ, μ; ν) and c(λ, μ, ν) are much closer, when ν corresponds to a minimal plane partition. We also note that Manivel’s proof is very different from ours. It uses representations of general linear groups and algebraic geometry.

References

[1] T. Brylawski, The lattice of integer partitions, Discrete Math. 6 (1973), 201-219.

[2] M. Clausen and H. Meier, Extreme irreduzible Konstituenten in Tensordarstellungen symmetrischer Gruppen, Bayreuther Math. Schriften 45 (1993), 1-17.

[3] A.J. Coleman, Induced Representations with applications to S_{n} and GL(n), in “Queen’s papers in pure and applied mathematics,” No. 4, Queens University, Kingston, Ontario, 1966.

[4] P. Doubilet, J. Fox, G.R. Rota, The elementary theory of the symmetric group, in “Combinatorics, representation theory and statistical methods in groups,” T.V. Narayama, R.M. Mathsen and J.G. Williams eds., Lecture Notes in Pure and Applied Mathematics, Vol. 57, Marcel Decker, New York, 1980.

[5] Y. Dvir, On the Kronecker product of S_{n} characters, J. Algebra 154 (1993), 125-140.

[6] Y. Dvir, A family of ℤ bases for the ring of S(n) characters and applications to the decomposition of Kronecker products, Europ. J. Combinatorics 15 (1994), 449-457.

[7] Ö. Eg̃eciog̃lu and J.B. Remmel. A combinatorial interpretation of the inverse Kostka matrix, Linear and multilinear Algebra 26 (1990), 59-84.

[8] P. C. Fishburn, J. C. Lagarias, J. A. Reeds and L. A. Shepp, Sets uniquely determined by projections on axes II. Discrete case, Discrete Math. 91 (1991), 149-159.

[9] D. Gale, A theorem of flows in networks, Pacif. J. Math. 7 (1957) 1073-1082.

[10] A. Garcia and J. B. Remmel, Shuffles of permutations and the Kronecker product, Graphs Combin. 1 (1985) 217-263.

[11] G.D. James and A. Kerber, “The representation theory of the symmetric group,” in Encyclopedia of mathematics and its applications, Vol. 16, Addison-Wesley, Reading, Massachusetts, 1981.

[12] T.Y. Lam, Young diagrams, Schur functions, the Gale-Ryser theorem and a conjecture of Snapper, J. Pure Appl. Algebra 10 (1977), 81-94.

[13] D.E. Littlewood, The Kronecker product of symmetric group representations, J. London Math. Soc. 31 (1956), 89-93.

[14] I.G. Macdonald, “Symmetric functions and Hall polynomials,” 2nd. edition, Oxford Univ. Press, Oxford, 1995.

[15] F.D. Murnaghan, The analysis of the Kronecker product of irreducible representations of the symmetric group, Amer. J. Math. 60 (1938), 761-784.

[16] P. A. MacMahon, “Combinatorial Analysis,” Vol. II. Cambridge Univ. Press, London-New York 1916; reprinted by Chelsea, New York, 1960.

[17] J.B. Remmel, A formula for the Kronecker products of Schur functions of hook shapes, J. Algebra 120 (1989), 100-118.

[18] J.B. Remmel, Formulas for the expansion of Kronecker products S_{(m,n)} ⊗ S_{(1^{p−r},r)} and S_{(1^{k},2^{l})} ⊗ S_{(1^{p−r},r)}, Discrete Math. 99, (1992), 265-287.

[19] J.B. Remmel and T. Whitehead, On the Kronecker product of Schur functions of two row shapes, Bull. Belg. Math. Soc. 1 (1994), 649-683.

[20] H.J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad. J. Math. 9 (1957), 371-377.

[21] H.J. Ryser, “Combinatorial mathematics,” Carus monograph No. 14, Math. Association of America, John Wiley and Sons, 1963.

[22] B.E. Sagan, “The symmetric group,” Wadsworth & Brooks/Cole, Pacific Grove, California, 1991.

[23] J. Saxl, The complex characters of the symmetric groups that remain irreducible on subgroups, J. Algebra 111 (1987), 210-219.

[24] E. Snapper, Group characters and nonnegative integral matrices, J. Algebra 19 (1971), 520-535.

[25] A. Torres-Cházaro and E. Vallejo, Sets of uniqueness and minimal matrices, J. Algebra 208 (1998), 444-451.

[26] E. Vallejo, Reductions of additive sets, sets of uniqueness and pyramids, Discrete Math. 173 (1997), 257-267.

[27] E. Vallejo, On the Kronecker product of the irreducible characters of the symmetric group, Pub. Prel. Inst. Mat. UNAM 526, March 1997.

[28] I. Zisser, The character covering numbers of the alternating groups, J. Algebra 153 (1992), 357-372.