Growth diagrams and dual graded graphs

AUTHORS:

• Martin Rubey (2016-09): Initial version

• Martin Rubey (2017-09): generalize, more rules, improve documentation

• Travis Scrimshaw (2017-09): switch to rule-based framework

Todo

• provide examples for the P and Q-symbol in the skew case

• implement a method providing a visualization of the growth diagram with all labels, perhaps as LaTeX code

• when shape is given, check that it is compatible with filling or labels

• optimize rules, mainly for RuleRSK and RuleBurge

• implement backward rules for GrowthDiagram.rules.Domino

• implement backward rule from [LLMSSZ2013], [LS2007]

• make semistandard extension generic

• accommodate dual filtered graphs

A guided tour

Growth diagrams, invented by Sergey Fomin [Fom1994], [Fom1995], provide a vast generalization of the Robinson-Schensted-Knuth (RSK) 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 pair of so-called local rules: a ‘forward’ rule, whose input are three vertices \(y\), \(t\) and \(x\) 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: \(0\) or \(1\)), 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 \(y\), \(z\) and \(x\).

As an example, the growth rules for the classical RSK correspondence are provided by RuleRSK. To produce a growth diagram, pass the desired rule and a permutation to GrowthDiagram:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: w = [2,3,6,1,4,5]; G = GrowthDiagram(RuleRSK, 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

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> w = [Integer(2),Integer(3),Integer(6),Integer(1),Integer(4),Integer(5)]; G = GrowthDiagram(RuleRSK, 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 49 partitions to the corners of each of the 36 cells of this matrix (i.e., 49 the vertices of a \((6+1) \times (6+1)\) grid graph), with the exception of the corners on the left and top boundary, which are initialized with the empty partition. More precisely, for each cell, the forward_rule() computes the partition \(z\) labelling the lower right corner, given the content \(c\) of a cell and the other three partitions:

t --- x
|  c  |
y --- z

Warning

Note that a growth diagram is printed with matrix coordinates, the origin being in the top-left corner. Therefore, the growth is from the top left to the bottom right!

The partitions along the boundary opposite of the origin, reading from the bottom left to the top right, are obtained by using the method out_labels():

Sage

sage: G.out_labels()
[[],
 [1],
 [2],
 [3],
 [3, 1],
 [3, 2],
 [4, 2],
 [4, 1],
 [3, 1],
 [2, 1],
 [1, 1],
 [1],
 []]

Python

>>> from sage.all import *
>>> 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. Interpreting the sequence of partitions along the right boundary as a standard Young tableau, we then obtain the so-called P_symbol(), the partitions along the bottom boundary yield the so-called Q_symbol(). These coincide with the output of the classical RSK() insertion algorithm:

Sage

sage: ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  3  4  5    1  2  3  6 ]
[   2  6      ,   4  5       ]
sage: ascii_art(RSK(w))
[   1  3  4  5    1  2  3  6 ]
[   2  6      ,   4  5       ]

Python

>>> from sage.all import *
>>> ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  3  4  5    1  2  3  6 ]
[   2  6      ,   4  5       ]
>>> ascii_art(RSK(w))
[   1  3  4  5    1  2  3  6 ]
[   2  6      ,   4  5       ]

The filling can be recovered knowing the partitions labelling the corners of the bottom and the right boundary alone, by repeatedly applying the backward_rule(). Therefore, to initialize a GrowthDiagram, we can provide these labels instead of the filling:

Sage

sage: GrowthDiagram(RuleRSK, labels=G.out_labels())
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

Python

>>> from sage.all import *
>>> GrowthDiagram(RuleRSK, labels=G.out_labels())
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

Invocation

In general, growth diagrams are defined for \(0-1\)-fillings of arbitrary skew shapes. In the case of the Robinson-Schensted-Knuth correspondence, even arbitrary nonnegative integers are allowed. In other cases, entries may be either zero or an \(r\)-th root of unity - for example, RuleDomino insertion is defined for signed permutations, that is, \(r=2\). Traditionally, words and permutations are also used to specify a filling in special cases.

To accommodate all this, the filling may be passed in various ways. The most general possibility is to pass a dictionary of coordinates to (signed) entries, where zeros can be omitted. In this case, when the parameter shape is not explicitly specified, it is assumed to be the minimal rectangle containing the origin and all coordinates with nonzero entries.

For example, consider the following generalized permutation:

1 2 2 2 4 4
4 2 3 3 2 3

that we encode as the dictionary:

Sage

sage: P = {(1-1,4-1): 1, (2-1,2-1): 1, (2-1,3-1): 2, (4-1,2-1): 1, (4-1,3-1): 1}

Python

>>> from sage.all import *
>>> P = {(Integer(1)-Integer(1),Integer(4)-Integer(1)): Integer(1), (Integer(2)-Integer(1),Integer(2)-Integer(1)): Integer(1), (Integer(2)-Integer(1),Integer(3)-Integer(1)): Integer(2), (Integer(4)-Integer(1),Integer(2)-Integer(1)): Integer(1), (Integer(4)-Integer(1),Integer(3)-Integer(1)): Integer(1)}

Note that we are subtracting \(1\) from all entries because of zero-based indexing, we obtain:

Sage

sage: GrowthDiagram(RuleRSK, P)
0  0  0  0
0  1  0  1
0  2  0  1
1  0  0  0

Python

>>> from sage.all import *
>>> GrowthDiagram(RuleRSK, P)
0  0  0  0
0  1  0  1
0  2  0  1
1  0  0  0

Alternatively, we could create the same growth diagram using a matrix.

Let us also mention that one can pass the arguments specifying a growth diagram directly to the rule:

Sage

sage: RuleRSK(P)
0  0  0  0
0  1  0  1
0  2  0  1
1  0  0  0

Python

>>> from sage.all import *
>>> RuleRSK(P)
0  0  0  0
0  1  0  1
0  2  0  1
1  0  0  0

In contrast to the classical insertion algorithms, growth diagrams immediately generalize to fillings whose shape is an arbitrary skew partition:

Sage

sage: GrowthDiagram(RuleRSK, [3,1,2], shape=SkewPartition([[3,3,2],[1,1]]))
.  1  0
.  0  1
1  0

Python

>>> from sage.all import *
>>> GrowthDiagram(RuleRSK, [Integer(3),Integer(1),Integer(2)], shape=SkewPartition([[Integer(3),Integer(3),Integer(2)],[Integer(1),Integer(1)]]))
.  1  0
.  0  1
1  0

As an important example, consider the Stanley-Sundaram correspondence between oscillating tableaux and (partial) perfect matchings. Perfect matchings of \(\{1, \ldots, 2r\}\) are in bijection with \(0-1\)-fillings of a triangular shape with \(2r-1\) rows, such that for each \(k\) there is either exactly one nonzero entry in row \(k\) or exactly one nonzero entry in column \(2r-k\). Explicitly, if \((i,j)\) is a pair in the perfect matching, the entry in column \(i-1\) and row \(2r-j\) equals \(1\). For example:

Sage

sage: m = [[1,5],[3,4],[2,7],[6,8]]
sage: G = RuleRSK({(i-1, 8-j): 1 for i,j in m}, shape=[7,6,5,4,3,2,1]); G
0  0  0  0  0  1  0
0  1  0  0  0  0
0  0  0  0  0
1  0  0  0
0  0  1
0  0
0

Python

>>> from sage.all import *
>>> m = [[Integer(1),Integer(5)],[Integer(3),Integer(4)],[Integer(2),Integer(7)],[Integer(6),Integer(8)]]
>>> G = RuleRSK({(i-Integer(1), Integer(8)-j): Integer(1) for i,j in m}, shape=[Integer(7),Integer(6),Integer(5),Integer(4),Integer(3),Integer(2),Integer(1)]); G
0  0  0  0  0  1  0
0  1  0  0  0  0
0  0  0  0  0
1  0  0  0
0  0  1
0  0
0

The partitions labelling the bottom-right corners along the boundary opposite of the origin then form a so-called oscillating tableau - the remaining partitions along the bottom-right boundary are redundant:

Sage

sage: G.out_labels()[1::2]
[[1], [1, 1], [2, 1], [1, 1], [1], [1, 1], [1]]

Python

>>> from sage.all import *
>>> G.out_labels()[Integer(1)::Integer(2)]
[[1], [1, 1], [2, 1], [1, 1], [1], [1, 1], [1]]

Another great advantage of growth diagrams is that we immediately have access to a skew version of the correspondence, by providing different initialization for the labels on the side of the origin. We reproduce the original example of Bruce Sagan and Richard Stanley, see also Tom Roby’s thesis [Rob1991]:

Sage

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: labels = T.to_chain()[::-1] + U.to_chain()[1:]
sage: G = GrowthDiagram(RuleRSK, filling=w, shape=[5,5,5,5,5], labels=labels); 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: ascii_art([G.P_symbol(), G.Q_symbol()])
[   .  .  2  3    .  .  1  4 ]
[   .  .          .  .       ]
[   .  4          .  2       ]
[   1             3          ]
[   5         ,   5          ]

Python

>>> from sage.all import *
>>> w = {(Integer(1)-Integer(1),Integer(4)-Integer(1)): Integer(1), (Integer(2)-Integer(1),Integer(2)-Integer(1)): Integer(1), (Integer(4)-Integer(1),Integer(3)-Integer(1)): Integer(1)}
>>> T = SkewTableau([[None, None], [None, Integer(5)], [Integer(1)]])
>>> U = SkewTableau([[None, None], [None, Integer(3)], [Integer(5)]])
>>> labels = T.to_chain()[::-Integer(1)] + U.to_chain()[Integer(1):]
>>> G = GrowthDiagram(RuleRSK, filling=w, shape=[Integer(5),Integer(5),Integer(5),Integer(5),Integer(5)], labels=labels); 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
>>> ascii_art([G.P_symbol(), G.Q_symbol()])
[   .  .  2  3    .  .  1  4 ]
[   .  .          .  .       ]
[   .  4          .  2       ]
[   1             3          ]
[   5         ,   5          ]

Similarly, there is a correspondence for skew oscillating tableau. Let us conclude by reproducing Example 4.2.6 from [Rob1991]. The oscillating tableau, as given, is:

Sage

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]]

Python

>>> from sage.all import *
>>> o = [[Integer(2),Integer(1)],[Integer(2),Integer(2)],[Integer(3),Integer(2)],[Integer(4),Integer(2)],[Integer(4),Integer(1)],[Integer(4),Integer(1),Integer(1)],[Integer(3),Integer(1),Integer(1)],[Integer(3),Integer(1)],[Integer(3),Integer(2)],[Integer(3),Integer(1)],[Integer(2),Integer(1)]]

From this, we have to construct the list of labels of the corners along the bottom-right boundary. The labels with odd indices are given by the oscillating tableau, the other labels are obtained by taking the smaller of the two neighbouring partitions:

Sage

