Young's lattice

Last updated March 20, 2024

In mathematics, Young's lattice is a lattice that is formed by all integer partitions. It is named after Alfred Young, who, in a series of papers On quantitative substitutional analysis, developed the representation theory of the symmetric group. In Young's theory, the objects now called Young diagrams and the partial order on them played a key, even decisive, role. Young's lattice prominently figures in algebraic combinatorics, forming the simplest example of a differential poset in the sense of Stanley (1988). It is also closely connected with the crystal bases for affine Lie algebras.

Definition

Young's lattice is a lattice (and hence also a partially ordered set) Y formed by all integer partitions ordered by inclusion of their Young diagrams (or Ferrers diagrams).

Significance

The traditional application of Young's lattice is to the description of the irreducible representations of symmetric groups S_n for all n, together with their branching properties, in characteristic zero. The equivalence classes of irreducible representations may be parametrized by partitions or Young diagrams, the restriction from S_n +1 to S_n is multiplicity-free, and the representation of S_n with partition p is contained in the representation of S_n +1 with partition q if and only if q covers p in Young's lattice. Iterating this procedure, one arrives at Young's semicanonical basis in the irreducible representation of S_n with partition p, which is indexed by the standard Young tableaux of shape p.

Properties

The poset Y is graded: the minimal element is ∅, the unique partition of zero, and the partitions of n have rank n. This means that given two partitions that are comparable in the lattice, their ranks are ordered in the same sense as the partitions, and there is at least one intermediate partition of each intermediate rank.
The poset Y is a lattice. The meet and join of two partitions are given by the intersection and the union of the corresponding Young diagrams. Because it is a lattice in which the meet and join operations are represented by intersections and unions, it is a distributive lattice.
If a partition p covers k elements of Young's lattice for some k then it is covered by k + 1 elements. All partitions covered by p can be found by removing one of the "corners" of its Young diagram (boxes at the end both of their row and of their column). All partitions covering p can be found by adding one of the "dual corners" to its Young diagram (boxes outside the diagram that are the first such box both in their row and in their column). There is always a dual corner in the first row, and for each other dual corner there is a corner in the previous row, whence the stated property.
If distinct partitions p and q both cover k elements of Y then k is 0 or 1, and p and q are covered by k elements. In plain language: two partitions can have at most one (third) partition covered by both (their respective diagrams then each have one box not belonging to the other), in which case there is also one (fourth) partition covering them both (whose diagram is the union of their diagrams).
Saturated chains between ∅ and p are in a natural bijection with the standard Young tableaux of shape p: the diagrams in the chain add the boxes of the diagram of the standard Young tableau in the order of their numbering. More generally, saturated chains between q and p are in a natural bijection with the skew standard tableaux of skew shape p/q.
The Möbius function of Young's lattice takes values 0, ±1. It is given by the formula

\mu (q,p)={\begin{cases}(-1)^{|p|-|q|}&{\text{if the skew diagram }}p/q{\text{ is a disconnected union of squares}}\\&{\text{(no common edges);}}\\[10pt]0&{\text{otherwise}}.\end{cases}}

Dihedral symmetry

The portion of Young's lattice lying below 1 + 1 + 1 + 1, 2 + 2 + 2, 3 + 3, and 4

Conventional diagram with partitions of the same rank at the same height

Diagram showing dihedral symmetry

Conventionally, Young's lattice is depicted in a Hasse diagram with all elements of the same rank shown at the same height above the bottom. Suter (2002) has shown that a different way of depicting some subsets of Young's lattice shows some unexpected symmetries.

The partition

n+\cdots +3+2+1

of the nth triangular number has a Ferrers diagram that looks like a staircase. The largest elements whose Ferrers diagrams are rectangular that lie under the staircase are these:

{\begin{array}{c}\underbrace {1+\cdots \cdots \cdots +1} _{n{\text{ terms}}}\\\underbrace {2+\cdots \cdots +2} _{n-1{\text{ terms}}}\\\underbrace {3+\cdots +3} _{n-2{\text{ terms}}}\\\vdots \\\underbrace {{}\quad n\quad {}} _{1{\text{ term}}}\end{array}}

