Young Tableaux in Combinatorics, Invariant Theory, and Algebra An Anthology of Recent Work Edited by JOSEPH P. S. KUNG Department of Mathematics North Texas State University Denton, Texas 1982 ACADEMIC PRESS A Subsidiary of Harcourt Brace Jovanovich, Publishers New York London Paris San Diego San Francisco Sao Paulo Sydney Tokyo Toronto COPYRIGHT © 1982, BY ACADEMIC PRESS, INC. ALL RIGHTS RESERVED. NO PART OF THIS PUBLICATION MAY BE REPRODUCED OR TRANSMITTED IN ANY FORM OR BY ANY MEANS, ELECTRONIC OR MECHANICAL, INCLUDING PHOTOCOPY, RECORDING, OR ANY INFORMATION STORAGE AND RETRIEVAL SYSTEM, WITHOUT PERMISSION IN WRITING FROM THE PUBLISHER. ACADEMIC PRESS, INC. Ill Fifth Avenue, New York, New York 10003 United Kingdom Edition published by ACADEMIC PRESS, INC. (LONDON) LTD. 24/28 Oval Road, London NW1 7DX LIBRARY OF CONGRESS CATALOG CARD NUMBER: 82-11330 ISBN 0-12-428780-8 PRINTED IN THE UNITED STATES OF AMERICA 82 83 84 85 9 8 7 6 5 4 3 2 1 Contributors Numbers in parentheses indicate the pages on which the authors' contributions begin. S. Abeasis (255), Istituto Matematico 'Guido Castelnuovo, ' Université di Roma, Piazzale A. Mow 5, Roma, Italy M. Clausen (197), Lehrstuhl II fur Mathematik, Universität Bayreuth, D-8580 Bayreuth, West Germany C. De Concini (169, 277), Istituto diMatematica 'Leonida Tonelli,' Univer- sita di Pisa, 56100, Pisa, Italy J. Désarménien (133), Département de Mathématique, Université Louis Pasteur, 67084 Strasbourg, France P. Doubilet (163), Harvard Medical School, 25 Shattuck St., Boston, Massachusetts 02115 A. Del Fra (255), Istituto Matematico 'Guido Castelnuovo,' Università di Roma, Piazzale A. Moro 5, Roma, Italy R. M. Grassl (23), Department of Mathematics, University of New Mexico, Albuquerque, New Mexico 87131 C. Greene (17, 39, 51), Department of Mathematics, Haverford College, Haverford, Pennsylvania 19041 A. P. Hillman (23), Department of Mathematics, University of New Mex- ico, Albuquerque, New Mexico 87131 J. P. S. Kung (133), Department of Mathematics, North Texas State Uni- versity, Denton, Texas 76203 A. Lascoux (299), U.E.R. de Mathématiques, Université Paris VII, 75221 Paris Cedex 05, France Β. F. Logan (63), Bell Laboratories, Murray Hill, New Jersey 07974 A. Nijenhuis (17), Department of Mathematics, University of Penn- sylvania, Philadelphia, Pennsylvania 19104 C. Procesi (169), Istituto Matematico 'Guido Castelnuovo,' Università di Roma, Piazzale A. Moro 5, Rome, Italy G.-C. Rota (133, 163), Department of Mathematics, Massachusetts In- stitute of Technology, Cambridge Massachusetts 02139 B. Sagan (29), Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109 vii viii Contributors L. A. Shepp (63), Bell Laboratories, Murray Hill, New Jersey 07974 E. Strickland (277), Istituto Matematico G( uido Castelnuovo/ Université di Roma, Piazzale A. Mow 5, Roma, Italy G. P. Thomas (81, 107), BBC Production Unit, Milton Keynes MK7 6ΛΛ, England D. E. White (123), Department of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455 H. S. Wilf (17), Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania 19104 Introduction In compiling this anthology of recent papers on Young tableaux and their applications, I was guided by the etymology of the word * 'anthology.' ' An anthology is literally a collection of flowers and my choice of papers was guided by the same practical and aesthetic considerations as in making up a floral bouquet. I did not aim at collecting all the papers in a given area; rather, the aim was to give a representative, contrasting, and enticing sample of recent work involving Young tableaux. The resulting lack of completeness is remedied by the following commentary, which contains extensive references to related work. Let A be a set of symbols. A Young tableau Γ with entries from A is an ar- ray of the form at a a ... α 2 3 Χχ bb ... Z?x x 2 2 Ci . . . CXm where ab... ,c are symbols in A and λι > λ > ... > X . The sequence i9 i9 f 2 m χ = (λι,λ ,... ,X ) is called the shape of Τ and is often visualized as an array 2 m of squares in the plane, λ is also thought of as a partition of n, where η = λι + λ + · · · + X . Now let A be linearly ordered. Then, the tableau Τ is 2 m said to be standard if the symbols are increasing along a row and, depending on the context, either increasing or nondecreasing down a column. Young tableaux were discovered by Alfred Young at the turn of the century. Using them and (to a certain extent) the contemporary work of Frobenius and Schur, Young obtained a complete classification of the irreducible representa- tions of the symmetric group S„ over the complex numbers. (Young also used his tableaux in computing the invariants of binary forms [Yl].) Somewhat earlier, Frobenius [F9] also obtained the irreducible representations of S„, but in a character theoretic manner. Shortly after, Schur [S13] showed that the ir- reducible polynomial representations of the general linear group GL(rt,Q are in one-to-one correspondence with the irreducible representations of S,n>k. In k the hands of Weyl and others, this spectacular application was a decisive in- fluence on the development of quantum mechanics and the representation ι 2 Joseph P. S. Kung theory of the classical groups (see [W] and [WW]) and since then, Young tableaux have pervaded much of mathematics and physics. However, it is difficult to say precisely how Young tableaux fit into mathe- matics: they are not (as yet) a conceptual part of any grand theory or structure (with one possible exception: their shapes represent all the symmetries between η objects), but it is nonetheless palpably inadequate to label them as mere nota- tion. Perhaps, Young tableaux are, quite simply, archetypal mathematical ob- jects. Among mathematicians, combinatorial theorists are the most attuned to dealing with mathematical objects as such, and it is with their contributions that we begin this anthology. COMBINATORICS The first paper in this section is concerned with the number f of standard x Young tableaux of a given shape λ. This number f is given by the following x formula of Frame, Robinson, and Thrall: fx = n\/U h (1) ij9 where Λ is the hook length of the (/j)th square and η = \ι + · · · + \ . Per- 0 m haps the shortest proof of this formula is the one due to MacMahon. It is in- ductive and relies on the recursion A,,...,xm = Σ/λι \-i*r l*i+v <xm- (2) This proof yields little intuition as to why (1) is true and, in particular, it leaves as a mystery the role of the hook lengths in (1). In the paper of Greene, Nijenhuis, and Wilf, a random walk model is constructed which yields a proba- bilistic interpretation of the recursion (2). This shows why the hook lengths should appear in (1) and also yields an efficient algorithm for generating a "random" standard Young tableau. There is another (determinantal) formula for f in which the role of the hook lengths is more immediate [F8]. Another approach, using Cayley operators, is in [Cl]. Sagan [S2] has obtained an analogous model for shifted standard Young tableaux and through it, a probabilistic interpretation of a formula for the number of shifted standard Young tableaux. Finally, Greene, Nijenhuis, and Wilf [G4] have used a modification of their random walk model to obtain a probabilistic proof of the Young-Frobenius equation [see Eq. (6) below]. The hook length formula can also be derived as a limiting case of a generat- ing function for reverse plane partitions. A reverse plane partition (or rpp) of the nonnegative integer A: is a Young tableau with entries from (0,1,... ,k] such that the sum of all the entries is k and the entries are nondecreasing along a row Introduction 3 and down a column. The shape of a rpp is the shape of the tableau. Let λ be a given shape and let a be the number of rpp of k with shape λ. Then, it is true k that ΣΓ α^ = Π(1 -JCV, (3) = 0 where the product is over all the squares of the shape λ and A is the hook 0 length of the (/j)th square. Now, the product equals where ß is the number of solutions (nty) in nonnegative integers of the equation k Lniijhij = k, the sum being over all the squares of the shape λ. Thus, one way to prove (3) is to show that a = ß. This is done in the second paper in this section. In this k k paper, Hillman and Grassl describe an explicit algorithm which constructs a rpp given a solution of (4), and thus obtain a combinatorial proof of (3). The Hillman-Grassl algorithm has become one of the basic combinatorial tools in the theory of rpp (see [HI] and [Gl]; the second reference contains a survey of this area). To derive the hook length formula from (3), we need the theory of P-partitions of Stanley [S9]. Consider the shape λ as a partially ordered set by setting the (ij) square greater than the (/{/) square if / > /' and j > / .A standard Young tableau with shape λ is a labeling of the squares of λ compati- ble with the partial order: that is, it is an extension of the partial order to a total order. The number of such extensions can be computed using Stanley's theory (see Corollaries 5.3 and 5.4, pp. 11-12 of [S9]). It equals lim(l-x)(l-χ2)-· (1 -xn) ΣΓ=ο α***. (5) x-M The hook length formula now follows from (3) and (5). The number / is also the dimension of the irreducible representation of S λ n corresponding to the shape λ. Hence, by an equation of Frobenius in group representation theory, Σ/χ2 = ni. (6) This equation can be interpreted combinatorially by an algorithm of Robinson [R3] and Schensted [S5], which associates to every permutation σ (the right- hand side) a pair [S(a),T(a)] of standard Young tableaux of the same shape (the left-hand side). This algorithm is the starting point of much of the recent com- binatorial work on Young tableaux. The next five papers give a cross-section of this work. 4 Joseph P. S. Kung The paper of Bruce Sagan is based on an analogue of (6) in the projective representation theory of the symmetric group (see [S14] or [M2]; I am indebted to Richard Stanley for these references): E2"-'<«>g2 = nl, M where g„ is the number of shifted standard Young tableaux of shape μ and ί(μ) is the number of parts in the partition μ. Sagan develops an analogue of Schensted's algorithm, which associates with each permutation of (1,2,...,n] a subset of [1,... ,n] and a pair of shifted standard Young tableaux. Schensted's motivation for developing his algorithm was to study the length of the longest increasing [decreasing] subsequence in a permutation. This turns out neatly to be Χι \\i*]9 the number of squares in the first row [column] of the common shape λ of the two standard Young tableaux associated with the per- mutation. In the fourth paper, Curtis Greene extends this theorem to the entire shape λ. More precisely, Greene shows (*): Let λ, [λ,*] be the number of squares in the /th row [column] of the shape λ. Then, the sum \ + λ + · · · + λ* [λι* + λ * + · · · Η- λ**] is the length of the t 2 2 longest subsequence obtainable by taking the union of k increasing [decreasing] subsequences. The proof is based on a characterization of Knuth [K2] of permutations π and σ, such that S(TT) = S(a). The next paper, also by Greene, extends the idea of (*) to partially ordered sets. Its main result is a "higher-order" extension of Dilworth's theorem about antichains and partitions into chains in a partially ordered set. This result is proved using the notion of saturated partitions [G3]. Other proofs can be found in [F3], [G2], and [H4]. The chains and antichains of a partially ordered set form an antiblocking pair of collections of subsets (or hypergraphs), that is, each chain intersects each antichain in at most one element. Greene's extension does not always hold for antiblocking pairs of hypergraphs (indeed, it is not even true for cliques and independent or stable sets in perfect graphs). Even so, it provides a useful paradigm for duality results in combinatorial structures and has led to many special classes of antiblocking pairs in which it holds. A survey of this area can be found in [S4]. The paper by Logan and Shepp is directly in the tradition of Schensted's paper. It is concerned with the question: What is the expected length of the longest increasing subsequence in a "random" permutation? Using Schensted's algorithm, this can be rephrased as a question about the shape of a random standard Young tableau. ("Random" here is in terms of a distribution involv- ing the hook lengths.) In turn, this can be rephrased as a variational problem for functional defined on certain real functions on the positive real axis. The Introduction 5 authors solve this problem and prove that 2 is a lower bound for the limit in ί/2 probability of / (σ„)/η , where / (σ„) is the length of the longest increasing sub- sequence in a random permutation on the set (1,2,...Related papers are [Kl] and [L3]. The wide applicability of Schensted's algorithm is shown in the seventh paper. In this paper, Glânffrwd Thomas extends Schensted's algorithm and us- ing this extension, gives a proof of the Littlewood-Richardson rule for the multiplication of two Schur functions. This proof and the proofs in [LI2] and Paper 13 in this anthology are the first truly rigorous proofs of the Littlewood-Richardson rule, even though this rule is one of the basic tools for computing with the representations of S„. There are other developments of Schensted's algorithm that are not included here. The most notable are perhaps the monoide plaxique of Lascoux and Schützenberger [L2] and the generalization using pictures of Zelevinsky [Zl], The reader is referred to [Bl], [B2], [Fl], [G7], [H2], [SI], [T2], [T5], [T6], [VI], [V2], and [W2], and to Schützenberger's article [S6], which ties together many different strands of research. In addition, Chapter 5 of [K] contains ap- plications of Schensted's algorithm to the theory of sorting. The eighth paper reveals a rather surprising connection between Young ta- bleaux and Baxter operators. In this paper, Thomas first defines an equivalence relation on the set of all "standard" Young tableaux whose entries come from the (infinite) set [1,2,3,... }. Associated with each equivalence class is a formal power series called the inventory of the equivalence class (the usage here derives from Polya enumeration theory). In each equivalence class, there is exactly one standard Young tableau Tin which the numbers 1,2,... ,n occur exactly once. The main result is that the inventory of the equivalence class can be described simply by means of a sequence of Baxter operators constructed from the Young tableau T. This result is applied to obtain a generating function for Schur functions. Inventories also appear in the final paper of the combinatorics section. In this short and elegant paper, Dennis White uses the representation theory of S n (in particular, Kostka numbers) to show a monotonicity result in Polya enu- meration theory. A particular case of this result is the unimodality of the coeffi- m w cients of the Gaussian coefficient [ * ]. Related papers are [Wl] and [Sil]. We end by mentioning (for the novice reader) a now classic source for the combinatorial theory of Young tableaux, Richard Stanley's [S7, I and II]. INVARIANT THEORY The first paper in this section begins with a study of letter place algebras. Let A: be a field and {x.. .,*„), {u.. .,w ) be two alphabets called letters and l9 u m 6 Joseph P. S. Kung places, respectively. The letter place algebra Ρ is the polynomial ring k[<Xi\Uj>] over the set (<JC,|W,>) of indeterminates. The reason for this bracket notation is that it offers a concise way of writing determinants in P, to wit <x.. ,x\ui.. M > = det[<x |w >]i . x p P i / Sif>Sp A similar notation, with the letters written on top of the places, was advocated by Cayley and Sylvester (independently) as an "umbral" notation for deter- minants; an enthusiastic account of this can be found in MacMahon's lecture [Ml]. Going further, we can write products of such determinants as a pair of Young tableaux: X2l . . -Xlq U21.. • u2q where superposition means multiplication. Such products are called bidetermi- nants and a bideterminant for which both Young tableaux are standard is called a standard bideterminant. Bideterminants were first studied by Turnbull [Τ, Chapter 5] in the guise of "inner products" of rectangular matrices. The main result about letter place algebras is that apart from the algebrai- cally "obvious" basis consisting of the monomials in <x |w >, there is f / another more useful basis consisting of the standard bideterminants. The special case of this result for a "single" tableau was discovered by Hodge [H6] in 1943 during his investigations into Grassmannians. (See also [H5]; Littlewood provided at about the same time another (rather opaque) proof us- ing the invariant theory of forms.) Although it was recognized that this result has important ramifications in the theory of invariants, the theory of letter place algebras lied dormant, with the exception of an application by Igusa [II] to invariant theory over fields of characteristic p. It was finally revived in the 1970s when the main result in its full generality was discovered independently by Mead [M2] and Doubilet, Rota, and Stein [D4]. Mead's motivation was in differential algebra and he considered the deriva- tives DjXi instead of the indeterminates <x | w,->. Under this substitution, a let- t ter place algebra becomes an algebra of differential polynomials and a bideter- minant becomes a product of generalized Wronskians. In [M2], Mead solved the following problem posed by Ritt: What is the differential ideal generated by the classical Wronskian Using the basis of standard bideterminants, Mead explicitly finds a basis for this ideal.