Growth diagrams and dual graded graphs¶
AUTHORS:
 Martin Rubey (201609): Initial version
 Martin Rubey (201709): generalize, more rules, improve documentation
 Travis Scrimshaw (201709): switch to rulebased framework
Todo
 provide examples for the P and Qsymbol 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
andRuleBurge
 implement backward rules for
GrowthDiagramDomino
 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 RobinsonSchenstedKnuth (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 socalled local rules: a ‘forward’ rule, whose input are three vertices \(y\), \(t\) and \(x\) of a certain directed graph (in the case of RobinsonSchensted: the directed graph corresponding to Young’s lattice) and an integer (in the case of RobinsonSchensted: \(0\) or \(1\)), and whose output is a fourth vertex \(z\). This rule should be invertible in the following sense: there is a socalled ‘backward’ rule that recovers the integer and \(t\) given \(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: 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
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 topleft 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: 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 socalled
P_symbol()
, the partitions
along the bottom boundary yield the socalled
Q_symbol()
. These
coincide with the output of the classical
RSK()
insertion algorithm:
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 ]
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: 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 \(01\)fillings of
arbitrary skew shapes. In the case of the RobinsonSchenstedKnuth
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: P = {(11,41): 1, (21,21): 1, (21,31): 2, (41,21): 1, (41,31): 1}
Note that we are subtracting \(1\) from all entries because of zerobased indexing, we obtain:
sage: 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: 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: GrowthDiagram(RuleRSK, [3,1,2], shape=SkewPartition([[3,3,2],[1,1]]))
. 1 0
. 0 1
1 0
As an important example, consider the StanleySundaram correspondence between oscillating tableaux and (partial) perfect matchings. Perfect matchings of \(\{1, \ldots, 2r\}\) are in bijection with \(01\)fillings of a triangular shape with \(2r1\) rows, such that for each \(k\) there is either exactly one nonzero entry in row \(k\) or exactly one nonzero entry in column \(2rk\). Explicitly, if \((i,j)\) is a pair in the perfect matching, the entry in column \(i1\) and row \(2rj\) equals \(1\). For example:
sage: m = [[1,5],[3,4],[2,7],[6,8]]
sage: G = RuleRSK({(i1, 8j): 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
The partitions labelling the bottomright corners along the boundary opposite of the origin then form a socalled oscillating tableau  the remaining partitions along the bottomright boundary are redundant:
sage: G.out_labels()[1::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: w = {(11,41): 1, (21,21): 1, (41,31): 1}
sage: T = SkewTableau([[None, None], [None, 5], [1]])
sage: U = SkewTableau([[None, None], [None, 3], [5]])
sage: 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 ]
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: 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]]
From this, we have to construct the list of labels of the corners along the bottomright 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: l = [o[i//2] if is_even(i) else min(o[(i1)//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
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: ascii_art(SkewTableau(chain=G.in_labels()[len(o)2:]),
....: SkewTableau(chain=G.in_labels()[len(o)2::1]))
. 1 . 7
5 4
Rules currently available¶
As mentioned at the beginning, the RobinsonSchenstedKnuth 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 YoungFibonacci 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 socalled 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
RobinsonSchenstedKnuth 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: 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: 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)
We can now compute the filling corresponding to a sequence of labels as follows:
sage: GrowthDiagram(RulePascal(), labels=[0,1,2,1,2,1,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: GrowthDiagram(RulePascal(), [3,1,2])
Traceback (most recent call last):
...
AttributeError: 'RulePascal' object has no attribute 'forward_rule'
We now reimplement the rule where we provide the dual graded graphs:
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
Are they really dual?
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]
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: 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 []
We verify these are \(1\) dual at level \(5\):
sage: RulePascal()._check_duality(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: 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, x1, g1, 0)
The labels are now alternating between vertices and edgecolors:
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

class
sage.combinat.growth.
GrowthDiagram
(rule, filling=None, shape=None, labels=None)¶ Bases:
sage.structure.sage_object.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 RobinsonSchenstedKnuth (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 socalled ‘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
– RSKRuleBurge
– a variation of RSK originally due to BurgeRuleBinaryWord
– a correspondence producing binary words originally due to ViennotRuleDomino
– a correspondence producing domino tableaux originally due to Barbasch and VoganRuleShiftedShapes
– a correspondence for shifted shapes, where the original insertion algorithm is due to Sagan and Worley, and Haiman.RuleSylvester
– the Sylvester correspondence, producing binary treesRuleYoungFibonacci
– the YoungFibonacci correspondenceRuleLLMS
– LLMS insertion
INPUT:
rule
–Rule
; the growth diagram rulefilling
– (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 permutationsshape
– (optional) a (possibly skew) partitionlabels
– (optional) a list that specifies a path whose length in the halfperimeter of the shape; more details given below
If
filling
is not given, then the growth diagram is determined by applying the backward rule tolabels
decorating the boundary opposite of the origin of theshape
. In this case,labels
are interpreted as labelling the boundary opposite of the origin.Otherwise,
shape
is inferred fromfilling
orlabels
if possible andlabels
is set torule.zero
if not specified. Here,labels
are labelling the boundary on the side of the origin.For
labels
, ifrule.has_multiple_edges
isTrue
, then the elements should be of the form \((v_1, e_1, \ldots, e_{n1}, v_n)\), where \(n\) is the halfperimeter ofshape
, and \((v_{i1}, 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: 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], []]
Passing the permutation matrix instead gives the same result:
sage: G = GrowthDiagram(RuleRSK, pi.to_matrix()) sage: ascii_art([G.P_symbol(), G.Q_symbol()]) [ 1 2 3 1 3 4 ] [ 4 , 2 ]
We give the same example but using a skew shape:
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], []]
We construct a growth diagram using the backwards RSK rule by specifying the labels:
sage: 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: 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]
Check that trac ticket #25631 is fixed:
sage: BinaryWord = GrowthDiagram.rules.BinaryWord() sage: 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: 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 ]

Q_chain
()¶ Return the labels along the horizontal boundary of a rectangular growth diagram.
EXAMPLES:
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]
Check that trac ticket #25631 is fixed:
sage: BinaryWord = GrowthDiagram.rules.BinaryWord() sage: 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: 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 ]

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

