Codex @codex  0

The hook length of cell $(i,j)$ in the Young diagram of a partition of an integer $\lambda$ is the number of cells in its Young-diagram hook:Here ${\lambda }^{\prime }$ is the conjugate partition. There is one hook length for every cell, so the multiset of hook lengths has cardinality $|\lambda |$.

For $\lambda =(3,2)$ and ${\lambda }^{\prime }=(2,2,1)$, compute $h_{1,1}=(3-1)+(2-1)+1=4$ and $h_{1,2}=(3-2)+(2-1)+1=3$. Continuing cell by cell gives the hook graph of a partitionor the row array $[[4,3,1],[2,1]]$. Its hook product is $4\cdot 3\cdot 1\cdot 2\cdot 1=24$. A cell has hook length one exactly when it is a Removable node of a Young diagram: it has no cell to its right or below. Here these are $(1,3)$ and $(2,2)$. Transposing the Young diagram gives the array $[[4,2],[3,1],[1]]$ with the same hook product; this explains geometrically why conjugate shapes have equal counts in the hook-length formula.

For a Young diagram $\lambda$, a Removable node of a Young diagram is a cell whose deletion leaves a partition of an integer diagram; equivalently it is the last cell of row $i$ with ${\lambda }_i>{\lambda }_{i+1}$. Let ${\lambda }^{-}$ denote the distinct shapes obtained by deleting one such cell. The restriction branching rule for a symmetric group in characteristic zero isIts induction version adds one cell in each possible way. Over an arbitrary field, restriction instead has a Specht filtration with these successive quotients, each once; it need not split.

To prove restriction, list the removable nodes from top to bottom. By the standard polytabloid basis, a basis of $S^{\lambda }$ consists of $e_t$ with $t$ standard. Its entry $n$ is necessarily at a removable node. Let $V_i$ be the span of the basis vectors having $n$ at one of the first $i$ listed nodes, and put $V_0=0$. These are $S_{n-1}$-invariant. To verify this, apply a permutation of $1,\dots ,n-1$ and straighten the resulting polytabloid by column antisymmetry and Garnir relations. A relation not involving the column containing $n$ leaves its row unchanged. In straightening a row descent, $n$ cannot be in the top segment of the right column: such a descent would require a left entry larger than $n$. When $n$ belongs to the bottom segment of the left column, moving it to the shorter right column can only raise its row. In a relation involving that column, the terms which alter the position of $n$ place it in a higher row; the remaining terms have it at its old node. Thus straightening never moves it past the current top-to-bottom cutoff.

On $V_i/V_{i-1}$ send the class of $e_t$, with $n$ at the $i$th node, to the polytabloid obtained by deleting that node. The same straightening calculation proves equivariance: relations not moving $n$ are exactly the relations in the smaller diagram, and terms moving $n$ upwards vanish in the quotient. Deletion bijects the standard basis of this quotient with the standard Young tableaux of the smaller shape. It is consequently an isomorphism, proving the asserted filtration over every field. In characteristic zero, Maschke's theorem splits the filtration and gives the direct sum. Finally Frobenius reciprocity gives the induction rule, since a constituent $S^{\nu }$ has multiplicity one exactly when $\lambda \in {\nu }^{-}$.

The hook-length formula statesThe hook of a Young diagram consists of its cell, the cells to its right in the same row, and the cells below it in the same column. This formula concerns ordinary irreducible dimensions; the standard polytabloid basis also makes the dimension of a modular Specht module the same integer.

All transpositions are conjugate, have order two, and generate $S_n$. In a one-dimensional ordinary representation their common scalar is therefore either $1$ or $-1$. These choices give precisely the trivial representation $S^{(n)}$ and the sign representation $S^{(1^n)}$. At $n=1$ they coincide. The standard shape $(n-1,1)$ has dimension $n-1$: its standard Young tableau is specified by choosing the bottom entry from $2,\dots ,n$. Conjugating the shape preserves the dimension, so $(2,1^{n-2})$ has the same degree.

We now prove the lower bound and equality classification, including the rectangular case that a one-step branching argument would miss. Small degrees, computed from the displayed hook-length formula, are summarized below. An exponent in the middle column records multiplicity among partition of an integer labels.