sage: l = [o[i//2] if is_even(i) else min(o[(i-1)//2],o[(i+1)//2])
....:      for i in range(2*len(o)-1)]
sage: la = list(range(len(o)-2, 0, -1))
sage: G = RuleRSK(labels=l[1:-1], shape=la); 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

Python

>>> from sage.all import *
>>> l = [o[i//Integer(2)] if is_even(i) else min(o[(i-Integer(1))//Integer(2)],o[(i+Integer(1))//Integer(2)])
...      for i in range(Integer(2)*len(o)-Integer(1))]
>>> la = list(range(len(o)-Integer(2), Integer(0), -Integer(1)))
>>> G = RuleRSK(labels=l[Integer(1):-Integer(1)], shape=la); 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

The skew tableaux can now be read off the partitions labelling the left and the top boundary. These can be accessed using the method in_labels():

Sage

sage: ascii_art(SkewTableau(chain=G.in_labels()[len(o)-2:]),
....:           SkewTableau(chain=G.in_labels()[len(o)-2::-1]))
.  1  .  7
5     4

Python

>>> from sage.all import *
>>> ascii_art(SkewTableau(chain=G.in_labels()[len(o)-Integer(2):]),
...           SkewTableau(chain=G.in_labels()[len(o)-Integer(2)::-Integer(1)]))
.  1  .  7
5     4

Rules currently available

As mentioned at the beginning, the Robinson-Schensted-Knuth correspondence is just a special case of growth diagrams. In particular, we have implemented the following local rules:

• RSK (RuleRSK).

• A variation of RSK originally due to Burge (RuleBurge).

• A correspondence producing binary words originally due to Viennot (RuleBinaryWord).

• A correspondence producing domino tableaux (RuleDomino) originally due to Barbasch and Vogan.

• A correspondence for shifted shapes (RuleShiftedShapes), where the original insertion algorithm is due to Sagan and Worley, and Haiman.

• The Sylvester correspondence, producing binary trees (RuleSylvester).

• The Young-Fibonacci correspondence (RuleYoungFibonacci).

• LLMS insertion (RuleLLMS).

Background

At the heart of Fomin’s framework is the notion of dual graded graphs. This is a pair of digraphs \(P, Q\) (multiple edges being allowed) on the same set of vertices \(V\), that satisfy the following conditions:

• the graphs are graded, that is, there is a function \(\rho : V \to \NN\), such that for any edge \((v, w)\) of \(P\) and also of \(Q\) we have \(\rho(w) = \rho(v) + 1\),

• there is a vertex \(0\) with rank zero, and

• there is a positive integer \(r\) such that \(DU = UD + rI\) on the free \(\ZZ\)-module \(\ZZ[V]\), where \(D\) is the down operator of \(Q\), assigning to each vertex the formal sum of its predecessors, \(U\) is the up operator of \(P\), assigning to each vertex the formal sum of its successors, and \(I\) is the identity operator.

Note that the condition \(DU = UD + rI\) is symmetric with respect to the interchange of the graphs \(P\) and \(Q\), because the up operator of a graph is the transpose of its down operator.

For example, taking for both \(P\) and \(Q\) to be Young’s lattice and \(r=1\), we obtain the dual graded graphs for classical Schensted insertion.

Given such a pair of graphs, there is a bijection between the \(r\)-colored permutations on \(k\) letters and pairs \((p, q)\), where \(p\) is a path in \(P\) from zero to a vertex of rank \(k\) and \(q\) is a path in \(Q\) from zero to the same vertex.

It turns out that - in principle - this bijection can always be described by so-called local forward and backward rules, see [Fom1995] for a detailed description. Knowing at least the forward rules, or the backward rules, you can implement your own growth diagram class.

Implementing your own growth diagrams

The class GrowthDiagram is written so that it is easy to implement growth diagrams you come across in your research. Moreover, the class tolerates some deviations from Fomin’s definitions. For example, although the general Robinson-Schensted-Knuth correspondence between integer matrices and semistandard tableaux is, strictly speaking, not a growth on dual graded graphs, it is supported by our framework.

For illustration, let us implement a growth diagram class with the backward rule only. Suppose that the vertices of the graph are the nonnegative integers, the rank is given by the integer itself, and the backward rule is \((y, z, x) \mapsto (\min(x,y), 0)\) if \(y = z\) or \(x = z\) and \((y, z, x) \mapsto (\min(x,y), 1)\) otherwise.

We first need to import the base class for a rule:

Sage

sage: from sage.combinat.growth import Rule

Python

>>> from sage.all import *
>>> from sage.combinat.growth import Rule

Next, we implement the backward rule and the rank function and provide the bottom element zero of the graph. For more information, see Rule.

Sage

sage: class RulePascal(Rule):
....:     zero = 0
....:     def rank(self, v): return v
....:     def backward_rule(self, y, z, x):
....:         return (min(x,y), 0 if y==z or x==z else 1)

Python

>>> from sage.all import *
>>> class RulePascal(Rule):
...     zero = Integer(0)
...     def rank(self, v): return v
...     def backward_rule(self, y, z, x):
...         return (min(x,y), Integer(0) if y==z or x==z else Integer(1))

We can now compute the filling corresponding to a sequence of labels as follows:

Sage

sage: GrowthDiagram(RulePascal(), labels=[0,1,2,1,2,1,0])
1  0  0
0  0  1
0  1

Python

>>> from sage.all import *
>>> GrowthDiagram(RulePascal(), labels=[Integer(0),Integer(1),Integer(2),Integer(1),Integer(2),Integer(1),Integer(0)])
1  0  0
0  0  1
0  1

Of course, since we have not provided the forward rule, we cannot compute the labels belonging to a filling:

Sage

sage: GrowthDiagram(RulePascal(), [3,1,2])
Traceback (most recent call last):
...
AttributeError: 'RulePascal' object has no attribute 'forward_rule'...

Python

>>> from sage.all import *
>>> GrowthDiagram(RulePascal(), [Integer(3),Integer(1),Integer(2)])
Traceback (most recent call last):
...
AttributeError: 'RulePascal' object has no attribute 'forward_rule'...

We now re-implement the rule where we provide the dual graded graphs:

Sage

sage: class RulePascal(Rule):
....:     zero = 0
....:     def rank(self, v): return v
....:     def backward_rule(self, y, z, x):
....:         return (min(x,y), 0 if y==z or x==z else 1)
....:     def vertices(self, n): return [n]
....:     def is_P_edge(self, v, w): return w == v + 1
....:     def is_Q_edge(self, v, w): return w == v + 1

Python

>>> from sage.all import *
>>> class RulePascal(Rule):
...     zero = Integer(0)
...     def rank(self, v): return v
...     def backward_rule(self, y, z, x):
...         return (min(x,y), Integer(0) if y==z or x==z else Integer(1))
...     def vertices(self, n): return [n]
...     def is_P_edge(self, v, w): return w == v + Integer(1)
...     def is_Q_edge(self, v, w): return w == v + Integer(1)

Are they really dual?

Sage

sage: RulePascal()._check_duality(3)
Traceback (most recent call last):
...
ValueError: D U - U D differs from 1 I for vertex 3:
D U = [3]
U D + 1 I = [3, 3]

Python

>>> from sage.all import *
>>> RulePascal()._check_duality(Integer(3))
Traceback (most recent call last):
...
ValueError: D U - U D differs from 1 I for vertex 3:
D U = [3]
U D + 1 I = [3, 3]

With our current definition, duality fails - in fact, there are no dual graded graphs on the integers without multiple edges. Consequently, also the backward rule cannot work as backward_rule requires additional information (the edge labels as arguments).

Let us thus continue with the example from Section 4.7 of [Fom1995] instead, which defines dual graded graphs with multiple edges on the integers. The color self.zero_edge, which defaults to 0 is reserved for degenerate edges, but may be abused for the unique edge if one of the graphs has no multiple edges. For greater clarity in this example we set it to None:

Sage

sage: class RulePascal(Rule):
....:     zero = 0
....:     has_multiple_edges = True
....:     zero_edge = None
....:     def rank(self, v): return v
....:     def vertices(self, n): return [n]
....:     def is_P_edge(self, v, w): return [0] if w == v + 1 else []
....:     def is_Q_edge(self, v, w): return list(range(w)) if w == v+1 else []

Python

>>> from sage.all import *
>>> class RulePascal(Rule):
...     zero = Integer(0)
...     has_multiple_edges = True
...     zero_edge = None
...     def rank(self, v): return v
...     def vertices(self, n): return [n]
...     def is_P_edge(self, v, w): return [Integer(0)] if w == v + Integer(1) else []
...     def is_Q_edge(self, v, w): return list(range(w)) if w == v+Integer(1) else []

We verify these are \(1\) dual at level \(5\):

Sage

sage: RulePascal()._check_duality(5)

Python

>>> from sage.all import *
>>> RulePascal()._check_duality(Integer(5))

Finally, let us provide the backward rule. The arguments of the rule are vertices together with the edge labels now, specifying the path from the lower left to the upper right of the cell. The horizontal edges come from \(Q\), whereas the vertical edges come from \(P\).

Thus, the definition in Section 4.7 of [Fom1995] translates as follows:

Sage

sage: class RulePascal(Rule):
....:     zero = 0
....:     has_multiple_edges = True
....:     zero_edge = None
....:     def rank(self, v): return v
....:     def vertices(self, n): return [n]
....:     def is_P_edge(self, v, w): return [0] if w == v + 1 else []
....:     def is_Q_edge(self, v, w): return list(range(w)) if w == v+1 else []
....:     def backward_rule(self, y, g, z, h, x):
....:         if g is None:
....:             return (0, x, None, 0)
....:         if h is None:
....:             return (None, y, g, 0)
....:         if g == 0:
....:             return (None, y, None, 1)
....:         else:
....:             return (0, x-1, g-1, 0)

Python

>>> from sage.all import *
>>> class RulePascal(Rule):
...     zero = Integer(0)
...     has_multiple_edges = True
...     zero_edge = None
...     def rank(self, v): return v
...     def vertices(self, n): return [n]
...     def is_P_edge(self, v, w): return [Integer(0)] if w == v + Integer(1) else []
...     def is_Q_edge(self, v, w): return list(range(w)) if w == v+Integer(1) else []
...     def backward_rule(self, y, g, z, h, x):
...         if g is None:
...             return (Integer(0), x, None, Integer(0))
...         if h is None:
...             return (None, y, g, Integer(0))
...         if g == Integer(0):
...             return (None, y, None, Integer(1))
...         else:
...             return (Integer(0), x-Integer(1), g-Integer(1), Integer(0))

The labels are now alternating between vertices and edge-colors:

Sage

sage: GrowthDiagram(RulePascal(), labels=[0,0,1,0,2,0,1,0,0])
1  0
0  1

sage: GrowthDiagram(RulePascal(), labels=[0,0,1,1,2,0,1,0,0])
0  1
1  0

Python

>>> from sage.all import *
>>> GrowthDiagram(RulePascal(), labels=[Integer(0),Integer(0),Integer(1),Integer(0),Integer(2),Integer(0),Integer(1),Integer(0),Integer(0)])
1  0
0  1

>>> GrowthDiagram(RulePascal(), labels=[Integer(0),Integer(0),Integer(1),Integer(1),Integer(2),Integer(0),Integer(1),Integer(0),Integer(0)])
0  1
1  0

class sage.combinat.growth.GrowthDiagram(rule, filling=None, shape=None, labels=None)

Bases: SageObject

A generalized Schensted growth diagram in the sense of Fomin.

Growth diagrams were introduced by Sergey Fomin [Fom1994], [Fom1995] and provide a vast generalization of the Robinson-Schensted-Knuth (RSK) correspondence between matrices with nonnegative integer entries and pairs of semistandard Young tableaux of the same shape.

A growth diagram is based on the notion of dual graded graphs, a pair of digraphs \(P, Q\) (multiple edges being allowed) on the same set of vertices \(V\), that satisfy the following conditions:

• the graphs are graded, that is, there is a function \(\rho: V \to \NN\), such that for any edge \((v, w)\) of \(P\) and also of \(Q\) we have \(\rho(w) = \rho(v) + 1\),

• there is a vertex \(0\) with rank zero, and

• there is a positive integer \(r\) such that \(DU = UD + rI\) on the free \(\ZZ\)-module \(\ZZ[V]\), where \(D\) is the down operator of \(Q\), assigning to each vertex the formal sum of its predecessors, \(U\) is the up operator of \(P\), assigning to each vertex the formal sum of its successors, and \(I\) is the identity operator.

Growth diagrams are defined by providing a pair of local rules: a ‘forward’ rule, whose input are three vertices \(y\), \(t\) and \(x\) of the dual graded graphs and an integer, 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 \(y\), \(z\) and \(x\).

All implemented growth diagram rules are available by GrowthDiagram.rules.<tab>. The current list is:

• RuleRSK – RSK

• RuleBurge – a variation of RSK originally due to Burge

• RuleBinaryWord – a correspondence producing binary words originally due to Viennot

• RuleDomino – a correspondence producing domino tableaux originally due to Barbasch and Vogan

• RuleShiftedShapes – a correspondence for shifted shapes, where the original insertion algorithm is due to Sagan and Worley, and Haiman.

• RuleSylvester – the Sylvester correspondence, producing binary trees

• RuleYoungFibonacci – the Young-Fibonacci correspondence

• RuleLLMS – LLMS insertion

INPUT:

• rule – Rule; the growth diagram rule

• filling – (optional) a dictionary whose keys are coordinates and values are integers, a list of lists of integers, or a word with integer values; if a word, then negative letters but without repetitions are allowed and interpreted as coloured permutations

• shape – (optional) a (possibly skew) partition

• labels – (optional) a list that specifies a path whose length in the half-perimeter of the shape; more details given below

If filling is not given, then the growth diagram is determined by applying the backward rule to labels decorating the boundary opposite of the origin of the shape. In this case, labels are interpreted as labelling the boundary opposite of the origin.

Otherwise, shape is inferred from filling or labels if possible and labels is set to rule.zero if not specified. Here, labels are labelling the boundary on the side of the origin.

For labels, if rule.has_multiple_edges is True, then the elements should be of the form \((v_1, e_1, \ldots, e_{n-1}, v_n)\), where \(n\) is the half-perimeter of shape, and \((v_{i-1}, e_i, v_i)\) is an edge in the dual graded graph for all \(i\). Otherwise, it is a list of \(n\) vertices.

Note

Coordinates are of the form (col, row) where the origin is in the upper left, to be consistent with permutation matrices and skew tableaux (in English convention). This is different from Fomin’s convention, who uses a Cartesian coordinate system.

Conventions are chosen such that for permutations, the same growth diagram is constructed when passing the permutation matrix instead.

EXAMPLES:

We create a growth diagram using the forward RSK rule and a permutation:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: pi = Permutation([4, 1, 2, 3])
sage: G = GrowthDiagram(RuleRSK, pi); G
0  1  0  0
0  0  1  0
0  0  0  1
1  0  0  0
sage: G.out_labels()
[[], [1], [1, 1], [2, 1], [3, 1], [3], [2], [1], []]

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> pi = Permutation([Integer(4), Integer(1), Integer(2), Integer(3)])
>>> G = GrowthDiagram(RuleRSK, pi); G
0  1  0  0
0  0  1  0
0  0  0  1
1  0  0  0
>>> G.out_labels()
[[], [1], [1, 1], [2, 1], [3, 1], [3], [2], [1], []]

Passing the permutation matrix instead gives the same result:

Sage

sage: G = GrowthDiagram(RuleRSK, pi.to_matrix())                                # needs sage.modules
sage: ascii_art([G.P_symbol(), G.Q_symbol()])                                   # needs sage.modules
[   1  2  3    1  3  4 ]
[   4      ,   2       ]

Python

>>> from sage.all import *
>>> G = GrowthDiagram(RuleRSK, pi.to_matrix())                                # needs sage.modules
>>> ascii_art([G.P_symbol(), G.Q_symbol()])                                   # needs sage.modules
[   1  2  3    1  3  4 ]
[   4      ,   2       ]

We give the same example but using a skew shape:

Sage

sage: shape = SkewPartition([[4,4,4,2],[1,1]])
sage: G = GrowthDiagram(RuleRSK, pi, shape=shape); G
.  1  0  0
.  0  1  0
0  0  0  1
1  0
sage: G.out_labels()
[[], [1], [1, 1], [1], [2], [3], [2], [1], []]

Python

>>> from sage.all import *
>>> shape = SkewPartition([[Integer(4),Integer(4),Integer(4),Integer(2)],[Integer(1),Integer(1)]])
>>> G = GrowthDiagram(RuleRSK, pi, shape=shape); G
.  1  0  0
.  0  1  0
0  0  0  1
1  0
>>> G.out_labels()
[[], [1], [1, 1], [1], [2], [3], [2], [1], []]

We construct a growth diagram using the backwards RSK rule by specifying the labels:

Sage

sage: GrowthDiagram(RuleRSK, labels=G.out_labels())
0  1  0  0
0  0  1  0
0  0  0  1
1  0

Python

>>> from sage.all import *
>>> GrowthDiagram(RuleRSK, labels=G.out_labels())
0  1  0  0
0  0  1  0
0  0  0  1
1  0

P_chain()

Return the labels along the vertical boundary of a rectangular growth diagram.

EXAMPLES:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()
sage: G = GrowthDiagram(BinaryWord, [4, 1, 2, 3])
sage: G.P_chain()
[word: , word: 1, word: 11, word: 111, word: 1011]

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()
>>> G = GrowthDiagram(BinaryWord, [Integer(4), Integer(1), Integer(2), Integer(3)])
>>> G.P_chain()
[word: , word: 1, word: 11, word: 111, word: 1011]

Check that Issue #25631 is fixed:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()
sage: BinaryWord(filling = {}).P_chain()
[word: ]

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()
>>> BinaryWord(filling = {}).P_chain()
[word: ]

P_symbol()

Return the labels along the vertical boundary of a rectangular growth diagram as a generalized standard tableau.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: G = GrowthDiagram(RuleRSK, [[0,1,0], [1,0,2]])
sage: ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  2  2    1  3  3 ]
[   2      ,   2       ]

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> G = GrowthDiagram(RuleRSK, [[Integer(0),Integer(1),Integer(0)], [Integer(1),Integer(0),Integer(2)]])
>>> ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  2  2    1  3  3 ]
[   2      ,   2       ]