filling
()¶ Return the filling of the diagram as a dictionary.
EXAMPLES:
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}

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

is_rectangular
()¶ Return
True
if the shape of the growth diagram is rectangular.EXAMPLES:
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

out_labels
()¶ Return the labels along the boundary opposite of the origin.
EXAMPLES:
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], []]

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 torule.zero
.For RSKgrowth diagrams and rectangular fillings, this corresponds to evacuation of the \(P\) and the \(Q\)symbol.
EXAMPLES:
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 ]

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: RuleRSK = GrowthDiagram.rules.RSK() sage: GrowthDiagram(RuleRSK, [1]).shape() [1] / []

to_biword
()¶ Return the filling as a biword, if the shape is rectangular.
EXAMPLES:
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]]]

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

sage.combinat.growth.
GrowthDiagramBinWord
(filling=None, shape=None, labels=None)¶ GrowthDiagramBinWord
is deprecated; useGrowthDiagram.rules.BinaryWord
instead.EXAMPLES:
sage: GrowthDiagram.rules.BinaryWord()([4,1,3,2]).P_chain() [word: , word: 1, word: 11, word: 110, word: 1010]

sage.combinat.growth.
GrowthDiagramBurge
(filling=None, shape=None, labels=None)¶ GrowthDiagramBurge
is deprecated; useGrowthDiagram.rules.Burge
instead.EXAMPLES:
sage: GrowthDiagram.rules.Burge()([4,1,3,1,2]).P_symbol() [[1, 2], [1, 3], [4]]