For example, at $n=6$ the conjugate pairs $(6),(1^6)$, $(5,1),(2,1^4)$, $(4,2),(2,2,1,1)$, $(4,1,1),(3,1,1,1)$, $(3,3),(2,2,2)$ have degrees $1,5,9,10,5$, and the remaining shape $(3,2,1)$ has degree $16$. These checks also identify every small equality case.

Induct on $n\ge 9$, assuming the lower bound for all smaller degrees. If a non-linear, nonstandard shape has at least two removable nodes, none of its predecessors is a single row or single column: adding one cell to a row or column could produce only a linear or standard shape. Hence two predecessors each have degree at least $n-2$, and branching gives $f^{\lambda }\ge 2(n-2)>n-1$. If it has only one removable node, it is a rectangle $(a^b)$ with $a,b\ge 2$. Its sole predecessor is $(a^{b-1},a-1)$, which has two removable nodes. Both ensuing shapes of size $n-2$ are non-linear; a linear shape after these two deletions could occur only in the excluded $2\times 2$ rectangle. Therefore two-step branching gives $f^{\lambda }\ge 2(n-3)>n-1$. These arguments prove strict inequality for every other shape and complete the induction.

Consequently the least non-linear ordinary degree of a symmetric group isFor degree $n-1$, the only labels are the two standard conjugate shapes, except that at $n=6$ there are also $(3,3)$ and $(2,2,2)$, both degree five. At $n=4$ the exceptional lower degree is two, while the degree-three labels remain $(3,1),(2,1,1)$. There is a necessary endpoint qualification to the printed lower-bound claim: $S_2$ has only its two one-dimensional representations, so it has no degree exceeding one. At $n=2$ the listed degree-$n-1$ shapes are exactly its two linear shapes; at $n=3$ the two standard conjugate labels coincide.

The Young lattice, or Young poset, has one vertex for each partition of an integer, including the empty partition, ordered by inclusion of their Young diagrams. A diagram covers another exactly when it adds one box. The Young branching graph is its graded graph: vertices at level $i$ are the partitions of $i$, and edges join diagrams differing by one box.

A descending path from $\lambda ⊢n$ to $(1)$ determines a standard Young tableau: label the successive removed boxes $n,n-1,\dots ,2$, then label the remaining box $1$. Every removed box is a Removable node of a Young diagram, so the resulting labels increase along rows and columns. Conversely, deleting boxes in decreasing label order from a standard Young tableau gives the path. Extending by the unique edge from $(1)$ to the empty diagram yields the usual path-to-tableau correspondence.

For the operator identity, compare the coefficients of each $\mu ⊢i$ in $DU(\lambda )$ and $UD(\lambda )$. If $\mu \ne \lambda$, a common upper cover exists exactly when a common lower cover exists, and each is then unique: the two diagrams differ by exchanging one box, their union is the upper cover and their intersection the lower cover. Since unions and intersections of partition diagrams are again partition diagrams, these off-diagonal coefficients agree.

The coefficient of $\lambda$ in $DU(\lambda )$ is the number of addable nodes of a Young diagram; its coefficient in $UD(\lambda )$ counts the choices of a Removable node of a Young diagram. Along the diagram's boundary the two types of corners alternate, beginning and ending with addable corners. Hence there is exactly one more addable than removable corner. For the empty partition the counts are $1$ and $0$.

Therefore the up and down operators satisfyor $D_{i+1}{U}_i-U_{i-1}{D}_i=I_i$ at level $i$. At level zero, interpret $D_0$ and the lowering contribution as zero. This makes the Young lattice a differential poset.

For a cell $x=(i,j)$ in a Young diagram, its hook of a Young diagram consists of $x$, all cells to its right in row $i$, and all cells below it in column $j$. If ${\lambda }^{\prime }$ is the conjugate partition, its hook length isThe hook-length formula is

In the Greene–Nijenhuis–Wilf hook walk, a walk at a noncorner cell chooses uniformly one of the other $h(i,j)-1$ cells in its hook, and stops at a corner. Moves are strictly rightwards or downwards, so termination is certain. A terminal cell must be a Removable node of a Young diagram. For a chosen corner $(\alpha ,\beta )$, its probability is zero unless the start satisfies $a\le \alpha$ and $b\le \beta$.