Partitions of this form are the only ones that have only one element immediately below them in Young's lattice. Suter showed that the set of all elements less than or equal to these particular partitions has not only the bilateral symmetry that one expects of Young's lattice, but also rotational symmetry: the rotation group of order n + 1 acts on this poset. Since this set has both bilateral symmetry and rotational symmetry, it must have dihedral symmetry: the (n + 1)st dihedral group acts faithfully on this set. The size of this set is 2ⁿ.

For example, when n = 4, then the maximal element under the "staircase" that have rectangular Ferrers diagrams are

1 + 1 + 1 + 1

2 + 2 + 2

3 + 3

4

The subset of Young's lattice lying below these partitions has both bilateral symmetry and 5-fold rotational symmetry. Hence the dihedral group D₅ acts faithfully on this subset of Young's lattice.

Related Research Articles

In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group $defined over a finite set of symbols consists of the permutations that can be performed on the symbols. Since there are such permutation operations, the order of the symmetric group is .$

In number theory and combinatorics, a partition of a non-negative integer $n$ , also called an integer partition, is a way of writing $n$ as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, $4$ can be partitioned in five distinct ways:

<span class="mw-page-title-main">Root system</span> Geometric arrangements of points, foundational to Lie theory

In mathematics, a root system is a configuration of vectors in a Euclidean space satisfying certain geometrical properties. The concept is fundamental in the theory of Lie groups and Lie algebras, especially the classification and representation theory of semisimple Lie algebras. Since Lie groups and Lie algebras have become important in many parts of mathematics during the twentieth century, the apparently special nature of root systems belies the number of areas in which they are applied. Further, the classification scheme for root systems, by Dynkin diagrams, occurs in parts of mathematics with no overt connection to Lie theory. Finally, root systems are important for their own sake, as in spectral graph theory.

In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

In mathematics, Euler's pentagonal number theorem relates the product and series representations of the Euler function. It states that

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.

In mathematics, a Young tableau is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups and to study their properties. Young tableaux were introduced by Alfred Young, a mathematician at Cambridge University, in 1900. They were then applied to the study of the symmetric group by Georg Frobenius in 1903. Their theory was further developed by many mathematicians, including Percy MacMahon, W. V. D. Hodge, G. de B. Robinson, Gian-Carlo Rota, Alain Lascoux, Marcel-Paul Schützenberger and Richard P. Stanley.

In mathematics, the representation theory of the symmetric group is a particular case of the representation theory of finite groups, for which a concrete and detailed theory can be obtained. This has a large area of potential applications, from symmetric function theory to quantum chemistry studies of atoms, molecules and solids.

In group theory, restriction forms a representation of a subgroup using a known representation of the whole group. Restriction is a fundamental construction in representation theory of groups. Often the restricted representation is simpler to understand. Rules for decomposing the restriction of an irreducible representation into irreducible representations of the subgroup are called branching rules, and have important applications in physics. For example, in case of explicit symmetry breaking, the symmetry group of the problem is reduced from the whole group to one of its subgroups. In quantum mechanics, this reduction in symmetry appears as a splitting of degenerate energy levels into multiplets, as in the Stark or Zeeman effect.

In mathematics, a Young symmetrizer is an element of the group algebra of the symmetric group, constructed in such a way that, for the homomorphism from the group algebra to the endomorphisms of a vector space $obtained from the action of on by permutation of indices, the image of the endomorphism determined by that element corresponds to an irreducible representation of the symmetric group over the complex numbers. A similar construction works over any field, and the resulting representations are called Specht modules . The Young symmetrizer is named after British mathematician Alfred Young.$

In mathematics, a Coxeter element is an element of an irreducible Coxeter group which is a product of all simple reflections. The product depends on the order in which they are taken, but different orderings produce conjugate elements, which have the same order. This order is known as the Coxeter number. They are named after British-Canadian geometer H.S.M. Coxeter, who introduced the groups in 1934 as abstractions of reflection groups.