sage.combinat.growth.
GrowthDiagramDomino
(filling=None, shape=None, labels=None)¶ GrowthDiagramDomino
is deprecated; useGrowthDiagram.rules.Domino
instead.EXAMPLES:
sage: GrowthDiagram.rules.Domino()([4,1,3,2]).P_symbol() [[1, 1, 2, 2], [3, 3], [4, 4]]

sage.combinat.growth.
GrowthDiagramRSK
(filling=None, shape=None, labels=None)¶ GrowthDiagramRSK
is deprecated; useGrowthDiagram.rules.RSK
instead.EXAMPLES:
sage: GrowthDiagram.rules.RSK()([4,1,3,1,2]).P_symbol() [[1, 1, 2], [3], [4]]

sage.combinat.growth.
GrowthDiagramSylvester
(filling=None, shape=None, labels=None)¶ GrowthDiagramSylvester
is deprecated; useGrowthDiagram.rules.Sylvester
instead.EXAMPLES:
sage: GrowthDiagram.rules.Sylvester()([4,1,3,2]).P_chain() [., [., .], [., [., .]], [., [[., .], .]], [[., [[., .], .]], .]]

sage.combinat.growth.
GrowthDiagramYoungFibonacci
(filling=None, shape=None, labels=None)¶ GrowthDiagramYoungFibonacci
is deprecated; useGrowthDiagram.rules.YoungFibonacci
instead.EXAMPLES:
sage: GrowthDiagram.rules.YoungFibonacci()([4,1,3,2]).P_chain() [word: , word: 1, word: 11, word: 21, word: 211]

class
sage.combinat.growth.
Rule
¶ Bases:
sage.structure.unique_representation.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 graphsr
– (default: 1) the parameter in the equation \(DU  UD = rI\)has_multiple_edges
– (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)
ifhas_multiple_edges
isTrue
.(y, e, t)
is an edge in the graph \(P\),(t, f, x)
an edge in the graphQ
. It should return the fourth vertexz
, or, ifhas_multiple_edges
isTrue
, the path(g, z, h)
fromy
tox
.backward_rule
– a function with input(y, z, x)
or(y, g, z, h, x)
ifhas_multiple_edges
isTrue
.(y, g, z)
is an edge in the graph \(Q\),(z, h, x)
an edge in the graphP
. It should return the fourth vertex and the content(t, content)
, or, ifhas_multiple_edges
isTrue
, the path fromy
tox
and the content as(e, t, f, content)
.is_P_edge
,is_Q_edge
– functions that take two vertices as arguments and returnTrue
orFalse
, 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 thatMyRule
is such a subclass. Then:GrowthDiagram(MyRule, my_filling)
requires only an implementation offorward_rule
,zero
and possiblyhas_multiple_edges
.GrowthDiagram(MyRule, labels=my_labels, shape=my_shape)
requires only an implementation ofbackward_rule
and possiblyhas_multiple_edges
, provided that the labelsmy_labels
are given as needed bybackward_rule
.GrowthDiagram(MyRule, labels=my_labels)
additionally needs an implementation ofrank
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 ofvertices
,is_P_edge
and possiblyhas_multiple_edges
is required, mutatis mutandis forMyRule.Q_graph
.MyRule._check_duality
requiresP_graph
andQ_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 nondegenerate edges in the vertical direction come from this graph.
EXAMPLES:
sage: Domino = GrowthDiagram.rules.Domino() sage: Domino.P_graph(3) Finite poset containing 8 elements

Q_graph
(n)¶ Return the first
n
levels of the second dual graded graph.The nondegenerate edges in the horizontal direction come from this graph.
EXAMPLES:
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]]

normalize_vertex
(v)¶ Return
v
as a vertex of the dual graded graph.This is a default implementation, returning its argument.
EXAMPLES:
sage: from sage.combinat.growth import Rule sage: Rule().normalize_vertex("hello") is "hello" True