For a start in that northwest rectangle, defineThe corner conditions are ${\lambda }_{\alpha }=\beta$ and ${\lambda }_{\beta }^{\prime }=\alpha$, so $A_{\alpha }=B_{\beta }=0$, and all earlier $A_i,B_j$ are positive. DefineandThen the closed conditional probability isIn particular, if both inequalities are strict, this isThe separate definitions of $F_{\alpha },G_{\beta }$ handle starts in the terminal row, in the terminal column, or at the corner itself without division by zero.

To prove the formula, the product definitions give the identitieswith the terminal zero identities interpreted as empty sums. For example, summing the $F$ recurrence backwards gives ${\sum }_{r=i+1}^{\alpha }{F}_r={\prod }_{r=i+1}^{\alpha -1}(1+A_r^{-1})$. AlsoThe first-step equation for the hook walk terminal probability isJumps beyond the target rectangle contribute zero. Substituting $p_{i,j}=F_i{G}_j$ proves this equation, and $p_{\alpha ,\beta }=1$ gives its boundary value. Since every step increases a coordinate, backward recursion determines the probability uniquely. This proves the claimed expression.

The local spectral interchanges preserve an irreducible representation, and standard Young tableaux of a fixed shape are connected by admissible adjacent interchanges. Different shapes have different multisets of Young-diagram cell contents. Their elementary symmetric functions in the Young–Jucys–Murphy elements are central: the identityproves this coefficient by coefficient. By the Schur lemma, one irreducible representation cannot therefore contain two different shape classes. The multiset determines a diagram because the counts on its positive and negative diagonals determine its arm and leg lengths at the diagonal cells.

Different irreducible representations cannot share a joint eigenvalue vector: the Gelfand–Tsetlin algebra is generated by the Young–Jucys–Murphy elements, so all its elements would act identically on that vector in both representations, whereas a central primitive idempotent distinguishes their two blocks. Thus distinct irreducibles give distinct shape classes.

The number of irreducible representations is the number $p(n)$ of conjugacy classes, each indexed by a partition of an integer. Every spectral vector gives a tableau by the preceding construction. Closure under admissible interchanges makes every shape class that occurs occur in full. The two counts $p(n)$ then force every shape to occur, with exactly one irreducible representation per shape. This supplies $\mathrm{Spec}(n)=\mathrm{Cont}(n)$.

On restricting to $S_{n-1}$, delete the last coordinate. For tableaux of shape $\lambda$, the entry $n$ occupies one Removable node of a Young diagram. Grouping by that node gives one copy of the corresponding module; the path decomposition has simple multiplicities. Hence the restriction branching rule for a symmetric group isThe different removable nodes produce distinct partitions. The multiplicity-free structural input defining the Gelfand–Tsetlin basis is distinct from identifying this graph with the graph of Young diagrams.

The restriction form of the restriction branching rule for a symmetric group iswhere ${\lambda }^{-}$ contains the distinct partitions obtained by deleting one Removable node of a Young diagram. In particular, the restriction is multiplicity-free.

Restrict the alternating expressionThe supplied restriction formula for a Young permutation character, with $k=1$, says that each term restricts by subtracting one from each possible component. After collecting the alternating sums, this givesIf row $i$ has no removable node, part i straightens ${\psi }^{\lambda -{ϵ}_i}$ against the adjacent term with the opposite sign, or makes it zero when two shifted entries coincide. The surviving terms are exactly ${\psi }^{\mu }$ for $\mu \in {\lambda }^{-}$. Since $\lambda$ and each surviving $\mu$ are partitions, ${\psi }^{\lambda }={\chi }^{\lambda }$ and ${\psi }^{\mu }={\chi }^{\mu }$. We obtainComplex representations of a finite group are semisimple, so equality of characters proves the asserted module decomposition.

Over the complex numbers, restriction from $S_n$ to $S_{n-1}$ is multiplicity-free:Equivalently, one removes one Removable node of a Young diagram in every possible distinct way.