Growth diagrams and dual graded graphs¶
AUTHORS:
 Martin Rubey (201609): Initial version
Todo
 when shape is given, check that it is compatible with filling or labels
 implement backward rules for
GrowthDiagramDomino
andGrowthDiagramSylvester
 optimise rules, mainly for
GrowthDiagramRSK
andGrowthDiagramBurge
 make semistandard extension generic
Growth diagrams, invented by Sergey Fomin [Fom1995], provide a vast generalisation of the RobinsonSchenstedKnuth correspondence between matrices with nonnegative integer entries and pairs of semistandard Young tableaux of the same shape.
The main fact is that many correspondences similar to RSK can be defined by providing a socalled ‘forward’ rule: a function whose input are three vertices x, y and t of a certain directed graph (in the case of RobinsonSchensted: the directed graph corresponding to Young’s lattice) and an integer (in the case of RobinsonSchensted: zero or one), and whose output is a fourth vertex z. This rule should be invertible in the following sense: there is a socalled ‘backward’ rule that recovers the integer and t given z, x and y.
The classical RobinsonSchenstedKnuth correspondence is provided by
GrowthDiagramRSK
. Note that a growth diagram is printed
with matrix coordinates, the origin being in the topleft corner:
sage: w = [2,3,6,1,4,5]; G = GrowthDiagramRSK(w); G
0 0 0 1 0 0
1 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 1 0 0 0
The ‘forward’ rule just mentioned assigns partitions to the corners
of each of the 36 cells of this matrix  with the exception of the
corners on the left and top boundary, which are initialized with the
empty partition. The partitions along the boundary opposite of the
origin are obtained by using the method
GrowthDiagramRSK.out_labels()
:
sage: G.out_labels()
[[],
[1],
[2],
[3],
[3, 1],
[3, 2],
[4, 2],
[4, 1],
[3, 1],
[2, 1],
[1, 1],
[1],
[]]
However, in the case of a rectangular filling, it is more practical to split this sequence of labels in two. We then obtain the \(P\) and \(Q\) symbols:
sage: [G.P_symbol(), G.Q_symbol()]
[[[1, 3, 4, 5], [2, 6]], [[1, 2, 3, 6], [4, 5]]]
sage: RSK(w)
[[[1, 3, 4, 5], [2, 6]], [[1, 2, 3, 6], [4, 5]]]
A great advantage of growth diagrams is that we immediately have access also to the skew version of the RSKcorrespondence, by providing different initialisation for the labels near the origin. We reproduce the original example of Bruce Sagan and Richard Stanley, see also Tom Roby’s thesis [Rob1991]. We can represent the generalised permutation:
1 2 4
4 2 3
as a dictionary of coordinates, subtracting \(1\) from all entries because lists in SageMath are zerobased:
sage: w = {(11,41):1, (21,21):1, (41,31):1}
sage: T = SkewTableau([[None, None],[None,5],[1]])
sage: U = SkewTableau([[None, None],[None,3],[5]])
sage: G = GrowthDiagramRSK(filling = w, shape = [5]*5, labels = T.to_chain()[::1]+U.to_chain()[1:]); G
0 0 0 0 0
0 1 0 0 0
0 0 0 1 0
1 0 0 0 0
0 0 0 0 0
sage: G.P_symbol(), G.Q_symbol()
([[None, None, 2, 3], [None, None], [None, 4], [1], [5]],
[[None, None, 1, 4], [None, None], [None, 2], [3], [5]])
Moreover, we are not forced to use rectangular fillings. For example, consider the StanleySundaram correspondence between (skew) oscillating tableaux and (partial) perfect matchings. Again, from Tom Roby’s thesis:
sage: o = [[2,1],[2,2],[3,2],[4,2],[4,1],[4,1,1],[3,1,1],[3,1],[3,2],[3,1],[2,1]]
sage: l = [None]*(2*len(o)1)
sage: l[::2] = [Partition(la) for la in o]
sage: l[1::2] = [l[2*i] if l[2*i].size() < l[2*i+2].size() else l[2*i+2] for i in range(len(o)1)]
sage: G = GrowthDiagramRSK(labels=l[1:1], shape=[i for i in range(len(o)2,0,1)]); G
0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0
0 0 0 0
0 0 0
0 0
0
sage: ascii_art(SkewTableau(chain=G.in_labels()[len(o)2:]), SkewTableau(chain=G.in_labels()[:len(o)1][::1]))
. 1 . 7
5 4
As mentioned at the beginning, the RobinsonSchenstedKnuth
correspondence is just a special case of growth diagrams. In
particular, we have implemented local rules for the variation of RSK
originally due to Burge (GrowthDiagramBurge
), a
correspondence producing binary words originally due to Viennot
(GrowthDiagramBinWord
), and a correspondence producing
domino tableaux (GrowthDiagramDomino
) originally due to
Barbasch and Vogan.
REFERENCES:
[Fom1995]  (1, 2, 3, 4, 5) Sergey V. Fomin. Schensted algorithms for dual graded graphs. Journal of Algebraic Combinatorics Volume 4, Number 1 (1995), pp. 545 
[Rob1991]  Tom Roby. Applications and extensions of Fomin’s generalization of the RobinsonSchensted correspondence to differential posets. M.I.T., Cambridge, Massachusetts 
[Kra2006]  (1, 2, 3, 4) Christian Krattenthaler. Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes. Advances in Applied Mathematics Volume 37, Number 3 (2006), pp. 404431 
[Lam2004]  (1, 2) Thomas Lam. Growth diagrams, domino insertion and signimbalance. Journal of Combinatorial Theory, Series A Volume 107, Number 1 (2004), pp. 87115 
[LamShi2007]  Thomas Lam and Mark Shimozono. Dual graded graphs for KacMoody algebras. Algebra & Number Theory 1.4 (2007): pp. 451488 
[HivNze]  Florent Hivert and Janvier Nzeutchap. Dual Graded Graphs in Combinatorial Hopf Algebras. https://www.lri.fr/~hivert/PAPER/commCombHopfAlg.pdf 
[Vie1983]  (1, 2) Xavier G. Viennot. Maximal chains of subwords and updown sequences of permutations. Journal of Combinatorial Theory, Series A Volume 34, (1983), pp. 114 
[Nze2007]  (1, 2) Janvier Nzeutchap. Binary Search Tree insertion, the Hypoplactic insertion, and Dual Graded Graphs. Arxiv 0705.2689 (2007) 