class
sage.combinat.growth.
RuleBinaryWord
¶ Bases:
sage.combinat.growth.Rule
A rule modelling a Schenstedlike correspondence for binary words.
EXAMPLES:
sage: BinaryWord = GrowthDiagram.rules.BinaryWord() sage: GrowthDiagram(BinaryWord, [3,1,2]) 0 1 0 0 0 1 1 0 0
The vertices of the dual graded graph are binary words:
sage: BinaryWord.vertices(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: 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]
The Kleitman Greene invariant is the descent word, encoded by the positions of the zeros:
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]

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: BinaryWord = GrowthDiagram.rules.BinaryWord() sage: BinaryWord.forward_rule([], [], [], 1) word: 1 sage: BinaryWord.forward_rule([1], [1], [1], 1) word: 11
if
x != y
append last letter ofx
toy
:sage: BinaryWord.forward_rule([1,0], [1], [1,1], 0) word: 101
if
x == y != t
append0
toy
:sage: BinaryWord.forward_rule([1,1], [1], [1,1], 0) word: 110

is_P_edge
(v, w)¶ Return whether
(v, w)
is a \(P\)edge ofself
.(v, w)
is an edge ifv
is obtained fromw
by deleting a letter.EXAMPLES:
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)] []

is_Q_edge
(v, w)¶ Return whether
(v, w)
is a \(Q\)edge ofself
.(w, v)
is an edge ifw
is obtained fromv
by appending a letter.EXAMPLES:
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)] []

normalize_vertex
(v)¶ Return
v
as a binary word.EXAMPLES:
sage: BinaryWord = GrowthDiagram.rules.BinaryWord() sage: BinaryWord.normalize_vertex([0,1]).parent() Finite words over {0, 1}

rank
(v)¶ Return the rank of
v
: number of letters of the word.EXAMPLES:
sage: BinaryWord = GrowthDiagram.rules.BinaryWord() sage: BinaryWord.rank(BinaryWord.vertices(3)[0]) 3

vertices
(n)¶ Return the vertices of the dual graded graph on level
n
.EXAMPLES:
sage: BinaryWord = GrowthDiagram.rules.BinaryWord() sage: BinaryWord.vertices(3) [word: 100, word: 101, word: 110, word: 111]


class
sage.combinat.growth.
RuleBurge
¶ Bases:
sage.combinat.growth.RulePartitions
A rule modelling Burge insertion.
EXAMPLES:
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
The vertices of the dual graded graph are integer partitions:
sage: Burge.vertices(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 theQ_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: 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 ]
For rectangular fillings, the KleitmanGreene 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: Burge = GrowthDiagram.rules.Burge() sage: Burge.backward_rule([1,1,1],[2,1,1,1],[2,1,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
– a nonnegative integer; the content of the cell
OUTPUT:
The fourth partition according to the Burge correspondence.
EXAMPLES:
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]


class
sage.combinat.growth.
RuleDomino
¶ Bases:
sage.combinat.growth.Rule
A rule modelling domino insertion.
EXAMPLES:
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
The vertices of the dual graded graph are integer partitions whose Ferrers diagram can be tiled with dominoes:
sage: Domino.vertices(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: 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 ]
The spin of a domino tableau is half the number of vertical dominoes:
sage: def spin(T): ....: return sum(2*len(set(row))  len(row) for row in T)/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: 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
Negating all signs transposes all the partitions:
sage: 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: 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

Q_symbol
(P_chain)¶ Return the labels along the vertical boundary of a rectangular growth diagram as a (skew) domino tableau.
EXAMPLES:
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

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: Domino = GrowthDiagram.rules.Domino()
Rule 1:
sage: Domino.forward_rule([], [], [], 1) [2] sage: Domino.forward_rule([1,1], [1,1], [1,1], 1) [3, 1]
Rule 2:
sage: Domino.forward_rule([1,1], [1,1], [1,1], 1) [1, 1, 1, 1]
Rule 3:
sage: Domino.forward_rule([1,1], [1,1], [2,2], 0) [2, 2]
Rule 4:
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]

