Growth diagrams and dual graded graphs¶
AUTHORS:
- Martin Rubey (2016-09): 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 Robinson-Schensted-Knuth correspondence between matrices with non-negative 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 so-called ‘forward’ rule: a function whose input are three vertices x, y and t of a certain directed graph (in the case of Robinson-Schensted: the directed graph corresponding to Young’s lattice) and an integer (in the case of Robinson-Schensted: zero or one), and whose output is a fourth vertex z. This rule should be invertible in the following sense: there is a so-called ‘backward’ rule that recovers the integer and t given z, x and y.
The classical Robinson-Schensted-Knuth correspondence is provided by
GrowthDiagramRSK
. Note that a growth diagram is printed
with matrix coordinates, the origin being in the top-left 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 RSK-correspondence, 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 zero-based:
sage: w = {(1-1,4-1):1, (2-1,2-1):1, (4-1,3-1):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 Stanley-Sundaram 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 Robinson-Schensted-Knuth
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. 5-45 |
[Rob1991] | Tom Roby. Applications and extensions of Fomin’s generalization of the Robinson-Schensted 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. 404-431 |
[Lam2004] | (1, 2) Thomas Lam. Growth diagrams, domino insertion and sign-imbalance. Journal of Combinatorial Theory, Series A Volume 107, Number 1 (2004), pp. 87-115 |
[LamShi2007] | Thomas Lam and Mark Shimozono. Dual graded graphs for Kac-Moody algebras. Algebra & Number Theory 1.4 (2007): pp. 451-488 |
[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 up-down sequences of permutations. Journal of Combinatorial Theory, Series A Volume 34, (1983), pp. 1-14 |
[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 RSK-growth diagrams and rectangular fillings, this corresponds to evacuation of the P- and the Q-symbol.
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 Schensted-like 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 non-negative 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 Robinson-Schensted-Knuth 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 non-negative integer, the content of the cell.
OUTPUT:
The fourth partition according to the Robinson-Schensted-Knuth 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 Robinson-Schensted-Knuth 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 Schensted-like 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 Schensted-like correspondence for Young-Fibonacci-tableaux.
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