Three enumeration formulas of standard Young tableaux of truncated shapes

In this paper we consider the enumeration of three kinds of standard Young tableaux (SYT) of truncated shapes by use of the method of multiple integrals. A product formula for the number of truncated shapes of the form (n^m, n ? r)\δ_k–1 is given, which implies that the number of SYT of truncated shape (n², 1)\(1) is the number of level steps in all 2-Motzkin paths. The number of SYT with three rows truncated by some boxes ((n + k)³)\(k) is discussed. Furthermore, the integral representation of the number of SYT of truncated shape (n^m)\(3, 2) is derived, which implies a simple formula of the number of SYT of truncated shape (nⁿ)\(3, 2).     

Properties of four partial orders on standard Young tableaux

Let SYTn be the set of all standard Young tableaux with n cells. After recalling the definitions of four partial orders, the weak, KL, geometric and chain orders on SYTn and some of their crucial properties, we prove three main results:

•

Intervals in any of these four orders essentially describe the product in a Hopf algebra of tableaux defined by Poirier and Reutenauer.

•

The map sending a tableau to its descent set induces a homotopy equivalence of the proper parts of all of these orders on tableaux with that of the Boolean algebra ²[n−1]. In particular, the Möbius function of these orders on tableaux is (−1)ⁿ⁻³.

•

For two of the four orders, one can define a more general order on skew tableaux having fixed inner boundary, and similarly analyze their homotopy type and Möbius function.

     

Standard Young tableaux and colored Motzkin paths

In this paper, we propose a notion of colored Motzkin paths and establish a bijection between the n-cell standard Young tableaux (SYT) of bounded height and the colored Motzkin paths of length n. This result not only gives a lattice path interpretation of the standard Young tableaux but also reveals an unexpected intrinsic relation between the set of SYTs with at most $2d+1$ rows and the set of SYTs with at most 2d rows.     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

Limit shapes of bumping routes in the Robinson–Schensted correspondence

We prove a limit shape theorem describing the asymptotic shape of bumping routes when the Robinson–Schensted algorithm is applied to a finite sequence of independent, identically distributed random variables with the uniform distribution U[0,1] on the unit interval, followed by an insertion of a deterministic number α. The bumping route converges after scaling, in the limit as the length of the sequence tends to infinity, to an explicit, deterministic curve depending only on α. This extends our previous result on the asymptotic determinism of Robinson–Schensted insertion, and answers a question posed by Moore in 2006. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 171–182, 2016     

A q-Analog of the Hook Walk Algorithm for Random Young Tableaux

A probabilistic algorithm, called the q-hook walk, is defined. For a given Young diagram, it produces a new one by adding a random box with probabilities, depending on a positive parameter q. The corresponding Markov chain in the space of infinite Young tableaux is closely related to the knot invariant of Jones, constructed via traces of Hecke algebras. For q = 1, the algorithm is essentially the hook walk of Greene, Nijenhuis, and Wilf. The q-hook formula and a q-deformation of Young graph are also considered.S. Kerov: Supported by a grant from CRM (Université de Montréal), during its Operator Algebras year     

Young tableaux and crystal base for U_q(osp(1|2n))

Let Uq(osp(1|2n)) be the quantized enveloping superalgebra corresponding to the Lie superalgebra osp(1|2n). In terms of semistandard Young tableaux satisfying some additional conditions, a realization of crystal graph of finite-dimensional irreducible modules of Uq(osp(1|2n)) is given. Also, the generalized LittlewoodRichardson rule for tensor product of crystal graphs is established.     

A Basis of Bideterminants for the Coordinate Ring of the Orthogonal Group

We give a basis of bideterminants for the coordinate ring K[O(n)] of the orthogonal group O(n,K), where K is an infinite field of characteristic not 2. The bideterminants are indexed by pairs of Young tableaux which are O(n)-standard in the sense of King–Welsh. We also give an explicit filtration of K[O(n)] as an O(n,K)-bimodule, whose factors are isomorphic to the tensor product of orthogonal analogs of left and right Schur modules.     

Nonvanishing of Kronecker coefficients for rectangular shapes

We prove that for any partition (λ₁,…,λd²) of size ?d there exists k?1 such that the tensor square of the irreducible representation of the symmetric group Sk?d with respect to the rectangular partition (k?,…,k?) contains the irreducible representation corresponding to the stretched partition (kλ₁,…,kλd²). We also prove a related approximate version of this statement in which the stretching factor k is effectively bounded in terms of d. We further discuss the consequences for geometric complexity theory which provided the motivation for this work.     