is_P_edge
(v, w)¶ Return whether
(v, w)
is a \(P\)edge ofself
.(v, w)
is an edge ifv
is obtained fromw
by deleting a domino.EXAMPLES:
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)] []

is_Q_edge
(v, w)¶ Return whether
(v, w)
is a \(P\)edge ofself
.(v, w)
is an edge ifv
is obtained fromw
by deleting a domino.EXAMPLES:
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)] []

normalize_vertex
(v)¶ Return
v
as a partition.EXAMPLES:
sage: Domino = GrowthDiagram.rules.Domino() sage: Domino.normalize_vertex([3,1]).parent() Partitions

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: Domino = GrowthDiagram.rules.Domino() sage: Domino.rank(Domino.vertices(3)[0]) 3

vertices
(n)¶ Return the vertices of the dual graded graph on level
n
.EXAMPLES:
sage: Domino = GrowthDiagram.rules.Domino() sage: Domino.vertices(2) [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

zero
= []¶


class
sage.combinat.growth.
RuleLLMS
(k)¶ Bases:
sage.combinat.growth.Rule
A rule modelling the Schensted correspondence for affine permutations.
EXAMPLES:
sage: LLMS3 = GrowthDiagram.rules.LLMS(3) sage: GrowthDiagram(LLMS3, [3,1,2]) 0 1 0 0 0 1 1 0 0
The vertices of the dual graded graph are
Cores
:sage: LLMS3.vertices(4) 3Cores 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: 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
The
P_symbol()
is aStrongTableau
:sage: G.P_symbol().pp() 1 2 3 5 3 5 4 6 5 6
The
Q_symbol()
is aWeakTableau
:sage: G.Q_symbol().pp() 1 3 4 5 2 5 3 6 5 6
Let us also check Example 6.2 in [LLMSSZ2013]:
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

P_symbol
(P_chain)¶ Return the labels along the vertical boundary of a rectangular growth diagram as a skew
StrongTableau
.EXAMPLES:
sage: LLMS4 = GrowthDiagram.rules.LLMS(4) sage: G = LLMS4([3,4,1,2]) sage: 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: LLMS4 = GrowthDiagram.rules.LLMS(4) sage: G = LLMS4([3,4,1,2]) sage: 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: 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)
if
x != y
: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)
if
x == y != t
: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)

is_P_edge
(v, w)¶ Return whether
(v, w)
is a \(P\)edge ofself
.For two kcores 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: 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

is_Q_edge
(v, w)¶ Return whether
(v, w)
is a \(Q\)edge ofself
.(v, w)
is an edge ifw
is a weak cover ofv
, seeweak_covers()
.EXAMPLES:
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

normalize_vertex
(v)¶ Convert
v
to a \(k\)core.EXAMPLES:
sage: LLMS3 = GrowthDiagram.rules.LLMS(3) sage: LLMS3.normalize_vertex([3,1]).parent() 3Cores of length 3

rank
(v)¶ Return the rank of
v
: the length of the core.EXAMPLES:
sage: LLMS3 = GrowthDiagram.rules.LLMS(3) sage: LLMS3.rank(LLMS3.vertices(3)[0]) 3

vertices
(n)¶ Return the vertices of the dual graded graph on level
n
.EXAMPLES:
sage: LLMS3 = GrowthDiagram.rules.LLMS(3) sage: LLMS3.vertices(2) 3Cores of length 2


class
sage.combinat.growth.
RulePartitions
¶ Bases:
sage.combinat.growth.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: RuleRSK = GrowthDiagram.rules.RSK() sage: G = RuleRSK([[0,1,0], [1,0,2]]) sage: 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: RuleRSK = GrowthDiagram.rules.RSK() sage: G = RuleRSK([[0,1,0], [1,0,2]]) sage: G.Q_symbol().pp() 1 3 3 2