Q_chain()

Return the labels along the horizontal boundary of a rectangular growth diagram.

EXAMPLES:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()
sage: G = GrowthDiagram(BinaryWord, [[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]

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()
>>> G = GrowthDiagram(BinaryWord, [[Integer(0),Integer(1),Integer(0),Integer(0)], [Integer(0),Integer(0),Integer(1),Integer(0)], [Integer(0),Integer(0),Integer(0),Integer(1)], [Integer(1),Integer(0),Integer(0),Integer(0)]])
>>> G.Q_chain()
[word: , word: 1, word: 10, word: 101, word: 1011]

Check that Issue #25631 is fixed:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()
sage: BinaryWord(filling = {}).Q_chain()
[word: ]

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()
>>> BinaryWord(filling = {}).Q_chain()
[word: ]

Q_symbol()

Return the labels along the horizontal boundary of a rectangular growth diagram as a generalized standard tableau.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: G = GrowthDiagram(RuleRSK, [[0,1,0], [1,0,2]])
sage: ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  2  2    1  3  3 ]
[   2      ,   2       ]

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> G = GrowthDiagram(RuleRSK, [[Integer(0),Integer(1),Integer(0)], [Integer(1),Integer(0),Integer(2)]])
>>> ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  2  2    1  3  3 ]
[   2      ,   2       ]

conjugate()

Return the conjugate growth diagram of self.

This is the growth diagram with the filling reflected over the main diagonal.

The sequence of labels along the boundary on the side of the origin is the reversal of the corresponding sequence of the original growth diagram.

