Growth diagrams and dual graded graphs

AUTHORS:

  • Martin Rubey (2016-09): Initial version

Todo

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 that labels, 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].

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.

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.

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.

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
static _forward_rule(x, t, y, content)

Return the output shape given three shapes and the content.

See [Nze2007], page 9.

INPUT:

  • y, t, x – three binary trees from a cell in a growth diagram, labelled as:

    t y
    x
    
  • content – 0 or 1, the content of the cell.

OUTPUT:

The fourth binary tree z.

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 _backward_rule(y, z, x)

Return the content and the input shape.

See [Fom1995] Lemma 4.4.1, page 35.

  • y, z, x – three Fibonacci 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.