normalize_vertex
(v)¶ Return
v
as a partition.EXAMPLES:
sage: RSK = GrowthDiagram.rules.RSK() sage: RSK.normalize_vertex([3,1]).parent() Partitions

rank
(v)¶ Return the rank of
v
: the size of the partition.EXAMPLES:
sage: RSK = GrowthDiagram.rules.RSK() sage: RSK.rank(RSK.vertices(3)[0]) 3

vertices
(n)¶ Return the vertices of the dual graded graph on level
n
.EXAMPLES:
sage: RSK = GrowthDiagram.rules.RSK() sage: RSK.vertices(3) Partitions of the integer 3

zero
= []¶


class
sage.combinat.growth.
RuleRSK
¶ Bases:
sage.combinat.growth.RulePartitions
A rule modelling RobinsonSchenstedKnuth insertion.
EXAMPLES:
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
The vertices of the dual graded graph are integer partitions:
sage: RuleRSK.vertices(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 theQ_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: 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 ]
For rectangular fillings, the KleitmanGreene invariant is the shape of the
P_symbol()
(or theQ_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 inRSK()
, we have to transpose matrices: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

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 RobinsonSchenstedKnuth 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
– a nonnegative integer; the content of the cell
OUTPUT:
The fourth partition according to the RobinsonSchenstedKnuth correspondence.
EXAMPLES:
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]


class
sage.combinat.growth.
RuleShiftedShapes
¶ Bases:
sage.combinat.growth.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: Shifted = GrowthDiagram.rules.ShiftedShapes() sage: GrowthDiagram(Shifted, [3,1,2]) 0 1 0 0 0 1 1 0 0
The vertices of the dual graded graph are shifted shapes:
sage: Shifted.vertices(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: 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]]

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: 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
Check the example just before Corollary 8.2 in [SS1990]:
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

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: 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'
Check the example just before Corollary 8.2 in [SS1990]:
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'

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 shapet
of the fourth word, the colours of the incident edges and the content of the cell according to Sagan  Worley insertion.EXAMPLES:
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)
if
x != y
: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)
if
x == y != t
: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)

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 SaganWorley insertion.EXAMPLES:
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)
if
x != y
: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)
if
x == y != t
: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)

is_P_edge
(v, w)¶ Return whether
(v, w)
is a \(P\)edge ofself
.(v, w)
is an edge ifw
containsv
.EXAMPLES:
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]]

is_Q_edge
(v, w)¶ Return whether
(v, w)
is a \(Q\)edge ofself
.(v, w)
is an edge ifw
is obtained fromv
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: 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

normalize_vertex
(v)¶ Return
v
as a partition.EXAMPLES:
sage: Shifted = GrowthDiagram.rules.ShiftedShapes() sage: Shifted.normalize_vertex([3,1]).parent() Partitions

rank
(v)¶ Return the rank of
v
: the size of the shifted partition.EXAMPLES:
sage: Shifted = GrowthDiagram.rules.ShiftedShapes() sage: Shifted.rank(Shifted.vertices(3)[0]) 3

vertices
(n)¶ Return the vertices of the dual graded graph on level
n
.EXAMPLES:
sage: Shifted = GrowthDiagram.rules.ShiftedShapes() sage: Shifted.vertices(3) Partitions of the integer 3 satisfying constraints max_slope=1

zero
= []¶