When the filling is a permutation, the conjugate filling corresponds to its inverse.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: G = GrowthDiagram(RuleRSK, [[0,1,0], [1,0,2]])
sage: Gc = G.conjugate()
sage: (Gc.P_symbol(), Gc.Q_symbol()) == (G.Q_symbol(), G.P_symbol())
True

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> G = GrowthDiagram(RuleRSK, [[Integer(0),Integer(1),Integer(0)], [Integer(1),Integer(0),Integer(2)]])
>>> Gc = G.conjugate()
>>> (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

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: G = GrowthDiagram(RuleRSK, [[0,1,0], [1,0,2]])
sage: G.filling()
{(0, 1): 1, (1, 0): 1, (2, 1): 2}

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> G = GrowthDiagram(RuleRSK, [[Integer(0),Integer(1),Integer(0)], [Integer(1),Integer(0),Integer(2)]])
>>> G.filling()
{(0, 1): 1, (1, 0): 1, (2, 1): 2}

half_perimeter()

Return half the perimeter of the shape of the growth diagram.

in_labels()

Return the labels along the boundary on the side of the origin.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: G = GrowthDiagram(RuleRSK, labels=[[2,2],[3,2],[3,3],[3,2]]); G
1 0
sage: G.in_labels()
[[2, 2], [2, 2], [2, 2], [3, 2]]

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> G = GrowthDiagram(RuleRSK, labels=[[Integer(2),Integer(2)],[Integer(3),Integer(2)],[Integer(3),Integer(3)],[Integer(3),Integer(2)]]); G
1 0
>>> 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

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: GrowthDiagram(RuleRSK, [2,3,1]).is_rectangular()
True
sage: GrowthDiagram(RuleRSK, [[1,0,1],[0,1]]).is_rectangular()
False

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> GrowthDiagram(RuleRSK, [Integer(2),Integer(3),Integer(1)]).is_rectangular()
True
>>> GrowthDiagram(RuleRSK, [[Integer(1),Integer(0),Integer(1)],[Integer(0),Integer(1)]]).is_rectangular()
False

out_labels()

Return the labels along the boundary opposite of the origin.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: G = GrowthDiagram(RuleRSK, [[0,1,0], [1,0,2]])
sage: G.out_labels()
[[], [1], [1, 1], [3, 1], [1], []]

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> G = GrowthDiagram(RuleRSK, [[Integer(0),Integer(1),Integer(0)], [Integer(1),Integer(0),Integer(2)]])
>>> G.out_labels()
[[], [1], [1, 1], [3, 1], [1], []]

rotate()

Return the growth diagram with the filling rotated by 180 degrees.

The rotated growth diagram is initialized with labels=None, that is, all labels along the boundary on the side of the origin are set to rule.zero.

For RSK-growth diagrams and rectangular fillings, this corresponds to evacuation of the \(P\)- and the \(Q\)-symbol.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: G = GrowthDiagram(RuleRSK, [[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([Tableau(t).evacuation()
....:            for t in [G.P_symbol(), G.Q_symbol()]])
[   1  1  1    1  1  2 ]
[   2      ,   3       ]

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> G = GrowthDiagram(RuleRSK, [[Integer(0),Integer(1),Integer(0)], [Integer(1),Integer(0),Integer(2)]])
>>> Gc = G.rotate()
>>> ascii_art([Gc.P_symbol(), Gc.Q_symbol()])
[   1  1  1    1  1  2 ]
[   2      ,   3       ]

>>> ascii_art([Tableau(t).evacuation()
...            for t in [G.P_symbol(), G.Q_symbol()]])
[   1  1  1    1  1  2 ]
[   2      ,   3       ]

rules

alias of Rules

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

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: GrowthDiagram(RuleRSK, [1]).shape()
[1] / []

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> GrowthDiagram(RuleRSK, [Integer(1)]).shape()
[1] / []

to_biword()

Return the filling as a biword, if the shape is rectangular.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: P = Tableau([[1,2,2],[2]])
sage: Q = Tableau([[1,3,3],[2]])
sage: bw = RSK_inverse(P, Q); bw
[[1, 2, 3, 3], [2, 1, 2, 2]]
sage: G = GrowthDiagram(RuleRSK, 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 = GrowthDiagram(RuleRSK, 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]]]

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> P = Tableau([[Integer(1),Integer(2),Integer(2)],[Integer(2)]])
>>> Q = Tableau([[Integer(1),Integer(3),Integer(3)],[Integer(2)]])
>>> bw = RSK_inverse(P, Q); bw
[[1, 2, 3, 3], [2, 1, 2, 2]]
>>> G = GrowthDiagram(RuleRSK, labels=Q.to_chain()[:-Integer(1)]+P.to_chain()[::-Integer(1)]); G
0  1  0
1  0  2

>>> P = SemistandardTableau([[Integer(1), Integer(1), Integer(2)], [Integer(2)]])
>>> Q = SemistandardTableau([[Integer(1), Integer(2), Integer(2)], [Integer(2)]])
>>> G = GrowthDiagram(RuleRSK, labels=Q.to_chain()[:-Integer(1)]+P.to_chain()[::-Integer(1)]); G
0  2
1  1
>>> G.to_biword()
([1, 2, 2, 2], [2, 1, 1, 2])
>>> RSK([Integer(1), Integer(2), Integer(2), Integer(2)], [Integer(2), Integer(1), Integer(1), Integer(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

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: w = [3,3,2,4,1]; G = GrowthDiagram(RuleRSK, 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]

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> w = [Integer(3),Integer(3),Integer(2),Integer(4),Integer(1)]; G = GrowthDiagram(RuleRSK, w)
>>> G
0  0  0  0  1
0  0  1  0  0
1  1  0  0  0
0  0  0  1  0
>>> G.to_word()
[3, 3, 2, 4, 1]

class sage.combinat.growth.Rule

Bases: UniqueRepresentation

Generic base class for a rule for a growth diagram.

Subclasses may provide the following attributes:

• zero – the zero element of the vertices of the graphs

• r – (default: 1) the parameter in the equation \(DU - UD = rI\)

• has_multiple_edges – boolean (default: False); if the dual graded graph has multiple edges and therefore edges are triples consisting of two vertices and a label

• zero_edge – (default: 0) the zero label of the edges of the graphs used for degenerate edges. It is allowed to use this label also for other edges.

Subclasses may provide the following methods:

• normalize_vertex – a function that converts its input to a vertex

• vertices – a function that takes a nonnegative integer as input and returns the list of vertices on this rank

• rank – the rank function of the dual graded graphs

• forward_rule – a function with input (y, t, x, content) or (y, e, t, f, x, content) if has_multiple_edges is True. (y, e, t) is an edge in the graph \(P\), (t, f, x) an edge in the graph Q. It should return the fourth vertex z, or, if has_multiple_edges is True, the path (g, z, h) from y to x.

• backward_rule – a function with input (y, z, x) or (y, g, z, h, x) if has_multiple_edges is True. (y, g, z) is an edge in the graph \(Q\), (z, h, x) an edge in the graph P. It should return the fourth vertex and the content (t, content), or, if has_multiple_edges is True, the path from y to x and the content as (e, t, f, content).

• is_P_edge, is_Q_edge – functions that take two vertices as arguments and return True or False, or, if multiple edges are allowed, the list of edge labels of the edges from the first vertex to the second in the respective graded graph. These are only used for checking user input and providing the dual graded graph, and are therefore not mandatory.

Note that the class GrowthDiagram is able to use partially implemented subclasses just fine. Suppose that MyRule is such a subclass. Then:

• GrowthDiagram(MyRule, my_filling) requires only an implementation of forward_rule, zero and possibly has_multiple_edges.

• GrowthDiagram(MyRule, labels=my_labels, shape=my_shape) requires only an implementation of backward_rule and possibly has_multiple_edges, provided that the labels my_labels are given as needed by backward_rule.

• GrowthDiagram(MyRule, labels=my_labels) additionally needs an implementation of rank to deduce the shape.

In particular, this allows to implement rules which do not quite fit Fomin’s notion of dual graded graphs. An example would be Bloom and Saracino’s variant of the RSK correspondence [BS2012], where a backward rule is not available.

Similarly:

• MyRule.P_graph only requires an implementation of vertices, is_P_edge and possibly has_multiple_edges is required, mutatis mutandis for MyRule.Q_graph.

• MyRule._check_duality requires P_graph and Q_graph.

In particular, this allows to work with dual graded graphs without local rules.

P_graph(n)

Return the first n levels of the first dual graded graph.

The non-degenerate edges in the vertical direction come from this graph.

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()
sage: Domino.P_graph(3)
Finite poset containing 8 elements

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()
>>> Domino.P_graph(Integer(3))
Finite poset containing 8 elements

Q_graph(n)

Return the first n levels of the second dual graded graph.

The non-degenerate edges in the horizontal direction come from this graph.

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()
sage: Q = Domino.Q_graph(3); Q
Finite poset containing 8 elements

sage: Q.upper_covers(Partition([1,1]))
[[1, 1, 1, 1], [3, 1], [2, 2]]

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()
>>> Q = Domino.Q_graph(Integer(3)); Q
Finite poset containing 8 elements

>>> Q.upper_covers(Partition([Integer(1),Integer(1)]))
[[1, 1, 1, 1], [3, 1], [2, 2]]

has_multiple_edges = False

normalize_vertex(v)

Return v as a vertex of the dual graded graph.

This is a default implementation, returning its argument.

EXAMPLES:

Sage

sage: from sage.combinat.growth import Rule
sage: Rule().normalize_vertex("hello") == "hello"
True

Python

>>> from sage.all import *
>>> from sage.combinat.growth import Rule
>>> Rule().normalize_vertex("hello") == "hello"
True

r = 1

zero_edge = 0

class sage.combinat.growth.RuleBinaryWord

Bases: Rule

A rule modelling a Schensted-like correspondence for binary words.

EXAMPLES:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()
sage: GrowthDiagram(BinaryWord, [3,1,2])
0  1  0
0  0  1
1  0  0

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()
>>> GrowthDiagram(BinaryWord, [Integer(3),Integer(1),Integer(2)])
0  1  0
0  0  1
1  0  0

The vertices of the dual graded graph are binary words:

Sage

sage: BinaryWord.vertices(3)
[word: 100, word: 101, word: 110, word: 111]

Python

>>> from sage.all import *
>>> BinaryWord.vertices(Integer(3))
[word: 100, word: 101, word: 110, word: 111]

Note that, instead of passing the rule to GrowthDiagram, we can also use call the rule to create growth diagrams. For example:

Sage

sage: BinaryWord([2,4,1,3]).P_chain()
[word: , word: 1, word: 10, word: 101, word: 1101]
sage: BinaryWord([2,4,1,3]).Q_chain()
[word: , word: 1, word: 11, word: 110, word: 1101]

Python

>>> from sage.all import *
>>> BinaryWord([Integer(2),Integer(4),Integer(1),Integer(3)]).P_chain()
[word: , word: 1, word: 10, word: 101, word: 1101]
>>> BinaryWord([Integer(2),Integer(4),Integer(1),Integer(3)]).Q_chain()
[word: , word: 1, word: 11, word: 110, word: 1101]

The Kleitman Greene invariant is the descent word, encoded by the positions of the zeros:

Sage

sage: pi = Permutation([4,1,8,3,6,5,2,7,9])
sage: G = BinaryWord(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: pi.descents()
[1, 3, 5, 6]

Python

>>> from sage.all import *
>>> pi = Permutation([Integer(4),Integer(1),Integer(8),Integer(3),Integer(6),Integer(5),Integer(2),Integer(7),Integer(9)])
>>> G = BinaryWord(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
>>> pi.descents()
[1, 3, 5, 6]

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 according to Viennot’s bijection [Vie1983].

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].

EXAMPLES:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()

sage: BinaryWord.forward_rule([], [], [], 1)
word: 1

sage: BinaryWord.forward_rule([1], [1], [1], 1)
word: 11

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()

>>> BinaryWord.forward_rule([], [], [], Integer(1))
word: 1

>>> BinaryWord.forward_rule([Integer(1)], [Integer(1)], [Integer(1)], Integer(1))
word: 11

if x != y append last letter of x to y:

Sage

sage: BinaryWord.forward_rule([1,0], [1], [1,1], 0)
word: 101

Python

>>> from sage.all import *
>>> BinaryWord.forward_rule([Integer(1),Integer(0)], [Integer(1)], [Integer(1),Integer(1)], Integer(0))
word: 101

if x == y != t append 0 to y:

Sage

sage: BinaryWord.forward_rule([1,1], [1], [1,1], 0)
word: 110

Python

>>> from sage.all import *
>>> BinaryWord.forward_rule([Integer(1),Integer(1)], [Integer(1)], [Integer(1),Integer(1)], Integer(0))
word: 110

is_P_edge(v, w)

Return whether (v, w) is a \(P\)-edge of self.

(v, w) is an edge if v is obtained from w by deleting a letter.

EXAMPLES:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()
sage: v = BinaryWord.vertices(2)[1]; v
word: 11
sage: [w for w in BinaryWord.vertices(3) if BinaryWord.is_P_edge(v, w)]
[word: 101, word: 110, word: 111]
sage: [w for w in BinaryWord.vertices(4) if BinaryWord.is_P_edge(v, w)]
[]

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()
>>> v = BinaryWord.vertices(Integer(2))[Integer(1)]; v
word: 11
>>> [w for w in BinaryWord.vertices(Integer(3)) if BinaryWord.is_P_edge(v, w)]
[word: 101, word: 110, word: 111]
>>> [w for w in BinaryWord.vertices(Integer(4)) if BinaryWord.is_P_edge(v, w)]
[]

is_Q_edge(v, w)

Return whether (v, w) is a \(Q\)-edge of self.

(w, v) is an edge if w is obtained from v by appending a letter.

EXAMPLES:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()
sage: v = BinaryWord.vertices(2)[0]; v
word: 10
sage: [w for w in BinaryWord.vertices(3) if BinaryWord.is_Q_edge(v, w)]
[word: 100, word: 101]
sage: [w for w in BinaryWord.vertices(4) if BinaryWord.is_Q_edge(v, w)]
[]

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()
>>> v = BinaryWord.vertices(Integer(2))[Integer(0)]; v
word: 10
>>> [w for w in BinaryWord.vertices(Integer(3)) if BinaryWord.is_Q_edge(v, w)]
[word: 100, word: 101]
>>> [w for w in BinaryWord.vertices(Integer(4)) if BinaryWord.is_Q_edge(v, w)]
[]

normalize_vertex(v)

Return v as a binary word.

EXAMPLES:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()
sage: BinaryWord.normalize_vertex([0,1]).parent()
Finite words over {0, 1}

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()
>>> BinaryWord.normalize_vertex([Integer(0),Integer(1)]).parent()
Finite words over {0, 1}

rank(v)

Return the rank of v: number of letters of the word.

EXAMPLES:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()
sage: BinaryWord.rank(BinaryWord.vertices(3)[0])
3

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()
>>> BinaryWord.rank(BinaryWord.vertices(Integer(3))[Integer(0)])
3

vertices(n)

Return the vertices of the dual graded graph on level n.

EXAMPLES:

Sage

sage: BinaryWord = GrowthDiagram.rules.BinaryWord()
sage: BinaryWord.vertices(3)
[word: 100, word: 101, word: 110, word: 111]

Python

>>> from sage.all import *
>>> BinaryWord = GrowthDiagram.rules.BinaryWord()
>>> BinaryWord.vertices(Integer(3))
[word: 100, word: 101, word: 110, word: 111]

zero = word:

class sage.combinat.growth.RuleBurge

Bases: RulePartitions

A rule modelling Burge insertion.

EXAMPLES:

Sage

sage: Burge = GrowthDiagram.rules.Burge()
sage: GrowthDiagram(Burge, labels=[[],[1,1,1],[2,1,1,1],[2,1,1],[2,1],[1,1],[]])
1  1
0  1
1  0
1  0

Python

>>> from sage.all import *
>>> Burge = GrowthDiagram.rules.Burge()
>>> GrowthDiagram(Burge, labels=[[],[Integer(1),Integer(1),Integer(1)],[Integer(2),Integer(1),Integer(1),Integer(1)],[Integer(2),Integer(1),Integer(1)],[Integer(2),Integer(1)],[Integer(1),Integer(1)],[]])
1  1
0  1
1  0
1  0

The vertices of the dual graded graph are integer partitions:

Sage

sage: Burge.vertices(3)
Partitions of the integer 3

Python

>>> from sage.all import *
>>> Burge.vertices(Integer(3))
Partitions of the integer 3

The local rules implemented provide Burge’s correspondence between matrices with nonnegative integer entries and pairs of semistandard tableaux, the P_symbol() and the Q_symbol(). For permutations, it reduces to classical Schensted insertion.

Instead of passing the rule to GrowthDiagram, we can also call the rule to create growth diagrams. For example:

Sage

sage: m = matrix([[2,0,0,1,0],[1,1,0,0,0], [0,0,0,0,3]])
sage: G = Burge(m); G
2  0  0  1  0
1  1  0  0  0
0  0  0  0  3

sage: ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  2  3    1  2  5 ]
[   1  3       1  5    ]
[   1  3       1  5    ]
[   2      ,   4       ]

Python

>>> from sage.all import *
>>> m = matrix([[Integer(2),Integer(0),Integer(0),Integer(1),Integer(0)],[Integer(1),Integer(1),Integer(0),Integer(0),Integer(0)], [Integer(0),Integer(0),Integer(0),Integer(0),Integer(3)]])
>>> G = Burge(m); G
2  0  0  1  0
1  1  0  0  0
0  0  0  0  3

>>> ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  2  3    1  2  5 ]
[   1  3       1  5    ]
[   1  3       1  5    ]
[   2      ,   4       ]

For rectangular fillings, the Kleitman-Greene invariant is the shape of the P_symbol(). Put differently, it is the partition labelling the lower right corner of the filling (recall that we are using matrix coordinates). It can be computed alternatively as the transpose of the partition \((\mu_1, \ldots, \mu_n)\), where \(\mu_1 + \cdots + \mu_i\) is the maximal sum of entries in a collection of \(i\) pairwise disjoint sequences of cells with weakly decreasing row indices and weakly increasing column indices.

backward_rule(y, z, x)

Return the content and the input shape.

See [Kra2006] \((B^4 0)-(B^4 2)\). (In the arXiv version of the article there is a typo: in the computation of carry in \((B^4 2)\) , \(\rho\) must be replaced by \(\lambda\)).

INPUT:

• y, z, x – three partitions from a cell in a growth diagram, labelled as:

    x
  y z
  

OUTPUT:

A pair (t, content) consisting of the shape of the fourth partition according to the Burge correspondence and the content of the cell.

EXAMPLES:

Sage

sage: Burge = GrowthDiagram.rules.Burge()
sage: Burge.backward_rule([1,1,1],[2,1,1,1],[2,1,1])
([1, 1], 0)

Python

>>> from sage.all import *
>>> Burge = GrowthDiagram.rules.Burge()
>>> Burge.backward_rule([Integer(1),Integer(1),Integer(1)],[Integer(2),Integer(1),Integer(1),Integer(1)],[Integer(2),Integer(1),Integer(1)])
([1, 1], 0)

forward_rule(y, t, x, content)

Return the output shape given three shapes and the content.

See [Kra2006] \((F^4 0)-(F^4 2)\).

INPUT:

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

  t x
  y
  

• content – nonnegative integer; the content of the cell

OUTPUT: the fourth partition according to the Burge correspondence

EXAMPLES:

Sage

sage: Burge = GrowthDiagram.rules.Burge()
sage: Burge.forward_rule([2,1],[2,1],[2,1],1)
[3, 1]

sage: Burge.forward_rule([1],[],[2],2)
[2, 1, 1, 1]

Python

>>> from sage.all import *
>>> Burge = GrowthDiagram.rules.Burge()
>>> Burge.forward_rule([Integer(2),Integer(1)],[Integer(2),Integer(1)],[Integer(2),Integer(1)],Integer(1))
[3, 1]

>>> Burge.forward_rule([Integer(1)],[],[Integer(2)],Integer(2))
[2, 1, 1, 1]

class sage.combinat.growth.RuleDomino

Bases: Rule

A rule modelling domino insertion.

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()
sage: GrowthDiagram(Domino, [[1,0,0],[0,0,1],[0,-1,0]])
1  0  0
0  0  1
0 -1  0

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()
>>> GrowthDiagram(Domino, [[Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(0),Integer(1)],[Integer(0),-Integer(1),Integer(0)]])
1  0  0
0  0  1
0 -1  0

The vertices of the dual graded graph are integer partitions whose Ferrers diagram can be tiled with dominoes:

Sage

sage: Domino.vertices(2)
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

Python

>>> from sage.all import *
>>> Domino.vertices(Integer(2))
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

Instead of passing the rule to GrowthDiagram, we can also call the rule to create growth diagrams. For example, let us check Figure 3 in [Lam2004]:

Sage

sage: G = Domino([[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    ]

Python

>>> from sage.all import *
>>> G = Domino([[Integer(0),Integer(0),Integer(0),-Integer(1)],[Integer(0),Integer(0),Integer(1),Integer(0)],[-Integer(1),Integer(0),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0),Integer(0)]]); G
 0  0  0 -1
 0  0  1  0
-1  0  0  0
 0  1  0  0

>>> ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  2  4    1  2  2 ]
[   1  2  4    1  3  3 ]
[   3  3   ,   4  4    ]

The spin of a domino tableau is half the number of vertical dominoes:

Sage

sage: def spin(T):
....:     return sum(2*len(set(row)) - len(row) for row in T)/4

Python

>>> from sage.all import *
>>> def spin(T):
...     return sum(Integer(2)*len(set(row)) - len(row) for row in T)/Integer(4)

According to [Lam2004], the number of negative entries in the signed permutation equals the sum of the spins of the two associated tableaux:

Sage

sage: pi = [3,-1,2,4,-5]
sage: G = Domino(pi)
sage: list(G.filling().values()).count(-1) == spin(G.P_symbol()) + spin(G.Q_symbol())
True

Python

>>> from sage.all import *
>>> pi = [Integer(3),-Integer(1),Integer(2),Integer(4),-Integer(5)]
>>> G = Domino(pi)
>>> list(G.filling().values()).count(-Integer(1)) == spin(G.P_symbol()) + spin(G.Q_symbol())
True

Negating all signs transposes all the partitions:

Sage

sage: G.P_symbol() == Domino([-e for e in pi]).P_symbol().conjugate()
True

Python

>>> from sage.all import *
>>> G.P_symbol() == Domino([-e for e in pi]).P_symbol().conjugate()
True

P_symbol(P_chain)

Return the labels along the vertical boundary of a rectangular growth diagram as a (skew) domino tableau.

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()
sage: G = Domino([[0,1,0],[0,0,-1],[1,0,0]])
sage: G.P_symbol().pp()
1  1
2  3
2  3

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()
>>> G = Domino([[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),-Integer(1)],[Integer(1),Integer(0),Integer(0)]])
>>> G.P_symbol().pp()
1  1
2  3
2  3

Q_symbol(P_chain)

Return the labels along the vertical boundary of a rectangular growth diagram as a (skew) domino tableau.

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()
sage: G = Domino([[0,1,0],[0,0,-1],[1,0,0]])
sage: G.P_symbol().pp()
1  1
2  3
2  3

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()
>>> G = Domino([[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),-Integer(1)],[Integer(1),Integer(0),Integer(0)]])
>>> G.P_symbol().pp()
1  1
2  3
2  3

forward_rule(y, t, x, content)

Return the output shape given three shapes and the content.

See [Lam2004] Section 3.1.

INPUT:

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

  t x
  y
  

• content – \(-1\), \(0\) or \(1\); the content of the cell

OUTPUT: the fourth partition according to domino insertion

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()

Rule 1:

Sage

sage: Domino.forward_rule([], [], [], 1)
[2]

sage: Domino.forward_rule([1,1], [1,1], [1,1], 1)
[3, 1]

Python

>>> from sage.all import *
>>> Domino.forward_rule([], [], [], Integer(1))
[2]

>>> Domino.forward_rule([Integer(1),Integer(1)], [Integer(1),Integer(1)], [Integer(1),Integer(1)], Integer(1))
[3, 1]

Rule 2:

Sage

sage: Domino.forward_rule([1,1], [1,1], [1,1], -1)
[1, 1, 1, 1]

Python

>>> from sage.all import *
>>> Domino.forward_rule([Integer(1),Integer(1)], [Integer(1),Integer(1)], [Integer(1),Integer(1)], -Integer(1))
[1, 1, 1, 1]

Rule 3:

Sage

sage: Domino.forward_rule([1,1], [1,1], [2,2], 0)
[2, 2]

Python

>>> from sage.all import *
>>> Domino.forward_rule([Integer(1),Integer(1)], [Integer(1),Integer(1)], [Integer(2),Integer(2)], Integer(0))
[2, 2]

Rule 4:

Sage

sage: Domino.forward_rule([2,2,2], [2,2], [3,3], 0)
[3, 3, 2]

sage: Domino.forward_rule([2], [], [1,1], 0)
[2, 2]

sage: Domino.forward_rule([1,1], [], [2], 0)
[2, 2]

sage: Domino.forward_rule([2], [], [2], 0)
[2, 2]

sage: Domino.forward_rule([4], [2], [4], 0)
[4, 2]

sage: Domino.forward_rule([1,1,1,1], [1,1], [1,1,1,1], 0)
[2, 2, 1, 1]

sage: Domino.forward_rule([2,1,1], [2], [4], 0)
[4, 1, 1]

Python

>>> from sage.all import *
>>> Domino.forward_rule([Integer(2),Integer(2),Integer(2)], [Integer(2),Integer(2)], [Integer(3),Integer(3)], Integer(0))
[3, 3, 2]

>>> Domino.forward_rule([Integer(2)], [], [Integer(1),Integer(1)], Integer(0))
[2, 2]

>>> Domino.forward_rule([Integer(1),Integer(1)], [], [Integer(2)], Integer(0))
[2, 2]

>>> Domino.forward_rule([Integer(2)], [], [Integer(2)], Integer(0))
[2, 2]

>>> Domino.forward_rule([Integer(4)], [Integer(2)], [Integer(4)], Integer(0))
[4, 2]

>>> Domino.forward_rule([Integer(1),Integer(1),Integer(1),Integer(1)], [Integer(1),Integer(1)], [Integer(1),Integer(1),Integer(1),Integer(1)], Integer(0))
[2, 2, 1, 1]

>>> Domino.forward_rule([Integer(2),Integer(1),Integer(1)], [Integer(2)], [Integer(4)], Integer(0))
[4, 1, 1]

is_P_edge(v, w)

Return whether (v, w) is a \(P\)-edge of self.

(v, w) is an edge if v is obtained from w by deleting a domino.

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()
sage: v = Domino.vertices(2)[1]; ascii_art(v)
***
*
sage: ascii_art([w for w in Domino.vertices(3) if Domino.is_P_edge(v, w)])
[             *** ]
[             *   ]
[ *****  ***  *   ]
[ *    , ***, *   ]
sage: [w for w in Domino.vertices(4) if Domino.is_P_edge(v, w)]
[]

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()
>>> v = Domino.vertices(Integer(2))[Integer(1)]; ascii_art(v)
***
*
>>> ascii_art([w for w in Domino.vertices(Integer(3)) if Domino.is_P_edge(v, w)])
[             *** ]
[             *   ]
[ *****  ***  *   ]
[ *    , ***, *   ]
>>> [w for w in Domino.vertices(Integer(4)) if Domino.is_P_edge(v, w)]
[]

is_Q_edge(v, w)

Return whether (v, w) is a \(P\)-edge of self.

(v, w) is an edge if v is obtained from w by deleting a domino.

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()
sage: v = Domino.vertices(2)[1]; ascii_art(v)
***
*
sage: ascii_art([w for w in Domino.vertices(3) if Domino.is_P_edge(v, w)])
[             *** ]
[             *   ]
[ *****  ***  *   ]
[ *    , ***, *   ]
sage: [w for w in Domino.vertices(4) if Domino.is_P_edge(v, w)]
[]

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()
>>> v = Domino.vertices(Integer(2))[Integer(1)]; ascii_art(v)
***
*
>>> ascii_art([w for w in Domino.vertices(Integer(3)) if Domino.is_P_edge(v, w)])
[             *** ]
[             *   ]
[ *****  ***  *   ]
[ *    , ***, *   ]
>>> [w for w in Domino.vertices(Integer(4)) if Domino.is_P_edge(v, w)]
[]

normalize_vertex(v)

Return v as a partition.

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()
sage: Domino.normalize_vertex([3,1]).parent()
Partitions

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()
>>> Domino.normalize_vertex([Integer(3),Integer(1)]).parent()
Partitions

r = 2

rank(v)

Return the rank of v.

The rank of a vertex is half the size of the partition, which equals the number of dominoes in any filling.

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()
sage: Domino.rank(Domino.vertices(3)[0])
3

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()
>>> Domino.rank(Domino.vertices(Integer(3))[Integer(0)])
3

vertices(n)

Return the vertices of the dual graded graph on level n.

EXAMPLES:

Sage

sage: Domino = GrowthDiagram.rules.Domino()
sage: Domino.vertices(2)
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

Python

>>> from sage.all import *
>>> Domino = GrowthDiagram.rules.Domino()
>>> Domino.vertices(Integer(2))
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

zero = []

class sage.combinat.growth.RuleLLMS(k)

Bases: Rule

A rule modelling the Schensted correspondence for affine permutations.

EXAMPLES:

Sage

sage: LLMS3 = GrowthDiagram.rules.LLMS(3)
sage: GrowthDiagram(LLMS3, [3,1,2])
0  1  0
0  0  1
1  0  0

Python

>>> from sage.all import *
>>> LLMS3 = GrowthDiagram.rules.LLMS(Integer(3))
>>> GrowthDiagram(LLMS3, [Integer(3),Integer(1),Integer(2)])
0  1  0
0  0  1
1  0  0

The vertices of the dual graded graph are Cores:

Sage

sage: LLMS3.vertices(4)
3-Cores of length 4

Python

>>> from sage.all import *
>>> LLMS3.vertices(Integer(4))
3-Cores of length 4

Let us check example of Figure 1 in [LS2007]. Note that, instead of passing the rule to GrowthDiagram, we can also call the rule to create growth diagrams:

Sage

sage: G = LLMS3([4,1,2,6,3,5]); G
0  1  0  0  0  0
0  0  1  0  0  0
0  0  0  0  1  0
1  0  0  0  0  0
0  0  0  0  0  1
0  0  0  1  0  0

Python

>>> from sage.all import *
>>> G = LLMS3([Integer(4),Integer(1),Integer(2),Integer(6),Integer(3),Integer(5)]); G
0  1  0  0  0  0
0  0  1  0  0  0
0  0  0  0  1  0
1  0  0  0  0  0
0  0  0  0  0  1
0  0  0  1  0  0

The P_symbol() is a StrongTableau:

Sage

sage: G.P_symbol().pp()
-1 -2 -3 -5
 3  5
-4 -6
 5
 6

Python

>>> from sage.all import *
>>> G.P_symbol().pp()
-1 -2 -3 -5
 3  5
-4 -6
 5
 6

The Q_symbol() is a WeakTableau:

Sage

sage: G.Q_symbol().pp()
1  3  4  5
2  5
3  6
5
6

Python

>>> from sage.all import *
>>> G.Q_symbol().pp()
1  3  4  5
2  5
3  6
5
6

Let us also check Example 6.2 in [LLMSSZ2013]:

Sage

sage: G = LLMS3([4,1,3,2])
sage: G.P_symbol().pp()
-1 -2  3
-3
-4

sage: G.Q_symbol().pp()
1  3  4
2
3

Python

>>> from sage.all import *
>>> G = LLMS3([Integer(4),Integer(1),Integer(3),Integer(2)])
>>> G.P_symbol().pp()
-1 -2  3
-3
-4

>>> G.Q_symbol().pp()
1  3  4
2
3

P_symbol(P_chain)

Return the labels along the vertical boundary of a rectangular growth diagram as a skew StrongTableau.

EXAMPLES:

Sage

sage: LLMS4 = GrowthDiagram.rules.LLMS(4)
sage: G = LLMS4([3,4,1,2])
sage: G.P_symbol().pp()
-1 -2
-3 -4

Python

>>> from sage.all import *
>>> LLMS4 = GrowthDiagram.rules.LLMS(Integer(4))
>>> G = LLMS4([Integer(3),Integer(4),Integer(1),Integer(2)])
>>> G.P_symbol().pp()
-1 -2
-3 -4

Q_symbol(Q_chain)

Return the labels along the horizontal boundary of a rectangular growth diagram as a skew WeakTableau.

EXAMPLES:

Sage

sage: LLMS4 = GrowthDiagram.rules.LLMS(4)
sage: G = LLMS4([3,4,1,2])
sage: G.Q_symbol().pp()
1 2
3 4

Python

>>> from sage.all import *
>>> LLMS4 = GrowthDiagram.rules.LLMS(Integer(4))
>>> G = LLMS4([Integer(3),Integer(4),Integer(1),Integer(2)])
>>> G.Q_symbol().pp()
1 2
3 4

forward_rule(y, e, t, f, x, content)

Return the output path given two incident edges and the content.

See [LS2007] Section 3.4 and [LLMSSZ2013] Section 6.3.

INPUT:

• y, e, t, f, x – a path of three partitions and two colors from a cell in a growth diagram, labelled as:

  t f x
  e
  y
  

• content – \(0\) or \(1\); the content of the cell

OUTPUT:

The two colors and the fourth partition g, z, h according to LLMS insertion.

EXAMPLES:

Sage

sage: LLMS3 = GrowthDiagram.rules.LLMS(3)
sage: LLMS4 = GrowthDiagram.rules.LLMS(4)

sage: Z = LLMS3.zero
sage: LLMS3.forward_rule(Z, None, Z, None, Z, 0)
(None, [], None)

sage: LLMS3.forward_rule(Z, None, Z, None, Z, 1)
(None, [1], 0)

sage: Y = Core([3,1,1], 3)
sage: LLMS3.forward_rule(Y, None, Y, None, Y, 1)
(None, [4, 2, 1, 1], 3)

Python

>>> from sage.all import *
>>> LLMS3 = GrowthDiagram.rules.LLMS(Integer(3))
>>> LLMS4 = GrowthDiagram.rules.LLMS(Integer(4))

>>> Z = LLMS3.zero
>>> LLMS3.forward_rule(Z, None, Z, None, Z, Integer(0))
(None, [], None)

>>> LLMS3.forward_rule(Z, None, Z, None, Z, Integer(1))
(None, [1], 0)

>>> Y = Core([Integer(3),Integer(1),Integer(1)], Integer(3))
>>> LLMS3.forward_rule(Y, None, Y, None, Y, Integer(1))
(None, [4, 2, 1, 1], 3)

if x != y:

Sage

sage: Y = Core([1,1], 3); T = Core([1], 3); X = Core([2], 3)
sage: LLMS3.forward_rule(Y, -1, T, None, X, 0)
(None, [2, 1, 1], -1)

sage: Y = Core([2], 4); T = Core([1], 4); X = Core([1,1], 4)
sage: LLMS4.forward_rule(Y, 1, T, None, X, 0)
(None, [2, 1], 1)

sage: Y = Core([2,1,1], 3); T = Core([2], 3); X = Core([3,1], 3)
sage: LLMS3.forward_rule(Y, -1, T, None, X, 0)
(None, [3, 1, 1], -2)

Python

>>> from sage.all import *
>>> Y = Core([Integer(1),Integer(1)], Integer(3)); T = Core([Integer(1)], Integer(3)); X = Core([Integer(2)], Integer(3))
>>> LLMS3.forward_rule(Y, -Integer(1), T, None, X, Integer(0))
(None, [2, 1, 1], -1)

>>> Y = Core([Integer(2)], Integer(4)); T = Core([Integer(1)], Integer(4)); X = Core([Integer(1),Integer(1)], Integer(4))
>>> LLMS4.forward_rule(Y, Integer(1), T, None, X, Integer(0))
(None, [2, 1], 1)

>>> Y = Core([Integer(2),Integer(1),Integer(1)], Integer(3)); T = Core([Integer(2)], Integer(3)); X = Core([Integer(3),Integer(1)], Integer(3))
>>> LLMS3.forward_rule(Y, -Integer(1), T, None, X, Integer(0))
(None, [3, 1, 1], -2)

if x == y != t:

Sage

sage: Y = Core([1], 3); T = Core([], 3); X = Core([1], 3)
sage: LLMS3.forward_rule(Y, 0, T, None, X, 0)
(None, [1, 1], -1)

sage: Y = Core([1], 4); T = Core([], 4); X = Core([1], 4)
sage: LLMS4.forward_rule(Y, 0, T, None, X, 0)
(None, [1, 1], -1)

sage: Y = Core([2,1], 4); T = Core([1,1], 4); X = Core([2,1], 4)
sage: LLMS4.forward_rule(Y, 1, T, None, X, 0)
(None, [2, 2], 0)

Python

>>> from sage.all import *
>>> Y = Core([Integer(1)], Integer(3)); T = Core([], Integer(3)); X = Core([Integer(1)], Integer(3))
>>> LLMS3.forward_rule(Y, Integer(0), T, None, X, Integer(0))
(None, [1, 1], -1)

>>> Y = Core([Integer(1)], Integer(4)); T = Core([], Integer(4)); X = Core([Integer(1)], Integer(4))
>>> LLMS4.forward_rule(Y, Integer(0), T, None, X, Integer(0))
(None, [1, 1], -1)

>>> Y = Core([Integer(2),Integer(1)], Integer(4)); T = Core([Integer(1),Integer(1)], Integer(4)); X = Core([Integer(2),Integer(1)], Integer(4))
>>> LLMS4.forward_rule(Y, Integer(1), T, None, X, Integer(0))
(None, [2, 2], 0)

has_multiple_edges = True

is_P_edge(v, w)

Return whether (v, w) is a \(P\)-edge of self.

For two k-cores v and w containing v, there are as many edges as there are components in the skew partition w/v. These components are ribbons, and therefore contain a unique cell with maximal content. We index the edge with this content.

EXAMPLES:

Sage

sage: LLMS4 = GrowthDiagram.rules.LLMS(4)
sage: v = LLMS4.vertices(2)[0]; v
[2]
sage: [(w, LLMS4.is_P_edge(v, w)) for w in LLMS4.vertices(3)]
[([3], [2]), ([2, 1], [-1]), ([1, 1, 1], [])]
sage: all(LLMS4.is_P_edge(v, w) == [] for w in LLMS4.vertices(4))
True

Python

>>> from sage.all import *
>>> LLMS4 = GrowthDiagram.rules.LLMS(Integer(4))
>>> v = LLMS4.vertices(Integer(2))[Integer(0)]; v
[2]
>>> [(w, LLMS4.is_P_edge(v, w)) for w in LLMS4.vertices(Integer(3))]
[([3], [2]), ([2, 1], [-1]), ([1, 1, 1], [])]
>>> all(LLMS4.is_P_edge(v, w) == [] for w in LLMS4.vertices(Integer(4)))
True

is_Q_edge(v, w)

Return whether (v, w) is a \(Q\)-edge of self.

(v, w) is an edge if w is a weak cover of v, see weak_covers().

EXAMPLES:

Sage

sage: LLMS4 = GrowthDiagram.rules.LLMS(4)
sage: v = LLMS4.vertices(3)[1]; v
[2, 1]
sage: [w for w in LLMS4.vertices(4) if len(LLMS4.is_Q_edge(v, w)) > 0]
[[2, 2], [3, 1, 1]]
sage: all(LLMS4.is_Q_edge(v, w) == [] for w in LLMS4.vertices(5))
True

Python

>>> from sage.all import *
>>> LLMS4 = GrowthDiagram.rules.LLMS(Integer(4))
>>> v = LLMS4.vertices(Integer(3))[Integer(1)]; v
[2, 1]
>>> [w for w in LLMS4.vertices(Integer(4)) if len(LLMS4.is_Q_edge(v, w)) > Integer(0)]
[[2, 2], [3, 1, 1]]
>>> all(LLMS4.is_Q_edge(v, w) == [] for w in LLMS4.vertices(Integer(5)))
True

normalize_vertex(v)

Convert v to a \(k\)-core.

EXAMPLES:

Sage

sage: LLMS3 = GrowthDiagram.rules.LLMS(3)
sage: LLMS3.normalize_vertex([3,1]).parent()
3-Cores of length 3

Python

>>> from sage.all import *
>>> LLMS3 = GrowthDiagram.rules.LLMS(Integer(3))
>>> LLMS3.normalize_vertex([Integer(3),Integer(1)]).parent()
3-Cores of length 3

rank(v)

Return the rank of v: the length of the core.

EXAMPLES:

Sage

sage: LLMS3 = GrowthDiagram.rules.LLMS(3)
sage: LLMS3.rank(LLMS3.vertices(3)[0])
3

Python

>>> from sage.all import *
>>> LLMS3 = GrowthDiagram.rules.LLMS(Integer(3))
>>> LLMS3.rank(LLMS3.vertices(Integer(3))[Integer(0)])
3

vertices(n)

Return the vertices of the dual graded graph on level n.

EXAMPLES:

Sage

sage: LLMS3 = GrowthDiagram.rules.LLMS(3)
sage: LLMS3.vertices(2)
3-Cores of length 2

Python

>>> from sage.all import *
>>> LLMS3 = GrowthDiagram.rules.LLMS(Integer(3))
>>> LLMS3.vertices(Integer(2))
3-Cores of length 2

zero_edge = None

class sage.combinat.growth.RulePartitions

Bases: Rule

A rule for growth diagrams on Young’s lattice on integer partitions graded by size.

P_symbol(P_chain)

Return the labels along the vertical boundary of a rectangular growth diagram as a (skew) tableau.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: G = RuleRSK([[0,1,0], [1,0,2]])
sage: G.P_symbol().pp()
1  2  2
2

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> G = RuleRSK([[Integer(0),Integer(1),Integer(0)], [Integer(1),Integer(0),Integer(2)]])
>>> G.P_symbol().pp()
1  2  2
2

Q_symbol(Q_chain)

Return the labels along the horizontal boundary of a rectangular growth diagram as a skew tableau.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: G = RuleRSK([[0,1,0], [1,0,2]])
sage: G.Q_symbol().pp()
1  3  3
2

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> G = RuleRSK([[Integer(0),Integer(1),Integer(0)], [Integer(1),Integer(0),Integer(2)]])
>>> G.Q_symbol().pp()
1  3  3
2

normalize_vertex(v)

Return v as a partition.

EXAMPLES:

Sage

sage: RSK = GrowthDiagram.rules.RSK()
sage: RSK.normalize_vertex([3,1]).parent()
Partitions

Python

>>> from sage.all import *
>>> RSK = GrowthDiagram.rules.RSK()
>>> RSK.normalize_vertex([Integer(3),Integer(1)]).parent()
Partitions

rank(v)

Return the rank of v: the size of the partition.

EXAMPLES:

Sage

sage: RSK = GrowthDiagram.rules.RSK()
sage: RSK.rank(RSK.vertices(3)[0])
3

Python

>>> from sage.all import *
>>> RSK = GrowthDiagram.rules.RSK()
>>> RSK.rank(RSK.vertices(Integer(3))[Integer(0)])
3

vertices(n)

Return the vertices of the dual graded graph on level n.

EXAMPLES:

Sage

sage: RSK = GrowthDiagram.rules.RSK()
sage: RSK.vertices(3)
Partitions of the integer 3

Python

>>> from sage.all import *
>>> RSK = GrowthDiagram.rules.RSK()
>>> RSK.vertices(Integer(3))
Partitions of the integer 3

zero = []

class sage.combinat.growth.RuleRSK

Bases: RulePartitions

A rule modelling Robinson-Schensted-Knuth insertion.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: GrowthDiagram(RuleRSK, [3,2,1,2,3])
0  0  1  0  0
0  1  0  1  0
1  0  0  0  1

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> GrowthDiagram(RuleRSK, [Integer(3),Integer(2),Integer(1),Integer(2),Integer(3)])
0  0  1  0  0
0  1  0  1  0
1  0  0  0  1

The vertices of the dual graded graph are integer partitions:

Sage

sage: RuleRSK.vertices(3)
Partitions of the integer 3

Python

>>> from sage.all import *
>>> RuleRSK.vertices(Integer(3))
Partitions of the integer 3

The local rules implemented provide the RSK correspondence between matrices with nonnegative integer entries and pairs of semistandard tableaux, the P_symbol() and the Q_symbol(). For permutations, it reduces to classical Schensted insertion.

Instead of passing the rule to GrowthDiagram, we can also call the rule to create growth diagrams. For example:

Sage

sage: m = matrix([[0,0,0,0,1],[1,1,0,2,0], [0,3,0,0,0]])
sage: G = RuleRSK(m); G
0  0  0  0  1
1  1  0  2  0
0  3  0  0  0

sage: ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  2  2  2  3    1  2  2  2  2 ]
[   2  3             4  4          ]
[   3            ,   5             ]

Python

>>> from sage.all import *
>>> m = matrix([[Integer(0),Integer(0),Integer(0),Integer(0),Integer(1)],[Integer(1),Integer(1),Integer(0),Integer(2),Integer(0)], [Integer(0),Integer(3),Integer(0),Integer(0),Integer(0)]])
>>> G = RuleRSK(m); G
0  0  0  0  1
1  1  0  2  0
0  3  0  0  0

>>> ascii_art([G.P_symbol(), G.Q_symbol()])
[   1  2  2  2  3    1  2  2  2  2 ]
[   2  3             4  4          ]
[   3            ,   5             ]

For rectangular fillings, the Kleitman-Greene invariant is the shape of the P_symbol() (or the Q_symbol()). Put differently, it is the partition labelling the lower right corner of the filling (recall that we are using matrix coordinates). It can be computed alternatively as the partition \((\mu_1,\dots,\mu_n)\), where \(\mu_1 + \dots + \mu_i\) is the maximal sum of entries in a collection of \(i\) pairwise disjoint sequences of cells with weakly increasing coordinates.

For rectangular fillings, we could also use the (faster) implementation provided via RSK(). Because the of the coordinate conventions in RSK(), we have to transpose matrices:

Sage

sage: [G.P_symbol(), G.Q_symbol()] == RSK(m.transpose())
True

sage: n = 5; l = [(pi, RuleRSK(pi)) for pi in Permutations(n)]
sage: all([G.P_symbol(), G.Q_symbol()] == RSK(pi) for pi, G in l)
True

sage: n = 5; l = [(w, RuleRSK(w)) for w in Words([1,2,3], 5)]
sage: all([G.P_symbol(), G.Q_symbol()] == RSK(pi) for pi, G in l)
True

Python

>>> from sage.all import *
>>> [G.P_symbol(), G.Q_symbol()] == RSK(m.transpose())
True

>>> n = Integer(5); l = [(pi, RuleRSK(pi)) for pi in Permutations(n)]
>>> all([G.P_symbol(), G.Q_symbol()] == RSK(pi) for pi, G in l)
True

>>> n = Integer(5); l = [(w, RuleRSK(w)) for w in Words([Integer(1),Integer(2),Integer(3)], Integer(5))]
>>> all([G.P_symbol(), G.Q_symbol()] == RSK(pi) for pi, G in l)
True

backward_rule(y, z, x)

Return the content and the input shape.

See [Kra2006] \((B^1 0)-(B^1 2)\).

INPUT:

• y, z, x – three partitions 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 according to the Robinson-Schensted-Knuth correspondence and the content of the cell.

forward_rule(y, t, x, content)

Return the output shape given three shapes and the content.

See [Kra2006] \((F^1 0)-(F^1 2)\).

INPUT:

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

  t x
  y
  

• content – nonnegative integer; the content of the cell

OUTPUT:

The fourth partition according to the Robinson-Schensted-Knuth correspondence.

EXAMPLES:

Sage

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: RuleRSK.forward_rule([2,1],[2,1],[2,1],1)
[3, 1]

sage: RuleRSK.forward_rule([1],[],[2],2)
[4, 1]

Python

>>> from sage.all import *
>>> RuleRSK = GrowthDiagram.rules.RSK()
>>> RuleRSK.forward_rule([Integer(2),Integer(1)],[Integer(2),Integer(1)],[Integer(2),Integer(1)],Integer(1))
[3, 1]

>>> RuleRSK.forward_rule([Integer(1)],[],[Integer(2)],Integer(2))
[4, 1]

class sage.combinat.growth.RuleShiftedShapes

Bases: Rule

A class modelling the Schensted correspondence for shifted shapes.

This agrees with Sagan [Sag1987] and Worley’s [Wor1984], and Haiman’s [Hai1989] insertion algorithms, see Proposition 4.5.2 of [Fom1995].

EXAMPLES:

Sage

sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: GrowthDiagram(Shifted, [3,1,2])
0  1  0
0  0  1
1  0  0

Python

>>> from sage.all import *
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> GrowthDiagram(Shifted, [Integer(3),Integer(1),Integer(2)])
0  1  0
0  0  1
1  0  0

The vertices of the dual graded graph are shifted shapes:

Sage

sage: Shifted.vertices(3)
Partitions of the integer 3 satisfying constraints max_slope=-1

Python

>>> from sage.all import *
>>> Shifted.vertices(Integer(3))
Partitions of the integer 3 satisfying constraints max_slope=-1

Let us check the example just before Corollary 3.2 in [Sag1987]. Note that, instead of passing the rule to GrowthDiagram, we can also call the rule to create growth diagrams:

Sage

sage: G = Shifted([2,6,5,1,7,4,3])
sage: G.P_chain()
[[], 0, [1], 0, [2], 0, [3], 0, [3, 1], 0, [3, 2], 0, [4, 2], 0, [5, 2]]
sage: G.Q_chain()
[[], 1, [1], 2, [2], 1, [2, 1], 3, [3, 1], 2, [4, 1], 3, [4, 2], 3, [5, 2]]

Python

>>> from sage.all import *
>>> G = Shifted([Integer(2),Integer(6),Integer(5),Integer(1),Integer(7),Integer(4),Integer(3)])
>>> G.P_chain()
[[], 0, [1], 0, [2], 0, [3], 0, [3, 1], 0, [3, 2], 0, [4, 2], 0, [5, 2]]
>>> G.Q_chain()
[[], 1, [1], 2, [2], 1, [2, 1], 3, [3, 1], 2, [4, 1], 3, [4, 2], 3, [5, 2]]

P_symbol(P_chain)

Return the labels along the vertical boundary of a rectangular growth diagram as a shifted tableau.

EXAMPLES:

Check the example just before Corollary 3.2 in [Sag1987]:

Sage

sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: G = Shifted([2,6,5,1,7,4,3])
sage: G.P_symbol().pp()
1  2  3  6  7
   4  5

Python

>>> from sage.all import *
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> G = Shifted([Integer(2),Integer(6),Integer(5),Integer(1),Integer(7),Integer(4),Integer(3)])
>>> G.P_symbol().pp()
1  2  3  6  7
   4  5

Check the example just before Corollary 8.2 in [SS1990]:

Sage

sage: T = ShiftedPrimedTableau([[4],[1],[5]], skew=[3,1])
sage: T.pp()
 .  .  .  4
    .  1
       5
sage: U = ShiftedPrimedTableau([[1],[3.5],[5]], skew=[3,1])
sage: U.pp()
 .  .  .  1
    .  4'
       5
sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: labels = [mu if is_even(i) else 0
....:           for i, mu in enumerate(T.to_chain()[::-1])] + U.to_chain()[1:]
sage: G = Shifted({(1,2):1, (2,1):1}, shape=[5,5,5,5,5], labels=labels)
sage: G.P_symbol().pp()
 .  .  .  .  2
    .  .  1  3
       .  4  5

Python

>>> from sage.all import *
>>> T = ShiftedPrimedTableau([[Integer(4)],[Integer(1)],[Integer(5)]], skew=[Integer(3),Integer(1)])
>>> T.pp()
 .  .  .  4
    .  1
       5
>>> U = ShiftedPrimedTableau([[Integer(1)],[RealNumber('3.5')],[Integer(5)]], skew=[Integer(3),Integer(1)])
>>> U.pp()
 .  .  .  1
    .  4'
       5
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> labels = [mu if is_even(i) else Integer(0)
...           for i, mu in enumerate(T.to_chain()[::-Integer(1)])] + U.to_chain()[Integer(1):]
>>> G = Shifted({(Integer(1),Integer(2)):Integer(1), (Integer(2),Integer(1)):Integer(1)}, shape=[Integer(5),Integer(5),Integer(5),Integer(5),Integer(5)], labels=labels)
>>> G.P_symbol().pp()
 .  .  .  .  2
    .  .  1  3
       .  4  5

Q_symbol(Q_chain)

Return the labels along the horizontal boundary of a rectangular growth diagram as a skew tableau.

EXAMPLES:

Check the example just before Corollary 3.2 in [Sag1987]:

Sage

sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: G = Shifted([2,6,5,1,7,4,3])
sage: G.Q_symbol().pp()
1  2  4' 5  7'
   3  6'

Python

>>> from sage.all import *
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> G = Shifted([Integer(2),Integer(6),Integer(5),Integer(1),Integer(7),Integer(4),Integer(3)])
>>> G.Q_symbol().pp()
1  2  4' 5  7'
   3  6'

Check the example just before Corollary 8.2 in [SS1990]:

Sage

sage: T = ShiftedPrimedTableau([[4],[1],[5]], skew=[3,1])
sage: T.pp()
 .  .  .  4
    .  1
       5
sage: U = ShiftedPrimedTableau([[1],[3.5],[5]], skew=[3,1])
sage: U.pp()
 .  .  .  1
    .  4'
       5
sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: labels = [mu if is_even(i) else 0
....:           for i, mu in enumerate(T.to_chain()[::-1])] + U.to_chain()[1:]
sage: G = Shifted({(1,2):1, (2,1):1}, shape=[5,5,5,5,5], labels=labels)
sage: G.Q_symbol().pp()
 .  .  .  .  2
    .  .  1  4'
       .  3' 5'

Python

>>> from sage.all import *
>>> T = ShiftedPrimedTableau([[Integer(4)],[Integer(1)],[Integer(5)]], skew=[Integer(3),Integer(1)])
>>> T.pp()
 .  .  .  4
    .  1
       5
>>> U = ShiftedPrimedTableau([[Integer(1)],[RealNumber('3.5')],[Integer(5)]], skew=[Integer(3),Integer(1)])
>>> U.pp()
 .  .  .  1
    .  4'
       5
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> labels = [mu if is_even(i) else Integer(0)
...           for i, mu in enumerate(T.to_chain()[::-Integer(1)])] + U.to_chain()[Integer(1):]
>>> G = Shifted({(Integer(1),Integer(2)):Integer(1), (Integer(2),Integer(1)):Integer(1)}, shape=[Integer(5),Integer(5),Integer(5),Integer(5),Integer(5)], labels=labels)
>>> G.Q_symbol().pp()
 .  .  .  .  2
    .  .  1  4'
       .  3' 5'

backward_rule(y, g, z, h, x)

Return the input path and the content given two incident edges.

See [Fom1995] Lemma 4.5.1, page 38.

INPUT:

• y, g, z, h, x – a path of three partitions and two colors from a cell in a growth diagram, labelled as:

      x
      h
  y g z
  

OUTPUT:

A tuple (e, t, f, content) consisting of the shape t of the fourth word, the colours of the incident edges and the content of the cell according to Sagan - Worley insertion.

EXAMPLES:

Sage

sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: Shifted.backward_rule([], 1, [1], 0, [])
(0, [], 0, 1)

sage: Shifted.backward_rule([1], 2, [2], 0, [1])
(0, [1], 0, 1)

Python

>>> from sage.all import *
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> Shifted.backward_rule([], Integer(1), [Integer(1)], Integer(0), [])
(0, [], 0, 1)

>>> Shifted.backward_rule([Integer(1)], Integer(2), [Integer(2)], Integer(0), [Integer(1)])
(0, [1], 0, 1)

if x != y:

Sage

sage: Shifted.backward_rule([3], 1, [3, 1], 0, [2,1])
(0, [2], 1, 0)

sage: Shifted.backward_rule([2,1], 2, [3, 1], 0, [3])
(0, [2], 2, 0)

Python

>>> from sage.all import *
>>> Shifted.backward_rule([Integer(3)], Integer(1), [Integer(3), Integer(1)], Integer(0), [Integer(2),Integer(1)])
(0, [2], 1, 0)

>>> Shifted.backward_rule([Integer(2),Integer(1)], Integer(2), [Integer(3), Integer(1)], Integer(0), [Integer(3)])
(0, [2], 2, 0)

if x == y != t:

Sage

sage: Shifted.backward_rule([3], 1, [3, 1], 0, [3])
(0, [2], 2, 0)

sage: Shifted.backward_rule([3,1], 2, [3, 2], 0, [3,1])
(0, [2, 1], 2, 0)

sage: Shifted.backward_rule([2,1], 3, [3, 1], 0, [2,1])
(0, [2], 1, 0)

sage: Shifted.backward_rule([3], 3, [4], 0, [3])
(0, [2], 3, 0)

Python

>>> from sage.all import *
>>> Shifted.backward_rule([Integer(3)], Integer(1), [Integer(3), Integer(1)], Integer(0), [Integer(3)])
(0, [2], 2, 0)

>>> Shifted.backward_rule([Integer(3),Integer(1)], Integer(2), [Integer(3), Integer(2)], Integer(0), [Integer(3),Integer(1)])
(0, [2, 1], 2, 0)

>>> Shifted.backward_rule([Integer(2),Integer(1)], Integer(3), [Integer(3), Integer(1)], Integer(0), [Integer(2),Integer(1)])
(0, [2], 1, 0)

>>> Shifted.backward_rule([Integer(3)], Integer(3), [Integer(4)], Integer(0), [Integer(3)])
(0, [2], 3, 0)

forward_rule(y, e, t, f, x, content)

Return the output path given two incident edges and the content.

See [Fom1995] Lemma 4.5.1, page 38.

INPUT:

• y, e, t, f, x – a path of three partitions and two colors from a cell in a growth diagram, labelled as:

  t f x
  e
  y
  

• content – \(0\) or \(1\); the content of the cell

OUTPUT:

The two colors and the fourth partition g, z, h according to Sagan-Worley insertion.

EXAMPLES:

Sage

sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: Shifted.forward_rule([], 0, [], 0, [], 1)
(1, [1], 0)

sage: Shifted.forward_rule([1], 0, [1], 0, [1], 1)
(2, [2], 0)

Python

>>> from sage.all import *
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> Shifted.forward_rule([], Integer(0), [], Integer(0), [], Integer(1))
(1, [1], 0)

>>> Shifted.forward_rule([Integer(1)], Integer(0), [Integer(1)], Integer(0), [Integer(1)], Integer(1))
(2, [2], 0)

if x != y:

Sage

sage: Shifted.forward_rule([3], 0, [2], 1, [2,1], 0)
(1, [3, 1], 0)

sage: Shifted.forward_rule([2,1], 0, [2], 2, [3], 0)
(2, [3, 1], 0)

Python

>>> from sage.all import *
>>> Shifted.forward_rule([Integer(3)], Integer(0), [Integer(2)], Integer(1), [Integer(2),Integer(1)], Integer(0))
(1, [3, 1], 0)

>>> Shifted.forward_rule([Integer(2),Integer(1)], Integer(0), [Integer(2)], Integer(2), [Integer(3)], Integer(0))
(2, [3, 1], 0)

if x == y != t:

Sage

sage: Shifted.forward_rule([3], 0, [2], 2, [3], 0)
(1, [3, 1], 0)

sage: Shifted.forward_rule([3,1], 0, [2,1], 2, [3,1], 0)
(2, [3, 2], 0)

sage: Shifted.forward_rule([2,1], 0, [2], 1, [2,1], 0)
(3, [3, 1], 0)

sage: Shifted.forward_rule([3], 0, [2], 3, [3], 0)
(3, [4], 0)

Python

>>> from sage.all import *
>>> Shifted.forward_rule([Integer(3)], Integer(0), [Integer(2)], Integer(2), [Integer(3)], Integer(0))
(1, [3, 1], 0)

>>> Shifted.forward_rule([Integer(3),Integer(1)], Integer(0), [Integer(2),Integer(1)], Integer(2), [Integer(3),Integer(1)], Integer(0))
(2, [3, 2], 0)

>>> Shifted.forward_rule([Integer(2),Integer(1)], Integer(0), [Integer(2)], Integer(1), [Integer(2),Integer(1)], Integer(0))
(3, [3, 1], 0)

>>> Shifted.forward_rule([Integer(3)], Integer(0), [Integer(2)], Integer(3), [Integer(3)], Integer(0))
(3, [4], 0)

has_multiple_edges = True

is_P_edge(v, w)

Return whether (v, w) is a \(P\)-edge of self.

(v, w) is an edge if w contains v.

EXAMPLES:

Sage

sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: v = Shifted.vertices(2)[0]; v
[2]
sage: [w for w in Shifted.vertices(3) if Shifted.is_P_edge(v, w)]
[[3], [2, 1]]

Python

>>> from sage.all import *
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> v = Shifted.vertices(Integer(2))[Integer(0)]; v
[2]
>>> [w for w in Shifted.vertices(Integer(3)) if Shifted.is_P_edge(v, w)]
[[3], [2, 1]]

is_Q_edge(v, w)

Return whether (v, w) is a \(Q\)-edge of self.

(v, w) is an edge if w is obtained from v by adding a cell. It is a black (color 1) edge, if the cell is on the diagonal, otherwise it can be blue or red (color 2 or 3).

EXAMPLES:

Sage

sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: v = Shifted.vertices(2)[0]; v
[2]
sage: [(w, Shifted.is_Q_edge(v, w)) for w in Shifted.vertices(3)]
[([3], [2, 3]), ([2, 1], [1])]
sage: all(Shifted.is_Q_edge(v, w) == [] for w in Shifted.vertices(4))
True

Python

>>> from sage.all import *
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> v = Shifted.vertices(Integer(2))[Integer(0)]; v
[2]
>>> [(w, Shifted.is_Q_edge(v, w)) for w in Shifted.vertices(Integer(3))]
[([3], [2, 3]), ([2, 1], [1])]
>>> all(Shifted.is_Q_edge(v, w) == [] for w in Shifted.vertices(Integer(4)))
True

normalize_vertex(v)

Return v as a partition.

EXAMPLES:

Sage

sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: Shifted.normalize_vertex([3,1]).parent()
Partitions

Python

>>> from sage.all import *
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> Shifted.normalize_vertex([Integer(3),Integer(1)]).parent()
Partitions

rank(v)

Return the rank of v: the size of the shifted partition.

EXAMPLES:

Sage

sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: Shifted.rank(Shifted.vertices(3)[0])
3

Python

>>> from sage.all import *
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> Shifted.rank(Shifted.vertices(Integer(3))[Integer(0)])
3

vertices(n)

Return the vertices of the dual graded graph on level n.

EXAMPLES:

Sage

sage: Shifted = GrowthDiagram.rules.ShiftedShapes()
sage: Shifted.vertices(3)
Partitions of the integer 3 satisfying constraints max_slope=-1

Python

>>> from sage.all import *
>>> Shifted = GrowthDiagram.rules.ShiftedShapes()
>>> Shifted.vertices(Integer(3))
Partitions of the integer 3 satisfying constraints max_slope=-1

zero = []

class sage.combinat.growth.RuleSylvester

Bases: Rule

A rule modelling a Schensted-like correspondence for binary trees.

EXAMPLES:

Sage

sage: Sylvester = GrowthDiagram.rules.Sylvester()
sage: GrowthDiagram(Sylvester, [3,1,2])
0  1  0
0  0  1
1  0  0

Python

>>> from sage.all import *
>>> Sylvester = GrowthDiagram.rules.Sylvester()
>>> GrowthDiagram(Sylvester, [Integer(3),Integer(1),Integer(2)])
0  1  0
0  0  1
1  0  0

The vertices of the dual graded graph are BinaryTrees:

Sage

sage: Sylvester.vertices(3)
Binary trees of size 3

Python

>>> from sage.all import *
>>> Sylvester.vertices(Integer(3))
Binary trees of size 3

The P_graph() is also known as the bracket tree, the Q_graph() is the lattice of finite order ideals of the infinite binary tree, see Example 2.4.6 in [Fom1994].

For a permutation, the P_symbol() is the binary search tree, the Q_symbol() is the increasing tree corresponding to the inverse permutation. Note that, instead of passing the rule to GrowthDiagram, we can also call the rule to create growth diagrams. From [Nze2007]:

Sage

sage: pi = Permutation([3,5,1,4,2,6]); G = Sylvester(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.P_symbol())
  __3__
 /     \
1       5
 \     / \
  2   4   6
sage: ascii_art(G.Q_symbol())
  __1__
 /     \
3       2
 \     / \
  5   4   6

sage: all(Sylvester(pi).P_symbol() == pi.binary_search_tree()
....:     for pi in Permutations(5))
True

sage: all(Sylvester(pi).Q_symbol() == pi.inverse().increasing_tree()
....:     for pi in Permutations(5))
True

Python

>>> from sage.all import *
>>> pi = Permutation([Integer(3),Integer(5),Integer(1),Integer(4),Integer(2),Integer(6)]); G = Sylvester(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
>>> ascii_art(G.P_symbol())
  __3__
 /     \
1       5
 \     / \
  2   4   6
>>> ascii_art(G.Q_symbol())
  __1__
 /     \
3       2
 \     / \
  5   4   6

>>> all(Sylvester(pi).P_symbol() == pi.binary_search_tree()
...     for pi in Permutations(Integer(5)))
True

>>> all(Sylvester(pi).Q_symbol() == pi.inverse().increasing_tree()
...     for pi in Permutations(Integer(5)))
True

P_symbol(P_chain)

Return the labels along the vertical boundary of a rectangular growth diagram as a labelled binary tree.

For permutations, this coincides with the binary search tree.

EXAMPLES:

Sage

sage: Sylvester = GrowthDiagram.rules.Sylvester()
sage: pi = Permutation([2,4,3,1])
sage: ascii_art(Sylvester(pi).P_symbol())
  _2_
 /   \
1     4
     /
    3
sage: Sylvester(pi).P_symbol() == pi.binary_search_tree()
True

Python

>>> from sage.all import *
>>> Sylvester = GrowthDiagram.rules.Sylvester()
>>> pi = Permutation([Integer(2),Integer(4),Integer(3),Integer(1)])
>>> ascii_art(Sylvester(pi).P_symbol())
  _2_
 /   \
1     4
     /
    3
>>> Sylvester(pi).P_symbol() == pi.binary_search_tree()
True

We can also do the skew version:

Sage

sage: B = BinaryTree; E = B(); N = B([])
sage: ascii_art(Sylvester([3,2], shape=[3,3,3], labels=[N,N,N,E,E,E,N]).P_symbol())
  __1___
 /      \
None     3
        /
       2

Python

>>> from sage.all import *
>>> B = BinaryTree; E = B(); N = B([])
>>> ascii_art(Sylvester([Integer(3),Integer(2)], shape=[Integer(3),Integer(3),Integer(3)], labels=[N,N,N,E,E,E,N]).P_symbol())
  __1___
 /      \
None     3
        /
       2

Q_symbol(Q_chain)

Return the labels along the vertical boundary of a rectangular growth diagram as a labelled binary tree.

For permutations, this coincides with the increasing tree.

EXAMPLES:

Sage

sage: Sylvester = GrowthDiagram.rules.Sylvester()
sage: pi = Permutation([2,4,3,1])
sage: ascii_art(Sylvester(pi).Q_symbol())
  _1_
 /   \
4     2
     /
    3
sage: Sylvester(pi).Q_symbol() == pi.inverse().increasing_tree()
True

Python

>>> from sage.all import *
>>> Sylvester = GrowthDiagram.rules.Sylvester()
>>> pi = Permutation([Integer(2),Integer(4),Integer(3),Integer(1)])
>>> ascii_art(Sylvester(pi).Q_symbol())
  _1_
 /   \
4     2
     /
    3
>>> Sylvester(pi).Q_symbol() == pi.inverse().increasing_tree()
True

We can also do the skew version:

Sage

sage: B = BinaryTree; E = B(); N = B([])
sage: ascii_art(Sylvester([3,2], shape=[3,3,3], labels=[N,N,N,E,E,E,N]).Q_symbol())
  _None_
 /      \
3        1
        /
       2

Python

>>> from sage.all import *
>>> B = BinaryTree; E = B(); N = B([])
>>> ascii_art(Sylvester([Integer(3),Integer(2)], shape=[Integer(3),Integer(3),Integer(3)], labels=[N,N,N,E,E,E,N]).Q_symbol())
  _None_
 /      \
3        1
        /
       2

backward_rule(y, z, x)

Return the output shape given three shapes and the content.

See [Nze2007], page 9.

INPUT:

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

    x
  y z
  

OUTPUT:

A pair (t, content) consisting of the shape of the fourth binary tree t and the content of the cell.

EXAMPLES:

Sage

sage: Sylvester = GrowthDiagram.rules.Sylvester()
sage: B = BinaryTree; E = B(); N = B([]); L = B([[],None])
sage: R = B([None,[]]); T = B([[],[]])

sage: ascii_art(Sylvester.backward_rule(E, E, E))
( , 0 )
sage: ascii_art(Sylvester.backward_rule(N, N, N))
( o, 0 )

Python

>>> from sage.all import *
>>> Sylvester = GrowthDiagram.rules.Sylvester()
>>> B = BinaryTree; E = B(); N = B([]); L = B([[],None])
>>> R = B([None,[]]); T = B([[],[]])

>>> ascii_art(Sylvester.backward_rule(E, E, E))
( , 0 )
>>> ascii_art(Sylvester.backward_rule(N, N, N))
( o, 0 )

forward_rule(y, t, x, 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 x
  y
  

• content – \(0\) or \(1\); the content of the cell

OUTPUT: the fourth binary tree z

EXAMPLES:

Sage

sage: Sylvester = GrowthDiagram.rules.Sylvester()
sage: B = BinaryTree; E = B(); N = B([]); L = B([[],None])
sage: R = B([None,[]]); T = B([[],[]])

sage: ascii_art(Sylvester.forward_rule(E, E, E, 1))
o
sage: ascii_art(Sylvester.forward_rule(N, N, N, 1))
o
 \
  o
sage: ascii_art(Sylvester.forward_rule(L, L, L, 1))
  o
 / \
o   o
sage: ascii_art(Sylvester.forward_rule(R, R, R, 1))
o
 \
  o
   \
    o

Python

>>> from sage.all import *
>>> Sylvester = GrowthDiagram.rules.Sylvester()
>>> B = BinaryTree; E = B(); N = B([]); L = B([[],None])
>>> R = B([None,[]]); T = B([[],[]])

>>> ascii_art(Sylvester.forward_rule(E, E, E, Integer(1)))
o
>>> ascii_art(Sylvester.forward_rule(N, N, N, Integer(1)))
o
 \
  o
>>> ascii_art(Sylvester.forward_rule(L, L, L, Integer(1)))
  o
 / \
o   o
>>> ascii_art(Sylvester.forward_rule(R, R, R, Integer(1)))
o
 \
  o
   \
    o

If y != x, obtain z from y adding a node such that deleting the right most gives x:

Sage

sage: ascii_art(Sylvester.forward_rule(R, N, L, 0))
  o
 / \
o   o

sage: ascii_art(Sylvester.forward_rule(L, N, R, 0))
  o
 /
o
 \
  o

Python

>>> from sage.all import *
>>> ascii_art(Sylvester.forward_rule(R, N, L, Integer(0)))
  o
 / \
o   o

>>> ascii_art(Sylvester.forward_rule(L, N, R, Integer(0)))
  o
 /
o
 \
  o

If y == x != t, obtain z from x by adding a node as left child to the right most node:

Sage

sage: ascii_art(Sylvester.forward_rule(N, E, N, 0))
  o
 /
o
sage: ascii_art(Sylvester.forward_rule(T, L, T, 0))
  _o_
 /   \
o     o
     /
    o
sage: ascii_art(Sylvester.forward_rule(L, N, L, 0))
    o
   /
  o
 /
o
sage: ascii_art(Sylvester.forward_rule(R, N, R, 0))
o
 \
  o
 /
o

Python

>>> from sage.all import *
>>> ascii_art(Sylvester.forward_rule(N, E, N, Integer(0)))
  o
 /
o
>>> ascii_art(Sylvester.forward_rule(T, L, T, Integer(0)))
  _o_
 /   \
o     o
     /
    o
>>> ascii_art(Sylvester.forward_rule(L, N, L, Integer(0)))
    o
   /
  o
 /
o
>>> ascii_art(Sylvester.forward_rule(R, N, R, Integer(0)))
o
 \
  o
 /
o

is_P_edge(v, w)

Return whether (v, w) is a \(P\)-edge of self.

(v, w) is an edge if v is obtained from w by deleting its right-most node.

EXAMPLES:

Sage

sage: Sylvester = GrowthDiagram.rules.Sylvester()
sage: v = Sylvester.vertices(2)[1]; ascii_art(v)
  o
 /
o

sage: ascii_art([w for w in Sylvester.vertices(3) if Sylvester.is_P_edge(v, w)])
[   o  ,     o ]
[  / \      /  ]
[ o   o    o   ]
[         /    ]
[        o     ]

sage: [w for w in Sylvester.vertices(4) if Sylvester.is_P_edge(v, w)]
[]

Python

>>> from sage.all import *
>>> Sylvester = GrowthDiagram.rules.Sylvester()
>>> v = Sylvester.vertices(Integer(2))[Integer(1)]; ascii_art(v)
  o
 /
o

>>> ascii_art([w for w in Sylvester.vertices(Integer(3)) if Sylvester.is_P_edge(v, w)])
[   o  ,     o ]
[  / \      /  ]
[ o   o    o   ]
[         /    ]
[        o     ]

>>> [w for w in Sylvester.vertices(Integer(4)) if Sylvester.is_P_edge(v, w)]
[]

is_Q_edge(v, w)

Return whether (v, w) is a \(Q\)-edge of self.

(v, w) is an edge if v is a sub-tree of w with one node less.

EXAMPLES:

Sage

sage: Sylvester = GrowthDiagram.rules.Sylvester()
sage: v = Sylvester.vertices(2)[1]; ascii_art(v)
  o
 /
o
sage: ascii_art([w for w in Sylvester.vertices(3) if Sylvester.is_Q_edge(v, w)])
[   o  ,   o,     o ]
[  / \    /      /  ]
[ o   o  o      o   ]
[         \    /    ]
[          o  o     ]
sage: [w for w in Sylvester.vertices(4) if Sylvester.is_Q_edge(v, w)]
[]

Python

>>> from sage.all import *
>>> Sylvester = GrowthDiagram.rules.Sylvester()
>>> v = Sylvester.vertices(Integer(2))[Integer(1)]; ascii_art(v)
  o
 /
o
>>> ascii_art([w for w in Sylvester.vertices(Integer(3)) if Sylvester.is_Q_edge(v, w)])
[   o  ,   o,     o ]
[  / \    /      /  ]
[ o   o  o      o   ]
[         \    /    ]
[          o  o     ]
>>> [w for w in Sylvester.vertices(Integer(4)) if Sylvester.is_Q_edge(v, w)]
[]

normalize_vertex(v)

Return v as a binary tree.

EXAMPLES:

Sage

sage: Sylvester = GrowthDiagram.rules.Sylvester()
sage: Sylvester.normalize_vertex([[],[]]).parent()
Binary trees

Python

>>> from sage.all import *
>>> Sylvester = GrowthDiagram.rules.Sylvester()
>>> Sylvester.normalize_vertex([[],[]]).parent()
Binary trees

rank(v)

Return the rank of v: the number of nodes of the tree.

EXAMPLES:

Sage

sage: Sylvester = GrowthDiagram.rules.Sylvester()
sage: Sylvester.rank(Sylvester.vertices(3)[0])
3

Python

>>> from sage.all import *
>>> Sylvester = GrowthDiagram.rules.Sylvester()
>>> Sylvester.rank(Sylvester.vertices(Integer(3))[Integer(0)])
3

vertices(n)

Return the vertices of the dual graded graph on level n.

EXAMPLES:

Sage

sage: Sylvester = GrowthDiagram.rules.Sylvester()
sage: Sylvester.vertices(3)
Binary trees of size 3

Python

>>> from sage.all import *
>>> Sylvester = GrowthDiagram.rules.Sylvester()
>>> Sylvester.vertices(Integer(3))
Binary trees of size 3

zero = .

class sage.combinat.growth.RuleYoungFibonacci

Bases: Rule

A rule modelling a Schensted-like correspondence for Young-Fibonacci-tableaux.

EXAMPLES:

Sage

sage: YF = GrowthDiagram.rules.YoungFibonacci()
sage: GrowthDiagram(YF, [3,1,2])
0  1  0
0  0  1
1  0  0

Python

>>> from sage.all import *
>>> YF = GrowthDiagram.rules.YoungFibonacci()
>>> GrowthDiagram(YF, [Integer(3),Integer(1),Integer(2)])
0  1  0
0  0  1
1  0  0

The vertices of the dual graded graph are Fibonacci words - compositions into parts of size at most two:

Sage

sage: YF.vertices(4)
[word: 22, word: 211, word: 121, word: 112, word: 1111]

Python

>>> from sage.all import *
>>> YF.vertices(Integer(4))
[word: 22, word: 211, word: 121, word: 112, word: 1111]

Note that, instead of passing the rule to GrowthDiagram, we can also use call the rule to create growth diagrams. For example:

Sage

sage: G = YF([2, 3, 7, 4, 1, 6, 5]); G
0  0  0  0  1  0  0
1  0  0  0  0  0  0
0  1  0  0  0  0  0
0  0  0  1  0  0  0
0  0  0  0  0  0  1
0  0  0  0  0  1  0
0  0  1  0  0  0  0

Python

>>> from sage.all import *
>>> G = YF([Integer(2), Integer(3), Integer(7), Integer(4), Integer(1), Integer(6), Integer(5)]); G
0  0  0  0  1  0  0
1  0  0  0  0  0  0
0  1  0  0  0  0  0
0  0  0  1  0  0  0
0  0  0  0  0  0  1
0  0  0  0  0  1  0
0  0  1  0  0  0  0

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:

Sage

sage: G.P_chain()[-1]
word: 21211

Python

>>> from sage.all import *
>>> G.P_chain()[-Integer(1)]
word: 21211

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.

forward_rule(y, t, x, content)

Return the output shape given three shapes and the content.

See [Fom1995] Lemma 4.4.1, page 35.

INPUT:

• y, t, x – three Fibonacci 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 Fibonacci word

EXAMPLES:

Sage

sage: YF = GrowthDiagram.rules.YoungFibonacci()

sage: YF.forward_rule([], [], [], 1)
word: 1

sage: YF.forward_rule([1], [1], [1], 1)
word: 11

sage: YF.forward_rule([1,2], [1], [1,1], 0)
word: 21

sage: YF.forward_rule([1,1], [1], [1,1], 0)
word: 21

Python

>>> from sage.all import *
>>> YF = GrowthDiagram.rules.YoungFibonacci()

>>> YF.forward_rule([], [], [], Integer(1))
word: 1

>>> YF.forward_rule([Integer(1)], [Integer(1)], [Integer(1)], Integer(1))
word: 11

>>> YF.forward_rule([Integer(1),Integer(2)], [Integer(1)], [Integer(1),Integer(1)], Integer(0))
word: 21

>>> YF.forward_rule([Integer(1),Integer(1)], [Integer(1)], [Integer(1),Integer(1)], Integer(0))
word: 21

is_P_edge(v, w)

Return whether (v, w) is a \(P\)-edge of self.

(v, w) is an edge if v is obtained from w by deleting a 1 or replacing the left-most 2 by a 1.

EXAMPLES:

Sage

sage: YF = GrowthDiagram.rules.YoungFibonacci()
sage: v = YF.vertices(5)[5]; v
word: 1121
sage: [w for w in YF.vertices(6) if YF.is_P_edge(v, w)]
[word: 2121, word: 11121]
sage: [w for w in YF.vertices(7) if YF.is_P_edge(v, w)]
[]

Python

>>> from sage.all import *
>>> YF = GrowthDiagram.rules.YoungFibonacci()
>>> v = YF.vertices(Integer(5))[Integer(5)]; v
word: 1121
>>> [w for w in YF.vertices(Integer(6)) if YF.is_P_edge(v, w)]
[word: 2121, word: 11121]
>>> [w for w in YF.vertices(Integer(7)) if YF.is_P_edge(v, w)]
[]

is_Q_edge(v, w)

Return whether (v, w) is a \(P\)-edge of self.

(v, w) is an edge if v is obtained from w by deleting a 1 or replacing the left-most 2 by a 1.

EXAMPLES:

Sage

sage: YF = GrowthDiagram.rules.YoungFibonacci()
sage: v = YF.vertices(5)[5]; v
word: 1121
sage: [w for w in YF.vertices(6) if YF.is_P_edge(v, w)]
[word: 2121, word: 11121]
sage: [w for w in YF.vertices(7) if YF.is_P_edge(v, w)]
[]

Python

>>> from sage.all import *
>>> YF = GrowthDiagram.rules.YoungFibonacci()
>>> v = YF.vertices(Integer(5))[Integer(5)]; v
word: 1121
>>> [w for w in YF.vertices(Integer(6)) if YF.is_P_edge(v, w)]
[word: 2121, word: 11121]
>>> [w for w in YF.vertices(Integer(7)) if YF.is_P_edge(v, w)]
[]

normalize_vertex(v)

Return v as a word with letters 1 and 2.

EXAMPLES:

Sage

sage: YF = GrowthDiagram.rules.YoungFibonacci()
sage: YF.normalize_vertex([1,2,1]).parent()
Finite words over {1, 2}

Python

>>> from sage.all import *
>>> YF = GrowthDiagram.rules.YoungFibonacci()
>>> YF.normalize_vertex([Integer(1),Integer(2),Integer(1)]).parent()
Finite words over {1, 2}

rank(v)

Return the rank of v: the size of the corresponding composition.

EXAMPLES:

Sage

sage: YF = GrowthDiagram.rules.YoungFibonacci()
sage: YF.rank(YF.vertices(3)[0])
3

Python

>>> from sage.all import *
>>> YF = GrowthDiagram.rules.YoungFibonacci()
>>> YF.rank(YF.vertices(Integer(3))[Integer(0)])
3

vertices(n)

Return the vertices of the dual graded graph on level n.

EXAMPLES:

Sage

sage: YF = GrowthDiagram.rules.YoungFibonacci()
sage: YF.vertices(3)
[word: 21, word: 12, word: 111]

Python

>>> from sage.all import *
>>> YF = GrowthDiagram.rules.YoungFibonacci()
>>> YF.vertices(Integer(3))
[word: 21, word: 12, word: 111]

zero = word:

class sage.combinat.growth.Rules

Bases: object

Catalog of rules for growth diagrams.

BinaryWord

alias of RuleBinaryWord

Burge

alias of RuleBurge

Domino

alias of RuleDomino

LLMS

alias of RuleLLMS

RSK

alias of RuleRSK

ShiftedShapes

alias of RuleShiftedShapes

Sylvester

alias of RuleSylvester

YoungFibonacci

alias of RuleYoungFibonacci