In mathematics, Schur polynomials, named after Issai Schur, are certain symmetric polynomials in n variables, indexed by partitions, that generalize the elementary symmetric polynomials and the complete homogeneous symmetric polynomials. In representation theory they are the characters of polynomial irreducible representations of the general linear groups. The Schur polynomials form a linear basis for the space of all symmetric polynomials. Any product of Schur polynomials can be written as a linear combination of Schur polynomials with non-negative integral coefficients; the values of these coefficients is given combinatorially by the Littlewood–Richardson rule. More generally, skew Schur polynomials are associated with pairs of partitions and have similar properties to Schur polynomials.

In mathematics, a Specht module is one of the representations of symmetric groups studied by Wilhelm Specht . They are indexed by partitions, and in characteristic 0 the Specht modules of partitions of n form a complete set of irreducible representations of the symmetric group on n points.

In discrete mathematics, dominance order is a partial order on the set of partitions of a positive integer n that plays an important role in algebraic combinatorics and representation theory, especially in the context of symmetric functions and representation theory of the symmetric group.

In mathematics, the Littlewood–Richardson rule is a combinatorial description of the coefficients that arise when decomposing a product of two Schur functions as a linear combination of other Schur functions. These coefficients are natural numbers, which the Littlewood–Richardson rule describes as counting certain skew tableaux. They occur in many other mathematical contexts, for instance as multiplicity in the decomposition of tensor products of finite-dimensional representations of general linear groups, or in the decomposition of certain induced representations in the representation theory of the symmetric group, or in the area of algebraic combinatorics dealing with Young tableaux and symmetric polynomials.

In mathematics, the Garnir relations give a way of expressing a basis of the Specht modules V_λ in terms of standard polytabloids.

In mathematics, a differential poset is a partially ordered set satisfying certain local properties. This family of posets was introduced by Stanley (1988) as a generalization of Young's lattice, many of whose combinatorial properties are shared by all differential posets. In addition to Young's lattice, the other most significant example of a differential poset is the Young–Fibonacci lattice.

In combinatorial mathematics, the hook length formula is a formula for the number of standard Young tableaux whose shape is a given Young diagram. It has applications in diverse areas such as representation theory, probability, and algorithm analysis; for example, the problem of longest increasing subsequences. A related formula gives the number of semi-standard Young tableaux, which is a specialization of a Schur polynomial.

In group theory, a branch of mathematics, the Murnaghan–Nakayama rule, named after Francis Murnaghan and Tadashi Nakayama, is a combinatorial method to compute irreducible character values of a symmetric group. There are several generalizations of this rule beyond the representation theory of symmetric groups, but they are not covered here.

The partition algebra is an associative algebra with a basis of set-partition diagrams and multiplication given by diagram concatenation. Its subalgebras include diagram algebras such as the Brauer algebra, the Temperley–Lieb algebra, or the group algebra of the symmetric group. Representations of the partition algebra are built from sets of diagrams and from representations of the symmetric group.

References

Misra, Kailash C.; Miwa, Tetsuji (1990). "Crystal base for the basic representation of $U_{q}({\widehat {\mathfrak {sl}}}(n))$ ". Communications in Mathematical Physics . 134 (1): 79–88. Bibcode:1990CMaPh.134...79M. doi:10.1007/BF02102090. S2CID 120298905.
Sagan, Bruce (2000). The Symmetric Group. Berlin: Springer. ISBN 0-387-95067-2.
Stanley, Richard P. (1988). "Differential posets". Journal of the American Mathematical Society . 1 (4): 919–961. doi: 10.2307/1990995 . JSTOR 1990995.
Suter, Ruedi (2002). "Young's lattice and dihedral symmetries". European Journal of Combinatorics . 23 (2): 233–238. doi: 10.1006/eujc.2001.0541 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

v t e Order theory
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types ( list )	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Ordered vector space Partially ordered Positive cone Riesz space Upper set Young's lattice