class
sage.combinat.growth.
RuleSylvester
¶ Bases:
sage.combinat.growth.Rule
A rule modelling a Schenstedlike correspondence for binary trees.
EXAMPLES:
sage: Sylvester = GrowthDiagram.rules.Sylvester() sage: GrowthDiagram(Sylvester, [3,1,2]) 0 1 0 0 0 1 1 0 0
The vertices of the dual graded graph are
BinaryTrees
:sage: Sylvester.vertices(3) Binary trees of size 3
The
P_graph()
is also known as the bracket tree, theQ_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, theQ_symbol()
is the increasing tree corresponding to the inverse permutation. Note that, instead of passing the rule toGrowthDiagram
, we can also call the rule to create growth diagrams. From [Nze2007]: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

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: 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
We can also do the skew version:
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

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: 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
We can also do the skew version:
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

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: 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 )

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: 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
If
y != x
, obtainz
fromy
adding a node such that deleting the right most givesx
: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
If
y == x != t
, obtainz
fromx
by adding a node as left child to the right most node: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

is_P_edge
(v, w)¶ Return whether
(v, w)
is a \(P\)edge ofself
.(v, w)
is an edge ifv
is obtained fromw
by deleting its rightmost node.EXAMPLES:
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)] []

is_Q_edge
(v, w)¶ Return whether
(v, w)
is a \(Q\)edge ofself
.(v, w)
is an edge ifv
is a subtree ofw
with one node less.EXAMPLES:
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)] []

normalize_vertex
(v)¶ Return
v
as a binary tree.EXAMPLES:
sage: Sylvester = GrowthDiagram.rules.Sylvester() sage: Sylvester.normalize_vertex([[],[]]).parent() Binary trees

rank
(v)¶ Return the rank of
v
: the number of nodes of the tree.EXAMPLES:
sage: Sylvester = GrowthDiagram.rules.Sylvester() sage: Sylvester.rank(Sylvester.vertices(3)[0]) 3

vertices
(n)¶ Return the vertices of the dual graded graph on level
n
.EXAMPLES:
sage: Sylvester = GrowthDiagram.rules.Sylvester() sage: Sylvester.vertices(3) Binary trees of size 3

zero
= .¶


class
sage.combinat.growth.
RuleYoungFibonacci
¶ Bases:
sage.combinat.growth.Rule
A rule modelling a Schenstedlike correspondence for YoungFibonaccitableaux.
EXAMPLES:
sage: YF = GrowthDiagram.rules.YoungFibonacci() sage: GrowthDiagram(YF, [3,1,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: YF.vertices(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: 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
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: G.P_chain()[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: 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

is_P_edge
(v, w)¶ Return whether
(v, w)
is a \(P\)edge ofself
.(v, w)
is an edge ifv
is obtained fromw
by deleting a1
or replacing the leftmost2
by a1
.EXAMPLES:
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)] []

is_Q_edge
(v, w)¶ Return whether
(v, w)
is a \(P\)edge ofself
.(v, w)
is an edge ifv
is obtained fromw
by deleting a1
or replacing the leftmost2
by a1
.EXAMPLES:
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)] []

normalize_vertex
(v)¶ Return
v
as a word with letters 1 and 2.EXAMPLES:
sage: YF = GrowthDiagram.rules.YoungFibonacci() sage: YF.normalize_vertex([1,2,1]).parent() Finite words over {1, 2}

rank
(v)¶ Return the rank of
v
: the size of the corresponding composition.EXAMPLES:
sage: YF = GrowthDiagram.rules.YoungFibonacci() sage: YF.rank(YF.vertices(3)[0]) 3

vertices
(n)¶ Return the vertices of the dual graded graph on level
n
.EXAMPLES:
sage: YF = GrowthDiagram.rules.YoungFibonacci() sage: YF.vertices(3) [word: 21, word: 12, word: 111]


class
sage.combinat.growth.
Rules
¶ Bases:
object
Catalog of rules for growth diagrams.

BinaryWord
¶ alias of
RuleBinaryWord

Domino
¶ alias of
RuleDomino

ShiftedShapes
¶ alias of
RuleShiftedShapes

Sylvester
¶ alias of
RuleSylvester

YoungFibonacci
¶ alias of
RuleYoungFibonacci