class
sage.combinat.growth.
GrowthDiagram
(filling=None, shape=None, labels=None)¶ Bases:
sage.structure.sage_object.SageObject
The base class all variants of growth diagrams inherit from.
Inheriting classes should provide an
__init__
method that checks thatlabels
, when provided, are of the correct type, and sets the following attributes:self._zero
, the zero element of the vertices of the graphs,self._rank_function
, the rank function of the dual graded graphs,self._covers_1
,self._covers_2
, functions taking two vertices as arguments and return True if the first covers the second in the respective graded graph.
It should then call the
__init__
method of this class.EXAMPLES:
sage: w = [3,3,2,4,1]; G = GrowthDiagramRSK(w) sage: [G.P_symbol(), G.Q_symbol()] [[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]] sage: RSK(w) [[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]

P_chain
()¶ Return the labels along the vertical boundary of a rectangular growth diagram.
EXAMPLES:
sage: G = GrowthDiagramBinWord([4, 1, 2, 3]) sage: G.P_chain() [word: , word: 1, word: 11, word: 111, word: 1011]

Q_chain
()¶ Return the labels along the horizontal boundary of a rectangular growth diagram.
EXAMPLES:
sage: G = GrowthDiagramBinWord([[0,1,0,0], [0,0,1,0], [0,0,0,1], [1,0,0,0]]) sage: G.Q_chain() [word: , word: 1, word: 10, word: 101, word: 1011]

conjugate
()¶ Return the conjugate growth diagram of
self
. This is the growth diagram with the filling reflected over the main diagonal.When the filling is a permutation, the conjugate filling corresponds to its inverse.
EXAMPLES:
sage: G = GrowthDiagramRSK([[0,1,0], [1,0,2]]) sage: Gc = G.conjugate() sage: (Gc.P_symbol(), Gc.Q_symbol()) == (G.Q_symbol(), G.P_symbol()) True

filling
()¶ Return the filling of the diagram as a dictionary.
EXAMPLES:
sage: G = GrowthDiagramRSK([[0,1,0], [1,0,2]]) sage: G.filling() {(0, 1): 1, (1, 0): 1, (2, 1): 2}

in_labels
()¶ Return the labels along the boundary on the side of the origin.
EXAMPLES:
sage: G = GrowthDiagramRSK(labels=[[2,2],[3,2],[3,3],[3,2]]); G 1 0 sage: G.in_labels() [[2, 2], [2, 2], [2, 2], [3, 2]]

is_rectangular
()¶ Return
True
if the shape of the growth diagram is rectangular.EXAMPLES:
sage: GrowthDiagramRSK([2,3,1]).is_rectangular() True sage: GrowthDiagramRSK([[1,0,1],[0,1]]).is_rectangular() False

out_labels
()¶ Return the labels along the boundary opposite of the origin.
EXAMPLES:
sage: G = GrowthDiagramRSK([[0,1,0], [1,0,2]]) sage: G.out_labels() [[], [1], [1, 1], [3, 1], [1], []]

rotate
()¶ Return the growth diagram with the filling rotated by 180 degrees.
For RSKgrowth diagrams and rectangular fillings, this corresponds to evacuation of the P and the Qsymbol.
EXAMPLES:
sage: G = GrowthDiagramRSK([[0,1,0], [1,0,2]]) sage: Gc = G.rotate() sage: ascii_art(Gc.P_symbol(), Gc.Q_symbol()) 1 1 1 1 1 2 2 3 sage: ascii_art(SemistandardTableau(Tableau(G.P_symbol())).evacuation(), SemistandardTableau(Tableau(G.Q_symbol())).evacuation()) 1 1 1 1 1 2 2 3

shape
()¶ Return the shape of the growth diagram as a skew partition.
Warning
In the literature the label on the corner opposite of the origin of a rectangular filling is often called the shape of the filling. This method returns the shape of the region instead.
EXAMPLES:
sage: GrowthDiagramRSK([1]).shape() [1] / []

to_biword
()¶ Return the filling as a biword, if the shape is rectangular.
EXAMPLES:
sage: P = Tableau([[1,2,2],[2]]); Q = Tableau([[1,3,3],[2]]) sage: bw = RSK_inverse(P, Q); bw [[1, 2, 3, 3], [2, 1, 2, 2]] sage: G = GrowthDiagramRSK(labels = Q.to_chain()[:1] + P.to_chain()[::1]); G 0 1 0 1 0 2 sage: P = SemistandardTableau([[1, 1, 2], [2]]) sage: Q = SemistandardTableau([[1, 2, 2], [2]]) sage: G = GrowthDiagramRSK(labels = Q.to_chain()[:1] + P.to_chain()[::1]); G 0 2 1 1 sage: G.to_biword() ([1, 2, 2, 2], [2, 1, 1, 2]) sage: RSK([1, 2, 2, 2], [2, 1, 1, 2]) [[[1, 1, 2], [2]], [[1, 2, 2], [2]]]

to_word
()¶ Return the filling as a word, if the shape is rectangular and there is at most one nonzero entry in each column, which must be 1.
EXAMPLES:
sage: w = [3,3,2,4,1]; G = GrowthDiagramRSK(w) sage: G 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 sage: G.to_word() [3, 3, 2, 4, 1]

class
sage.combinat.growth.
GrowthDiagramBinWord
(filling=None, shape=None, labels=None)¶ Bases:
sage.combinat.growth.GrowthDiagram
A class modelling a Schenstedlike correspondence for binary words.
EXAMPLES:
sage: pi = Permutation([4,1,8,3,6,5,2,7,9]); G = GrowthDiagramBinWord(pi); G 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 sage: G.out_labels()[9] word: 101010011
The Kleitman Greene invariant is the descent word:
sage: pi.descents(from_zero=False) [1, 3, 5, 6]

static
_forward_rule
(y, t, x, content)¶ Return the output shape given three shapes and the content.
See [Fom1995] Lemma 4.6.1, page 40.
INPUT:
y, t, x
– three binary words from a cell in a growth diagram, labelled as:t x y
content
– 0 or 1, the content of the cell.
OUTPUT:
The fourth binary word z according to Viennot’s bijection [Vie1983].

static
_backward_rule
(y, z, x)¶ Return the content and the input shape.
See [Fom1995] Lemma 4.6.1, page 40.
y, z, x
– three binary words from a cell in a growth diagram, labelled as:x y z
OUTPUT:
A pair
(t, content)
consisting of the shape of the fourth word and the content of the cell acording to Viennot’s bijection [Vie1983].

static

class
sage.combinat.growth.
GrowthDiagramBurge
(filling=None, shape=None, labels=None)¶ Bases:
sage.combinat.growth.GrowthDiagramOnPartitions
A class modelling Burge insertion.
EXAMPLES:
sage: GrowthDiagramBurge(labels=[[],[1,1,1],[2,1,1,1],[2,1,1],[2,1],[1,1],[]]) 1 1 0 1 1 0 1 0

static
_forward_rule
(shape3, shape2, shape1, content)¶ Return the output shape given three shapes and the content.
See [Kra2006] \((F^4 0)(F^4 2)\).
INPUT:
shape3, shape2, shape1
– three from a cell in a growth diagram, labelled as:shape2 shape1 shape3
content
– a nonnegative integer, the content of the cell.
OUTPUT:
The fourth partition according to the Burge correspondence.

static
_backward_rule
(shape3, shape4, shape1)¶ Return the content and the input shape.
See [Kra2006] \((B^4 0)(B^4 2)\). There is a typo in the computation of carry in \((B^4 2)\) in the arXiv version of the article, \(\rho\) must be replaced by \(\lambda\).
INPUT:
shape3, shape4, shape1
– three partitions from a cell in a growth diagram, labelled as:shape1 mu shape3 shape4 nu lambda
OUTPUT:
A pair
(t, content)
consisting of the shape of the fourth partition acording to the Burge correspondence and the content of the cell.

static

class
sage.combinat.growth.
GrowthDiagramDomino
(filling=None, shape=None, labels=None)¶ Bases:
sage.combinat.growth.GrowthDiagramOnPartitions
A class modelling domino insertion.
EXAMPLES:
Figure 3 in [Lam2004]:
sage: G = GrowthDiagramDomino([[0,0,0,1],[0,0,1,0],[1,0,0,0],[0,1,0,0]]); G 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 sage: ascii_art(G.P_symbol(), G.Q_symbol()) 1 2 4 1 2 2 1 2 4 1 3 3 3 3 4 4

static
_forward_rule
(shape3, shape2, shape1, content)¶ Return the output shape given three shapes and the content.
See [Lam2004] Section 3.1.
INPUT:
shape3, shape2, shape1
– three partitions from a cell in a growth diagram, labelled as:shape2 shape1 shape3
content
– 1, 0 or 1, the content of the cell.
OUTPUT:
The fourth partition according to domino insertion.

static

class
sage.combinat.growth.
GrowthDiagramOnPartitions
(filling=None, shape=None, labels=None)¶ Bases:
sage.combinat.growth.GrowthDiagram
A class for growth diagrams on Young’s lattice on integer partitions graded by size. Since we do not use the covering relation, but only check partition containment, this class can also be used as a base class for growth diagrams modelling domino insertion,
GrowthDiagramDomino
.
P_symbol
()¶ Return the labels along the vertical boundary of a rectangular growth diagram as a skew tableau.
EXAMPLES:
sage: G = GrowthDiagramRSK([[0,1,0], [1,0,2]]) sage: G.P_symbol().pp() 1 2 2 2

Q_symbol
()¶ Return the labels along the horizontal boundary of a rectangular growth diagram as a skew tableau.
EXAMPLES:
sage: G = GrowthDiagramRSK([[0,1,0], [1,0,2]]) sage: G.Q_symbol().pp() 1 3 3 2


class
sage.combinat.growth.
GrowthDiagramRSK
(filling=None, shape=None, labels=None)¶ Bases:
sage.combinat.growth.GrowthDiagramOnPartitions
A class modelling RobinsonSchenstedKnuth insertion.
EXAMPLES:
sage: pi = Permutation([2,3,6,1,4,5]) sage: G = GrowthDiagramRSK(pi) sage: G.P_symbol(), G.Q_symbol() ([[1, 3, 4, 5], [2, 6]], [[1, 2, 3, 6], [4, 5]]) sage: RSK(pi) [[[1, 3, 4, 5], [2, 6]], [[1, 2, 3, 6], [4, 5]]]

static
_forward_rule
(shape3, shape2, shape1, content)¶ Return the output shape given three shapes and the content.
See [Kra2006] \((F^1 0)(F^1 2)\).
INPUT:
shape3, shape2, shape1
– three partitions from a cell in a growth diagram, labelled as:shape2 shape1 shape3
content
– a nonnegative integer, the content of the cell.
OUTPUT:
The fourth partition according to the RobinsonSchenstedKnuth correspondence.

static
_backward_rule
(shape3, shape4, shape1)¶ Return the content and the input shape.
See [Kra2006] \((B^1 0)(B^1 2)\).
INPUT:
shape3, shape4, shape1
– three partitions from a cell in a growth diagram, labelled as:shape1 shape3 shape4
OUTPUT:
A pair
(shape2, content)
consisting of the shape of the fourth word acording to the RobinsonSchenstedKnuth correspondence and the content of the cell.

static

class
sage.combinat.growth.
GrowthDiagramSylvester
(filling=None, shape=None, labels=None)¶ Bases:
sage.combinat.growth.GrowthDiagram
A class modelling a Schenstedlike correspondence for binary trees.
EXAMPLES:
From [Nze2007]:
sage: pi = Permutation([3,5,1,4,2,6]); G = GrowthDiagramSylvester(pi); G 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 sage: ascii_art(G.out_labels()[len(pi)]) __o__ / \ o o \ / \ o o o

class
sage.combinat.growth.
GrowthDiagramYoungFibonacci
(filling=None, shape=None, labels=None)¶ Bases:
sage.combinat.growth.GrowthDiagram
A class modelling a Schenstedlike correspondence for YoungFibonaccitableaux.
EXAMPLES:
sage: G = GrowthDiagramYoungFibonacci([4,1,8,3,6,5,2,7,9]); G 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 sage: G.out_labels()[9] word: 122121
The Kleitman Greene invariant is: take the last letter and the largest letter of the permutation and remove them. If they coincide write 1, otherwise write 2.

static
_forward_rule
(shape3, shape2, shape1, content)¶ Return the output shape given three shapes and the content.
See [Fom1995] Lemma 4.4.1, page 35.
INPUT:
shape3, shape2, shape1
– three Fibonacci words from a cell in a growth diagram, labelled as:shape2 shape1 shape3
content
– 0 or 1, the content of the cell.
OUTPUT:
The fourth Fibonacci word.

static