The celebrated Robinson-Schensted (RS) correspondence [1,2] gives a bijection between words w in the alphabet {1, 2, . . . , n} of length k and a pair of tableaux of the same shape λ, a partition of k with at most n parts, where the first tableau is a semistandard Young tableau in the same alphabet and the second tableau is a standard tableau. Schensted [2] proved that λ 1 (the biggest part of the partition λ) is the length of the longest increasing subword of w. Knuth's generalization of the RS correspondence [3], known as the RSK correspondence, provides a bijective proof of the Cauchy identity in symmetric function theory
where the sum is over all partitions λ and s λ (x) is the Schur function in the variables x 1 , x 2 , . . . indexed by the partition λ. In [4], W. Burge gives four variants of the RSK correspondence. In this paper, we focus on the correspondence in [4, Section 4], which gives a bijection between simple labelled graphs (graphs without loops or multiple edges) and semistandard Young tableaux of threshold shape. A partition λ = (λ 1 , λ 2 , . . . , λ n ) is called threshold if λ t i = λ i + 1 for all 1 ⩽ i ⩽ d(λ), where λ t i is the length of ith column of the Young diagram of λ and d(λ) is the maximal d such that (d, d) ∈ λ. We call this bijection the Burge correspondence. The Burge correspondence gives a bijective proof of the Littlewood identity [5, Exer. I.5.9(a) and I.8.6(c)]
where the sum runs over all threshold partitions. For more details about the representation theoretic significance of the Burge correspondence, see [6].
In this paper, we characterize the graphs whose shapes under the Burge correspondence are hook shapes in terms of peak and valley conditions. This is the first step towards an analogue for the Burge correspondence of Schensted's result for the RS correspondence, namely that increasing sequences under the RS correspondence give tableaux of single row shape.
Threshold partitions also play an important role in graph theory. Given a simple graph G = ([n], E) with vertex set [n] = {1, 2, . . . , n} and edge set E, the degree d i of a vertex i is the number of neighbours of i. The degree sequence of G is the tuple d G = (d 1 , d 2 , . . . , d n ). One of the central questions in graph theory is the characterization of all sequences that appear as degree sequences of a simple graph (see for example [7][8][9][10][11]). The Erdös-Gallai theorem [7] gives a characterization of graphic partitions, that is, partitions that are degree sequences of a simple graph.
Define X G := x
is a symmetric function in x 1 , x 2 , . . ., where the sum runs over all simple graphs G. Note that the right hand side is the right hand side in Littlewood's identity (1.1). Hence, from (1.1) and the Burge correspondence, it follows that a sequence
is a degree sequence of a simple graph G if and only if d ⩽ λ for some threshold partition λ, where ⩽ is the dominance order for partitions. In [12],
Gasharov proved that this condition is equivalent to the Erdös-Gallai theorem. Hence threshold partitions are the maximal graphic partitions.
The degree partition of G is the partition dG obtained by rearranging d G in weakly decreasing manner. A graph G is called threshold if the associated degree partition is threshold. For alternative definitions and characterizations of threshold graphs, see [10,Chapter 3]. Threshold graphs can be interpreted in an extremal sense. First, the threshold partitions (the degree partitions of threshold graphs) are maximal among graphic partitions. Second, the threshold partitions of n are the extreme points of the degree partition polytope, the convex hull of all degree partitions of simple graphs on n, see [13] and references therein.
Example 1.1. The simple graph in Fig. 1 is threshold as its degree partition (3, 2, 2, 1) is threshold.
The condition λ t i = λ i + 1 for threshold partitions is in fact Merris' and Roby's reformulation [11] of conditions stated by Ruch and Gutman [8]. Klivans and Reiner [14] give some generalizations of these concepts to hypergraphs and related them to plethysm.
In this paper, we characterize when the shape λ G of a simple graph G is a hook shape. This is done by analysing the Burge correspondence and imposing peak and valley conditions on the Burge array corresponding to G. In addition, we impose a crystal structure on simple graphs of hook shape. Crystal graphs are combinatorial skeletons of Lie algebra representations (see for example [15,16]).
The extremal vectors in this crystal are precisely the simple graphs whose degree sequence is threshold.
The paper is organized as follows. In Section 2, we review the Burge correspondence and prove some results regarding standardization. In Section 3, we provide the characterization of simple graphs of hook shape. Finally in Section 4, we give the crystal structure on simple graphs of hook shape.
In this section, we define the Burge correspondence [4]. We review some preliminaries in Section 2.1. We remind the reader of Schensted's result on longest increasing subwords of words in Section 2.2 before introducing the Burge correspondence in Section 2.3. In Section 2.4, we show that the Burge correspondence intertwines with standardization.
A partition λ of a nonnegative integer n, denoted by λ ⊢ n, is a weakly decreasing sequence λ
of λ is a left-justified array of boxes with λ i boxes in row i from the top. (This is also known as the English convention for Young diagrams of partitions). A partition λ is a hook if Y (λ) does not contain any 2 × 2 squares. Definition 2.1. Let λ be a partition. A semistandard Young tableau of shape λ in the alphabet [n] := {1, 2, . . . , n} is a filling of the Young diagram of λ with letters in [n] such that the numbers weakly increase along rows and strictly increase along columns. We denote by Tab n (λ) the set of all semistandard Young tableaux of shape λ in the alphabet [n].
Let T be a semistandard Young tableau. The shape of T is denoted sh(T ). The weight of a semistandard Young tableau T , denoted wt(T ), is the integer vector (µ 1 , . . . , µ n ), where µ i is the number of times the number i occurs. The subset of Tab n (λ) consisting of all semistandard Young tableaux of weight µ is denoted by Tab(λ, µ).
Given an integer vector µ = (µ 1 , . . . , µ n ), let x µ denote the monomial x
Definition 2.2. For each integer partition λ, the Schur polynomial in n variables corresponding to λ is defined as
x wt(T ) .
The Burge correspondence (as well as the celebrated Robinson-Schensted-Knuth (RSK) correspondence) uses the Schensted row insertion algorithm. Given a semistandard Young tableau T in the alphabet [n], a letter i ∈ [n] can be inserted into T in the following way: if i is larger than or equal to all the entries of the first row of T , a new box containing i is added at the end of first row and the process stops. Otherwise, i replaces the smallest leftmost number j of the first row such that j > i. Then j is inserted in the second row of T in the same way and so on. The procedure stops when a new box is added to T at the end of a row. The result is denoted T ← i. The shape of T ← i contains one new box compared to the shape of T .
Given a tableau T and a letter x that lies at the end of some row of T , the Schensted reverse bumping algorithm generates a pair of a tableau T ′ and a letter y in the following way: Let t be the row index of x and x 1 be the rightmost entry of row t -1 such that x 1 < x. Replace x 1 by x in T and output x 1 . Repeat the process for x 1 and continue until an element of the first row say y is obtained as output. The resulting tableau is T ′ . We shall denote the pair (T ′ , y) by T → x.
Given a word w = w 1 w 2 . . . w k in the alphabet {1, 2, . . . , n}, the Schensted insertion tableau is defined as P(w) := ∅ ← w 1 ← w 2 ← • • • ← w k . The shape of the semistandard Young tableau P(w), denoted λ(w) = (λ 1 , λ 2 , . . .), is called the shape of the word w. Schensted [2] proved that λ 1 is the length of the longest increasing subword of w. In particular, the shape λ(w) is a single row if w is weakly increasing. Greene [17] extended the result of Schensted by interpreting the rest of the shape of λ. For a poset theoretic viewpoint of the map w ↦ → λ(w) and various applications including in the context of flag varieties, see Britz and Fomin [18] and references therein. In the same spirit, we ask very similar questions about the Burge correspondence introduced in the next subsection.
We begin by recalling the definition of a Burge array from [4,Section 4].
(2) The top line is weakly increasing, that is, a k ⩽ a k+1 for all 1 ⩽ k < r.
( Having defined all the necessary tools, we now state the main algorithm of the Burge correspondence. Starting with the empty tableau T 0 , we shall insert all the edges of G, as ordered in A G , into T 0 . Let T k be the tableau obtained by inserting the edge (a k , b k ) into T k-1 in the following way:
(1) First insert b k into T k-1 using the Schensted insertion algorithm. This adds a new cell to the shape, say in position (s k , t k ).
(2) Place the entry a k in the cell op(s k , t k ). Observe that each addition of an edge transforms a tableau of threshold shape to another tableau of threshold shape.
Finally, the tableau T G := T r is the threshold tableau associated with the graph G under the Burge correspondence.
Burge [4] proved that this tableau is semistandard. Given such a tableau T , we recover the Burge array in the following way: Let a r be the largest entry of T with largest column index. Remove a r from T . Let z r be the value at the opposite position of the cell containing a r . Let b r = y r where T → z r = (T r-1 , y r ). Repeat the process for T r-1 and continue until the empty tableau is obtained in the output.
. The associated tableau T G of threshold shape (3, 2, 2, 1) is obtained by inserting the edges of G as ordered in A G as depicted in Fig. 2.
In the same spirit as the shape of a word under the RSK correspondence, we can define the shape of a graph under the Burge correspondence. It can be observed that the shape of a threshold graph G is its degree partition dG . Namely, let G be a threshold graph with degree sequence d G . If T is the semistandard Young tableau of threshold shape λ and weight d G , then d G is less than or equal to λ in dominance order. Since d G is a threshold sequence by assumption, we know that the only partition that dominates a threshold sequence is the corresponding partition. Hence λ = dG .
We call a simple graph G a hook-graph if the associated tableau T G has hook shape. Given the nature of the Burge algorithm, determining when a T G has hook shape is analogous to asking when a tableau under the RSK algorithm has single row shape. Problem 2.6. What is the shape of a simple graph?
In the next section, we characterize all hook-graphs.
Both Tab m (λ) and words over [m] with length n have the notion of standardization. Standardization intertwines with RSK in the sense that they form a commuting diagram. We show that an analogous result holds true for the Burge correspondence.
First, we review the standardization map for semistandard Young tableaux. Let λ ⊢ n and let
The standardization of T ∈ Tab(λ, µ) with respect to the alphabet C , denoted by stand C (T ), is the map replacing all the 1's in T from left to right with the numbers c 1 through c µ 1 , replacing all the 2's from left to right with the numbers c µ 1 +1 through c µ 1 +µ 2 , etc.
The standardization map on words over the alphabet [m] can be defined similarly. Let ω be a word using the alphabet [m] with length n and let µ denote its content. In other words, let µ = (µ 1 , µ 2 , . . . , µ m ) be an integer vector, where µ i denotes the number of i's in ω. The standardization of ω with respect to C , which we also denote by stand C (ω), is defined by replacing the 1's in ω from left to right with the numbers c 1 through c µ 1 , replacing the 2's in ω from left to right with the numbers c µ 1 +1 through c µ 1 +µ 2 , etc. The following result formalizes the relationship between standardization and RSK, see for example [19,Lemma 7.11.6].
Let ω be a word in the alphabet [m] with length n. Then stand C (P(ω)) = P(stand C (ω)).
Analogously, we define the standardization of a Burge array A G . Given a Burge array A G with r columns and a subset C = {c 1 < • • • < c 2r } of N, define the standardization of A G with respect to C , denoted by stand C (A G ), to be the map that replaces the 1's in A G from left to right with the numbers c 1 through c d 1 , replaces the 2's from left to right with the numbers
For T a semistandard Young tableau, the reading word of T denoted by R(T ) is obtained by reading the entries within a row from left to right starting with the bottommost row.
that the base case of r = 0 is trivial. Let A r-1 (resp. B r-1 ) denote the Burge array formed by the first r -
). As the reading word
Thus the a r and c 2r must be placed in the same position of their respective tableau. From the inverse of the Burge correspondence, a r is the largest value in T G and lies in a column to the right of any equivalent letters. Therefore, a r in T G gets sent to c 2r by stand C and does not affect the mapping of the other letters in the tableau. Hence,
While answering Problem 2.6 in full generality seems far-achieving, we determine necessary and sufficient conditions of a hook graph in this section.
We begin by establishing a necessary condition for a connected graph to be of hook shape.
that contain at least one edge. If G contains k edges e 1 , . . . , e k such that G -{e 1 , . . . , e k } has the same number of connected components as G, then G is not a hook-graph.
However, the length of the partition (e, 1 e ) is at least n+1, where e ⩾ n is the number of edges of G.
This implies that the partition (e, 1 e ) is not weakly greater than dG in dominance order. Thus, there are no semistandard Young tableaux of shape (e, 1 e ) with weight d G , and T G is not hook-shaped. □ Recall that an undirected graph is called a tree if it is connected and does not contain any cycle.
Setting k = 1 into Proposition 3.1, we obtain the following necessary condition for connected (excluding singletons) hook-graphs.
Remark 3.3. A tree need not be a hook-graph always. For example, the tree whose Burge array is
has the shape (2, 2, 2).
We now introduce peak and valley conditions which characterize when a graph has hook shape.
(1) The graph with Burge array
(
Note that b 1 < b 4 < b 3 , but j = 3 is not the minimal j satisfying this condition. Also, A G does not have a valley. (3) The graph considered in Example 2.4 has both a peak and a valley.
We refer to a Burge array as being PV-free if the Burge array does not contain a peak or a valley.
Proof. We prove the equivalent statement that the shape of G is non-hook if and only if G has either a peak or a valley.
Let T G be the tableau of non-hook shape associated with the Burge array
. Let T ℓ denote the tableau corresponding to the sub-array consisting of the first
Choose k minimal such that the shape of T k is non-hook, that is, let k be the column that creates the cells (2, 2) and (3, 2) when applying the Burge algorithm. We claim that there exist
is either a peak or a valley.
Let x be the first row entry of T k-1 that is bumped by b k in kth step of the Burge algorithm. Let y be the entry in position (2, 1) (first entry of 2nd row) of T k-1 , see Fig. 3. Note that x > b k and y ⩽ x.
There are two different cases depending on whether x is an inserted letter or a recorded letter.
Case 1: Let x be the inserted letter b j for some 1 < j ⩽ k -1. index between 1 and
bump an entry weakly larger than y and the shape of T k-1 becomes non-hook. This contradicts the minimality of k. Hence a m ⩽ b j . Also note that j is the smallest index between m and k satisfying b m ⩽ b k < b j as otherwise this would contradict the choice of y or x. Hence the claim is true.
Case 2: Let x be a recorded letter say a j for 1 < j ⩽ k -1. This implies y = b i for some i as y can no longer be the recording letter a 1 .
Now we shall prove that the shape of T G is non-hook if G has either a valley or a peak. We start by proving the result for the case of a valley.
. We may assume that there is no peak or valley in the first k -1 columns of A G and that T k-1 has hook shape. We consider two cases.
Assume that b i is present in the first row of T j-1 . Since b i > b j , b j bumps an element, say x, from the first row of T j-1 . So b j < x ⩽ b i . Since b j bumps a letter in the first row and since by assumption T j has hook shape, it follows that a j must be in the first row of T j . Note that a j must also be in the first row of T k-1 . This is because if an element say b ℓ (insertion letter) bumps a j from the first row before the insertion of b k , then T ℓ has non-hook shape since a j ⩾ a 1 , which is greater or equal to the letter in cell (2, 1).
Since we have b j ⩽ b k < a j , b k bumps an element (which lies in the first row of T k-1 ), say y. Then b j < y ⩽ a j . We claim that x ⩽ y. If y < x, note that y was not in T j-1 when b j was inserted, since otherwise b j would have bumped y. So b j < y < x ⩽ b i < a i < a j . This shows that y must be an inserted letter, say b ℓ with j < ℓ < k, and we have a valley formed by columns i, j, ℓ. This is a contradiction to our assumption. Therefore we must have x ⩽ y. In this case the shape of T k becomes non-hook, because the entry in cell (2, 1) of T k-1 is less than or equal to x and so y must be placed in the (2, 2) position of T k .
Case 2: Assume that b i is not present in the first row of T j-1 . Let x be the element in T j-1 in the position where b i was originally inserted. Since x < b i and x is inserted after step i, x must be an inserted letter, say b ℓ with i < ℓ < j. We claim that b ℓ > b j . If not, we have b ℓ ⩽ b j and
This is a contradiction. Hence b ℓ > b j . This implies that b j must bump an element from the first row of T j-1 . If z is that element, then b j < z ⩽ b ℓ . Also, since b j bumps an element, a j must be in the first row in T j . By the same arguments as in Case 1, a j must be in the first row in T k-1 . Since by the valley condition b k < a j , b k bumps an element in T k-1 . Call this element w. We claim that z ⩽ w. If w < z, note that w was not in T j-1 since then b j ⩽ b k < w < z and hence b j would have bumped
forms a valley as b m = w < z ⩽ b ℓ < a ℓ ⩽ a j . This is a contradiction. If w is a recorded letter, then w ⩾ a j ⩾ a ℓ > b ℓ ⩾ z, contradicting the assumption that w < z. This proves z ⩽ w. Hence w must be placed in position (2, 2) of T k . This implies that the shape of T k is non-hook.
Considering the above cases, we conclude that T G has non-hook shape when A G has a valley.
. As before, we may assume that there is no valley or peak in first k -1 columns of A G and that T k-1 has hook shape.
Claim. b j cannot be bumped from the first row before the kth step.
Proof. Assume that b j is bumped from the first row before the kth column is inserted. This would create a non-hook shape as b j ⩾ a i ⩾ a 1 . This contradicts the fact that T k-1 has hook shape. Hence we have proved the claim. Subcase B: b i bumps an element from the first row of T i-1 when inserted. Then a i is placed in the first row of T i . Let u be the value bumped by b i when inserted to T i-1 and let z be the value bumped by b k . So, b i < u and b k < z. Notice that the entry in position (2, 1) of T k-1 is less than or equal to u. So, if u ⩽ z, the shape of T k becomes non-hook.
On the contrary, suppose u > z. Then z is not in the first row of T i-1 since otherwise b i would bump z instead of u as b i ⩽ b k < z < u. This contradicts the definition of u. Hence z is inserted after the ith step. As b i bumps u from the first row of T i-1 , u is weakly less than a i . As z is inserted after the ith step, it must be an inserted letter i.e. z = b ℓ for some i < ℓ < k. Now either z < a i or z ⩾ a i . Assume that z < a i . We prove that there does not exists an inserted letter b t such that i < t < k and b i ⩽ b t < a i . Assume that there exists such an inserted letter b t , where t is the smallest possible index. Observe that when b t is inserted it bumps an element strictly right of b i and weakly left of a i in the arm of T t-1 . Denote this element by w. From the minimality of t, we have w is present in the first row of T i-1 and is strictly to the right of u. Thus, w is weakly larger than u, and when w is bumped, it will be weakly larger than the value in the (2, 1) cell of T t-1 . This would contradict T k-1 being hook shaped. Therefore no such inserted letter b t exists. Observe that z satisfies the condition of b t namely z = b ℓ where i < ℓ < k and b i ⩽ b ℓ < a i . By our claim this is impossible.
Next consider the case z ⩾ a i . Note that a 1 ⩾ u as both of them are placed in first column.
Together with u > z ⩾ a i we get a 1 > a i , which is not possible. Therefore the case u > z does not arise.
Considering all the cases, we proved that the shape of T k is non-hook when A G has a peak. This completes the proof. □ Remark 3.8. Theorem 3.7 is the analogue to the statement for RSK that the shape of a word w under RSK is a single row if and only if w is weakly increasing. Remark 3.9. In analogy with Schensted's result for the RSK insertion that the length of the longest increasing subsequence of a word w gives the length of the longest row in the Young tableaux under RSK, one might suspect that the longest PV-free subsequence of a Burge array gives the size of the largest hook in sh(T G ). However, this is not true as the following counterexample shows. Take the graph G with Burge array
] .
The tableau under the Burge correspondence is
, so that sh(T G ) = (3, 3, 2, 2). However, the subsequence
is PV-free and has hook shape (4, 1, 1, 1, 1), which is larger than the biggest hook (3, 1, 1, 1) in sh(T G ).
A star graph is a graph where one vertex i is connected to all other vertices by an edge and no other edges exist in the graph. Proof. Assuming that the vertices of the star graph are labelled 1, 2, . . . , n and the vertex connected to all other vertices is vertex i, the Burge array is
which is PV-free. □
We review the crystal structure on semistandard Young tableaux in Section 4.1 and then define the new crystal structure on hook-graphs in Section 4.2.
Crystal bases provide a combinatorial skeleton for U q (g)-representations, where U q (g) is the quantum group associated to the Lie algebra g. A Kashiwara crystal is a nonempty set B together with maps
where Λ is the weight lattice associated to the Lie algebra g and I is the index set of the Dynkin diagram for g. These maps have to satisfy certain conditions (see [15,Definition 2.13]).
For simply-laced Lie algebras g, a Stembridge crystal is a Kashiwara crystal for which the raising and lowering operators e i and f i satisfy certain local rules (see [15,Section 4.2]). Stembridge crystals are crystals corresponding to U q (g)-representations.
Two words ω and ν are said to be Knuth equivalent if they differ by a sequence of Knuth moves.
It is well-known that ω and ν are Knuth equivalent if and only if P(ω) = P(ν), that is, their insertion tableaux under Schensted insertion are equal. In addition, it is also known that the crystal operators f i and e i on words preserve Knuth equivalence. Thus, in order to define the crystal operators on semistandard Young tableaux it suffices to look at their reading words. Definition 4.3. Let T be a semistandard Young tableau in Tab m (λ). Assign a ')' to every i in R i (T ) and a '(' to every i + 1 in R i (T ). Successively pair every '(' that is directly left of a ')' which we call an i-pair and remove the i-paired terms. Continue this process until no more terms can be i-paired.
The lowering operator f i for 1 ⩽ i < m acts on T as follows:
(1) If there are no unpaired ')' terms left, then f i annihilates T .
(2) Otherwise locate the i in T corresponding to the rightmost unpaired ')' of R i (T ) and replace it with an i + 1.
The raising operator e i for 1 ⩽ i < m acts on T as follows:
(1) If there are no unpaired '(' terms left, then e i annihilates T .
(2) Otherwise locate the i + 1 in T corresponding to the leftmost unpaired '(' of R i (T ) and replace it with an i.
The weight wt(T ) = (a 1 , a 2 , . . . , a m ) is an m-tuple such that a i is the number of letters i in T .
The crystal lowering and raising operators f i and e i for 1 ⩽ i < m together with the weight function wt define a crystal structure on Tab m (λ). The vertices of the crystal are the elements in Tab m (λ) for a fixed partition λ. There is an edge labelled i from T ∈ Tab m (λ) to T ′ ∈ Tab m (λ) if f i (T ) = T ′ . Note that f i and e i are partial inverses, that is, if f i (T ) = T ′ then e i (T ′ ) = T and vice versa.
In this section, we assume that G is a hook-graph or equivalently by Theorem 3.7 that A G is a PV -free Burge array. Definition 4.4. The ith reading word of A G , denoted by Ri (A G ), is obtained by the following algorithm:
(1) Let a k denote the leftmost i + 1 in the top row of 2) Read all other i's and (i + 1)'s in A G from left to right while appending the corresponding value to Ri (A G ).
, then it must be the leftmost column containing i + 1 in the top row since by the definition of a Burge array the bottom row is decreasing for equal top row elements. Hence a k is this leftmost i + 1 and either
Definition 4.7. Assign a ')' to every i in Ri (A G ) and a '(' to every i + 1 in Ri (A G ). Successively pair every '(' that is directly left of a ')', called an i-pair, and remove the paired terms. Continue this process until no more terms can be paired.
The operator fi acts on A G as follows:
(1) If there are no unpaired ')' terms left, then fi annihilates A G denoted by fi (A G ) = 0.
(2) Otherwise locate the i in A G corresponding to the rightmost unpaired ')' and denote it by x.
(a) If there is no i + 1 in the same column as x, then fi changes x in A G to an i + 1. (b) If there is an i + 1 in the same column as x, then x is on the bottom row of
Let ℓ ⩽ m ⩽ k be the largest index such that b m < a ℓ . In the top row of A G replace a k-1 with an i + 1 and replace a s with a s+1 for ℓ ⩽ s ⩽ k -2. In the bottom row of A G replace b m with a ℓ and replace b k with b m . (Remark: Observe that in this case k ̸ = 1 as otherwise the i + 1 and i in this column would form an i-pair in Ri . Thus, this operation is well-defined.) This procedure is illustrated in Fig. 4.
The operator ẽi acts on A G as follows:
(1) If there are no unpaired '(' terms left, then ẽi annihilates A G denoted by ẽi (A G ) = 0.
(2) Otherwise locate the i + 1 in A G corresponding to the leftmost unpaired '(' and denote it by
x.
(a) If x is in the top row of A G and there is an i +1 directly to the left of it, then let k be the index such that
In the top row of A G replace a ℓ with b m and replace a s with a s- ]
.
The fact that a non-annihilated fi (A G ) (resp. ẽi (A G )) is a PV -free Burge array or even a valid Burge array will be shown as a consequence of Proposition 4.11.
Lemma 4.9. Ri (A G ) has at most one i-pair.
Proof. Assume that Ri (A G ) has at least two i-pairs. This implies that A G contains at least two (i+1)'s.
Let j be the index of the column containing the leftmost i + 1 and k be the index of the column containing the second leftmost i + 1. We break into cases based on the position of the (i + 1)'s in columns j and k.
Case 1: Assume that a j = i + 1 and a k = i + 1. This implies that a k is the second leftmost i + 1 in Ri (A G ). Since A G is assumed to have at least two i-pairs, there must exist ℓ > k such that b ℓ = i.
The subarray
This contradicts A G being a PV -free Burge array.
Case 2: Assume that a j = i + 1 and b k = i + 1. This once again implies that b k is the second leftmost i + 1 in Ri (A G ). As A G contains at least two i-pairs, there must exist ℓ > k such that b ℓ = i. Let j < s < ℓ be the leftmost index such that b j ⩽ i = b ℓ < b s . Note that such an s exists as k satisfies the desired conditions. The subarray
and a j = i + 1 ⩽ b s . This contradicts A G being a PV -free Burge array.
Case 3: Assume that b j = i + 1 and b k = i + 1. This implies that b j is the leftmost i + 1 in Ri (A G ). To have at least two i-pairs, A G must contain columns ℓ and m such that j < ℓ < m and
This contradicts A G being a PV -free Burge array. □ Lemma 4.10. Let T G be the threshold tableau associated to A G under the Burge correspondence. Then
Proof. Since T G is a hook tableau, R i (T G ) has at most one i-pair. Thus by Lemma 4.9 it suffices to prove that Ri (A G ) has an i-pair if and only if R i (T G ) has an i-pair, since the content of T G and A G are the same.
Assume that Ri (A G ) has an i-pair. Let k be the index of the column containing the i + 1 that is in the i-pair. First assume that a
when inserted, does not bump an element. Otherwise it would bump an element greater than the element bumped by b k-1 which would create a non-hook shape. Thus, a k is recorded in the leg of T G and R i (T G ) has an i-pair. If b k-1 > b k , then in order for Ri (A G ) to have an i-pair, there must exist ℓ > k such that b ℓ = i. The subarray
In order for Ri (A G ) to have an i-pair, there must exist ℓ > k such that b ℓ = i. This implies that some i + 1 must be bumped into the leg by an insertion letter whose index is at most ℓ. Thus, T G has an i + 1 in its leg and R i (T G ) has an i-pair. Thus, R i (T G ) has an i-pair whenever Ri (A G ) has an i-pair.
Assume that R i (T G ) has an i-pair. This implies that T G has an i + 1 in its leg. If the i + 1 in the leg corresponds to a recording letter a j for some j, then b j does not bump an element when inserted.
Otherwise a j = i + 1 would get placed in the first row of T G and cannot be bumped into the leg as a 1 ⩽ a j . This implies that either j = 1 or b j-1 ⩽ b j . In either case, Ri (A G ) contains an i-pair. Assume the i + 1 in the leg corresponds to an insertion letter b j . Since b j must be bumped into the leg and be i-paired with some i, there exists j < k such that b k = i. This implies that Ri (A G ) contains an i-pair. Thus, Ri (A G ) has an i-pair whenever R i (T G ) has an i-pair. □ Proposition 4.11. Let A G be a PV-free Burge array and let T G be its associated threshold tableau.
(1
(2) If ẽi (A G ) ̸ = 0, then ẽi (A G ) = ÃG , where ÃG is the associated Burge array of e i (T G ).
Proof. As fi and ẽi are clearly partial inverses, it suffices to just prove part (1). From Lemma 4.10, we have that f i (T G ) is not annihilated. Let s be the column index of the rightmost i in A G and denote this rightmost i by ¯i. We claim that ¯i corresponds to the rightmost i in R i (T G ). If b s = ¯i, then ¯i is inserted into the arm to the right of all preexisting i's when column s is inserted and will remain the rightmost i by the properties of Schensted row insertions. If a s = ¯i and a s-1 = i, then when column s is inserted b s will bump an element from the arm. As T G is hook-shaped, a s = ¯i will be recorded into the arm to the right of all preexisting i's and will remain the rightmost i. If a s = ¯i and a s-1 ̸ = i, then a s is the only i in A G and is trivially the rightmost i in R i (T G ) which proves our claim. As f i (T G ) is not annihilated and T G is hook-shaped, ¯i is the rightmost unpaired i of T G and is changed to an i + 1 by f i .
Let r be the column index of the last column of A G . We denote by S t the tableau obtained by reverse inserting columns t + 1 through r of f i (T G ) and T t the tableau obtained by inserting columns 1 through t of A G . We first assume that r > s and prove that columns s + 1 through r are the same in both arrays so that we may take r to be the same as s later in the proof. More specifically using induction, we will prove that for s + 1 ⩽ t ⩽ r column t of A ′ G is the same as column t in A G and
Let ℓ and a be the largest entries in the leg and arm of T r = T G , respectively. Note that ℓ and a are also the largest entries in the leg and arm of S r = f i (T G ), respectively, as r > s. We break into subcases depending on whether ℓ > a or ℓ ⩽ a.
When ℓ > a, the column [ℓ, a] T is obtained by reverse inserting both T r and S r implying the rth column of A ′ G is the same as the rth column of A G . We claim that ℓ > i + 1. This is clearly true if ¯i is in the leg of T G as we assume r > s. If ¯i is in the arm of T r , then a ⩾ i + 1 as a is to the right of ¯i and ¯i is the rightmost i in T r . Hence the claim is true, and ¯i remains the rightmost unpaired i in T r-1 . Thus, f i acts on T r-1 by changing ¯i to an i + 1 which is precisely S r-1 .
When ℓ ⩽ a, a is removed from T r and a number which we denote by b r is reverse inserted. This implies that the rth column of A G is [a, b r ] T . Similarly, reverse inserting a column from S r , a is removed from S r and a number which we denote by c r is reverse inserted. Note that b r and c r are equal and are in the same cell of their corresponding tableau except if an i and i + 1 lie in the arm of S r and the (2, 1) cell of S r is an i + 1. If an i and i + 1 lie in the arm of S r , then the value of the (2, 1) entry in T r cannot be ¯i as this would contradict ¯i being the rightmost unpaired i of T r . Thus, if an i and i + 1 lie in the arm of S r and the (2, 1) cell of S r is an i + 1, then the (2, 1) cell of T r is an i + 1. However, this would imply b r = i as it would need to bump an i + 1 so that a is in the arm of T r , an i + 1 is in the (2, 1) cell, and the i in the arm is not bumped. This contradicts r > s.
Therefore the rth column of A G and A ′ G match. As b r ̸ = i, ¯i is still the rightmost unpaired i of T r-1 and f i (T r-1 ) = S r-1 . Assume that column t of A ′ G is the same as column t in A G and S t-1 = f i (T t-1 ) for some s + 1 < t ⩽ r. Repeating the argument in the base case, we see that this holds for the case t -1 as well.
From the definition of fi , we have that the columns s + 1 through r of fi (A G ) are the same as the columns s + 1 through r of A G . By the previous paragraph, these columns are also equal to columns s + 1 through r of A ′ G . We now assume that r = s and prove that the columns 1 through s of fi (A G )
and A ′ G are equal by breaking into cases based off the position of ¯i in T s . Case 1: ¯i is in the leg of T s .
Since ¯i is the rightmost unpaired i of T s , this implies that T s does not contain any other i except for ¯i. Also in order for ¯i to be in column s of A G , we must have a s = ¯i. Thus, the column obtained from T s by reverse inserting is of the form [ ¯i, a] T where a is the largest value in the arm of T s . In S s , ¯i is replaced with an i + 1. Thus, the column obtained from S s by reverse inserting is of the form [i + 1, a] T . We see that T s-1 and S s-1 are equal implying columns 1 through s -1 of A G and A ′ G are equal. Note that as ¯i is the only i in A G and a s = ¯i, we have fi acts by changing ¯i to an i + 1 in A G .
Case 2: ¯i is in the arm of T s .
Let ℓ and a be the largest elements in the leg and arm of T s , respectively. We break into subcases. Assume ¯i ⩾ ℓ. In order for ¯i to be in the sth column of A G , ¯i must be a; otherwise the column reverse inserted from T s would be [a, ¯i] T . This implies ¯i must bump an entry in the arm of T s-1 into its leg which would contradict ¯i ⩾ ℓ. In particular, this implies that a = ¯i ⩾ ℓ. Furthermore, the column obtained from T s when reverse inserting is of the form [ ¯i, b s ] T , where b s is the largest element in the arm of T s strictly less than the entry in the cell (2, 1). Since ¯i is the largest value in T s , the i + 1 in S s created by applying f i to T s is also the largest value. Thus, the column obtained from S s when reverse inserting is of the form [i + 1, c s ] T , where c s is the largest element in the arm of S s strictly less than the entry in the cell (2,1). Since f i (T s ) = S s , we have b s = c s and T s-1 = S s-1 . Thus, columns 1 through s -1 of A G are identical to the corresponding columns of A ′ G . As ¯i is the rightmost i in A G and is in the top row, it is also the rightmost unpaired i in A G . Thus, fi acts by changing ¯i to an
Assume now that ℓ > a and ℓ ̸ = i + 1. In order for ¯i to be in the sth column of A G , ¯i must be equal to a. When reversing the Burge correspondence of T s , the column obtained is then of the form [ℓ, ¯i] T . From our assumption, we also have ℓ > i + 1 which implies that the column obtained from S s when reversing the Burge correspondence is [ℓ, i + 1] T . Observe that T s-1 = S s-1 which forces columns 1 through s-1 of A G and A ′ G to be equal. We prove that ¯i is the rightmost unpaired i in A G . For there to be a hope that this claim is not true, then there must exist either a column
Note that there can only be one column with an i + 1 in the top row; otherwise it would form a valley with columns [i + 1, b j ] T and [ℓ, ¯i] T . If there exists a column of the form [i + 1, b j ] T , then in order for ¯i to be unpaired in T s there must be an i in a column j + 1 through s -1 or a column of the form [i, b j ′ ] T . Note that if there is an i in columns j +1 through s -1 this would imply ¯i is the rightmost unpaired i of A G . If there is no i in columns j + 1 through s -1, we must then have that column j -1 is of the form
¯i ] is a valley implying b j-1 ⩽ b j . Thus, if there exists a column of the form [i + 1, b j ] T with no i's in columns j through s -1, then ¯i must be the rightmost unpaired i. If there exists a column of the form [a j , i + 1] T with no i's in columns j through s -1, this would imply ¯i when inserted would bump an element from the arm of T s contradicting that ℓ is in the leg of T s . Thus, if there exists a column of the form [a j , i + 1] T , then there exists an i in columns j through s -1. Therefore, ¯i is the rightmost unpaired i of A G and fi acts by changing ¯i to an i + 1 in the sth column. This is precisely
Assume that ℓ > a and ℓ = i+1. In order for ¯i to be in column s of A G , a must be precisely ¯i. When reversing the Burge correspondence of T s , the column obtained is then of the form [ℓ = i + 1, ¯i] T . Since ℓ = i + 1 came from the leg of T s , there must exist an i somewhere in columns 1 through s -1; otherwise ¯i would not be the rightmost unpaired i in T s . Thus, ¯i is also the rightmost unpaired i of A G . Let x be the value in the (2, 1) position of T s and let y be the rightmost element in the arm of T s that is strictly less than x. Note that x < i + 1 = ℓ; otherwise T s would have shape (1, 1) and R i (T s ) = i + 1 i. This implies y ̸ = i. We also have y is not an element in the top row of A G . Otherwise if a m = y for some m, then x > y ⩾ a 1 which contradicts x being in the (2, 1) cell. Thus, y = b m for some 1 ⩽ m ⩽ s -1.
Assume now that x is a recording letter. As x lies in the (2, 1) cell of T s , we must have
Recall that in S s , b s = ¯i is replaced with an i + 1. Hence, when reverse inserting a column from S s , the i + 1 that replaced ¯i is removed, y = b m is replaced by x = a 1 , and the rest of the entries in the leg are shifted up. Thus
which mimics the action of fi on A G as
Assume now that x lies in the bottom row of A G . This implies that there exists b n that bumped
] and S n-1 is equal to T n-1 as x is in its original cell. These changes to A G are seen to be the same as fi as n is the leftmost column index such that b n ⩽ • • • ⩽ b s-1 and n is the rightmost column index between n and s -1 such that b n < a n . Assume that ¯i < ℓ ⩽ a and the (2, 1) cell of T s is not an i + 1. Let x be the value in the (2, 1) position of T s and let y be the rightmost element in the arm of T s that is strictly less than x. Note that for ¯i to be in the sth column of A G , y must equal ¯i. As x is not equal to i + 1, we have also i + 1 < x. When reversing the Burge correspondence of T s and S s the columns obtained are [a, ¯i] T and [a, i + 1] T respectively where the i + 1 reverse bumped from S s was the i + 1 created by f i . We have T s-1 and S s-1 are equal implying columns 1 through s -1 of A G and A ′ G are the same. Note that there cannot be an i + 1 in columns 1 through s -1. Otherwise there would either be an i + 1 in the leg of T s-1 which would contradict x > i + 1 or i + 1 is in the arm of T s-1 in which case ¯i would bump an i + 1 instead of x. Thus, ¯i is the rightmost unpaired i of A G and fi changes ¯i to an i + 1.
Assume that ¯i < ℓ ⩽ a and the (2, 1) cell of T s is an i + 1. Let x = i + 1 be the value in the (2, 1) cell of T s and y be the rightmost element in the arm of T s that is strictly less than x. For ¯i to be in the sth column of A G , y must equal ¯i. As column s in A G is of the form [a, ¯i] T , ¯i bumps i + 1 from the arm of T s-1 . Since x is bumped into the cell (2, 1), we have x = b n for some n. Observe that no i can be strictly between columns n through s in A G ; otherwise T s-1 would contain an i + 1 in its leg. From this observation and the fact that ¯i is the rightmost unpaired i in T G , there must exist an i somewhere in columns 1 through n -1 in A G .
Let m be the column of the index of the second rightmost i in A G which by the reasoning above satisfies m < n. We claim that i must be the insertion letter in column m, i.e. b m = i. If a m = i, then b m must have bumped an element in T m-1 when inserted; otherwise an i would be present in the leg of T s-1 . Let b z be the element bumped by b m . This implies b z is in the leg of T m-1 ; however, b z < a z ⩽ a m = i < i + 1 which would be a contradiction. Thus our claim that b m = i holds. We also have a m ̸ = i + 1 as Ri (A G ) can have at most one i-pair by Lemma 4.9. From these two facts, would be a valley. As y = ¯i is turned into an i + 1 in S s , the rightmost element in the arm of S s that is strictly less than x = i + 1 is b m . Thus, the column reverse inserted from S s is [a, b m = i] T while the column reverse inserted from T s is [a, ¯i] T . This implies the sth columns of A G and A ′ G are the same, but S s-1 differs from T s-1 . Note that columns m + 1 through s -1 of both A G and A ′ G are the same as the reverse insertions of T s and S s in these steps do not involve b m or the i + 1 created by f i respectively. As b m did not bump an element when inserted into T m-1 , we have a m is in the leg of both T m and S m and is the largest entry. We see [a m , b m ] T is reverse inserted from T m and [a m , i + 1] T is reverse inserted from S m and S s-1 = T s-1 . Thus, the only difference between A G and A ′ G is that b m is changed to an i + 1 in A G . Note that b m is the rightmost unpaired i in A G since it is the second rightmost i and ¯i is i-paired with the b n . Thus, fi acts by changing b m in A G to an i + 1 which is precisely A ′ G . □ For a crystal C , an element b ∈ C is called extremal if either f i (b) = 0 or e i (b) = 0 for each i in the index set and its weight is in the Weyl orbit of the highest weight element in the crystal component (see [20]). Let the weight of the highest weight vector u ∈ C (which satisfies e i (u) = 0 for all i) be wt(u) = λ. The weight of the extremal vectors are permutations of λ. The tableaux under the Burge correspondence are threshold shapes. Hence, by the definition of threshold graphs, the extremal vectors of the crystal correspond to threshold graphs under the Burge correspondence.