Young's lattice
Encyclopedia
In mathematics
, Young's lattice is a partially ordered set
and 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 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 . It is also closely connected with the crystal base
s for affine Lie algebra
s.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Young's lattice is a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
and a lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
that is formed by all integer partitions
Partition (number theory)
In number theory and combinatorics, a partition of a positive 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 to be the same partition; if order matters then the sum becomes a...
. It is named after Alfred Young
Alfred Young
Alfred Young, FRS was a British mathematician.He was born in Widnes, Lancashire, England and educated at Monkton Combe School in Somerset and Clare College, Cambridge, graduating BA as 10th Wrangler in 1895. He is known for his work in the area of group theory...
, who in a series of papers On quantitative substitutional analysis developed representation theory of the symmetric group
Representation theory of the symmetric group
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 problems of quantum...
. 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
Algebraic combinatorics
Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra....
, forming the simplest example of a differential poset
Differential poset
In mathematics, a differential poset is a poset with operators D and U behaving like the operators x and d/dx on polynomials. In particular, DU-UD=1....
in the sense of . It is also closely connected with the crystal base
Crystal base
In algebra, a crystal base or canonical base is a base of a representation, such that generators of a quantum group or semisimple Lie algebra have a particularly simple action on it...
s for affine Lie algebra
Affine Lie algebra
In mathematics, an affine Lie algebra is an infinite-dimensional Lie algebra that is constructed in a canonical fashion out of a finite-dimensional simple Lie algebra. It is a Kac–Moody algebra for which the generalized Cartan matrix is positive semi-definite and has corank 1...
s.
Definition
Young's lattice is 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 Sn 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 Sn + 1 to Sn is multiplicity-free, and the representation of Sn with partition p is contained in the representation of Sn + 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 Sn with partition p, which is indexed by the standard Young tableaux of shape p.Properties
- The poset Y is gradedGraded posetIn mathematics, in the branch of combinatorics, a graded poset, sometimes called a ranked poset , is a partially ordered set P equipped with a rank function ρ from P to N compatible with the ordering such that whenever y covers x, then...
: 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 the join of two partitions is 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 latticeDistributive latticeIn mathematics, distributive lattices are lattices for 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...
. - If a partition p coversCovering relationIn mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours...
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 functionIncidence algebraIn order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for any locally finite partially ordered setand commutative ring with unity.-Definition:...
of Young's lattice takes values 0, ±1. It is given by the formula
-
-
Dihedral symmetry
Conventionally, Young's lattice is depicted in a Hasse diagramHasse diagramIn order theory, a branch of mathematics, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction...
with all elements of the same rank shown at the same height above the bottom.
has shown that a different way of depicting some subsets of Young's lattice shows some unexpected symmetries.
The partition
of the nth triangular numberTriangular numberA triangular number or triangle number numbers the objects that can form an equilateral triangle, as in the diagram on the right. The nth triangle number is the number of dots in a triangle with n dots on a side; it is the sum of the n natural numbers from 1 to n...
has a Ferrers diagram that looks like a staircase. The largest elements whose Ferrers diagrams are rectangular that lie under the staircase are these:
-
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)th dihedral groupDihedral groupIn mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...
acts faithfullyGroup actionIn algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
on this set. The size of this set is 2n.
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 D5 acts faithfully on this subset of Young's lattice.
-
-