Paths and tableaux descriptions of Jacobi-Trudi determinant associated with quantum affine algebra of type <Emphasis Type="Italic">D</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

We study the Jacobi-Trudi-type determinant which is conjectured to be the q-character of a certain, in many cases irreducible, finite-dimensional representation of the quantum affine algebra of type D _n . Unlike the A _n and B _n cases, a simple application of the Gessel-Viennot path method does not yield an expression of the determinant by a positive sum over a set of tuples of paths. However, applying an additional involution and a deformation of paths, we obtain an expression by a positive sum over a set of tuples of paths, which is naturally translated into the one over a set of tableaux on a skew diagram.     

A Rational-Function Identity Related to the Murnaghan–Nakayama Formula for the Characters of S n

The Murnaghan–Nakayama formula for the characters of S _n is derived from Young's seminormal representation, by a direct combinatorial argument. The main idea is a rational function identity which when stated in a more general form involves Möbius functions of posets whose Hasse diagrams have a planar embedding. These ideas are also used to give an elementary exposition of the main properties of Young's seminormal representations.     

A Fatou lemma for Gelfand integrals by Means of Young Measure Theory

It is shown that a Fatou-type lemma for Gelfand-integrable functions, due to Cornet and Medecin, can be generalized by following the approach to Fatou-type results introduced in (Balder, Math. Op. Res. 9 (1984), 270; Balder, J. Math. Anal. Appl. 136 (1988), 450)     

Crystal Bases for Quantum Affine Algebras and Combinatorics of Young Walls

In this paper we give a realization of crystal bases for quantumaffine algebras using some new combinatorial objects which wecall the Young walls. The Young walls consist of colored blockswith various shapes that are built on a given ground-state walland can be viewed as generalizations of Young diagrams. Therules for building Young walls and the action of Kashiwara operatorsare given explicitly in terms of combinatorics of Young walls.The crystal graph of a basic representation is characterizedas the set of all reduced proper Young walls. The characterof a basic representation can be computed easily by countingthe number of colored blocks that have been added to the ground-statewall. 2000 Mathematical Subject Classification: 17B37, 17B65,81R50, 82B23.     

A local proof for the characterization of Young measures generated by sequences in BV

This work presents a new proof of the recent characterization theorem for generalized Young measures generated by sequences in BV by Kristensen and Rindler (2010) [14]. The present argument is based on a localization technique together with a local Hahn–Banach argument in novel function spaces combined with an application of Alberti's Rank-One Theorem. This strategy avoids employing a relaxation theorem as in the previously known proof, and the new tools introduced in its course should prove useful in other contexts as well. In particular, we introduce “homogeneous” Young measures, separately at regular and singular points, which exhibit rather different behavior than the classical homogeneous Young measures. As an application, we show how for BV-Young measures with an “atomic” part one can find a generating sequence respecting this structure.     

Upper bound on the characters of the symmetric groups for balanced Young diagrams and a generalized Frobenius formula

We study asymptotics of an irreducible representation of the symmetric group Sn corresponding to a balanced Young diagram λ (a Young diagram with at most rows and columns for some fixed constant C) in the limit as n tends to infinity. We show that there exists a constant D (which depends only on C) with a property that

     

On the power of standard information for tractability for L∞ approximation of periodic functions in the worst case setting

We study multivariate approximation of periodic functions in the worst case setting with the error measured in the $L_{\infty }$ norm. We consider algorithms that use standard information ${\mathrm{\Lambda }}^{\mathrm{std}}$ consisting of function values or general linear information ${\mathrm{\Lambda }}^{\mathrm{all}}$ consisting of arbitrary continuous linear functionals. We investigate equivalences of various notions of algebraic and exponential tractability for ${\mathrm{\Lambda }}^{\mathrm{std}}$ and ${\mathrm{\Lambda }}^{\mathrm{all}}$ under the absolute or normalized error criterion, and show that the power of ${\mathrm{\Lambda }}^{\mathrm{std}}$ is the same as the one of ${\mathrm{\Lambda }}^{\mathrm{all}}$ for various notions of algebraic and exponential tractability. Our results can be applied to weighted Korobov spaces and Korobov spaces with exponential weights. This gives a special solution to Open Problem 145 as posed by Novak and Woźniakowski (2012) [40].