Kleber Trees¶
A Kleber tree is a tree of weights generated by Kleber’s algorithm [Kleber1]. The nodes correspond to the weights in the positive Weyl chamber obtained by subtracting a (non-zero) positive root. The edges are labeled by the coefficients of the roots of the difference.
AUTHORS:
- Travis Scrimshaw (2011-05-03): Initial version
- Travis Scrimshaw (2013-02-13): Added support for virtual trees and improved output
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree
sage: KleberTree(['A', 3, 1], [[3,2], [2,1], [1,1], [1,1]])
Kleber tree of Cartan type ['A', 3, 1] and B = ((3, 2), (2, 1), (1, 1), (1, 1))
sage: KleberTree(['D', 4, 1], [[2,2]])
Kleber tree of Cartan type ['D', 4, 1] and B = ((2, 2),)
TESTS:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree
sage: KT = KleberTree(['A', 3, 1], [[3,2], [2,1], [1,1], [1,1]])
sage: for x in set(KT.list()): x
Kleber tree node with weight [1, 0, 3] and upwards edge root [1, 1, 0]
Kleber tree node with weight [0, 2, 2] and upwards edge root [1, 0, 0]
Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 0, 0]
Kleber tree node with weight [2, 0, 0] and upwards edge root [0, 1, 1]
Kleber tree node with weight [0, 0, 2] and upwards edge root [1, 1, 0]
Kleber tree node with weight [0, 1, 0] and upwards edge root [0, 0, 1]
Kleber tree node with weight [3, 0, 1] and upwards edge root [0, 1, 1]
Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 1, 1]
Kleber tree node with weight [1, 1, 1] and upwards edge root [1, 1, 1]
Kleber tree node with weight [0, 0, 2] and upwards edge root [2, 2, 1]
sage: KT = KleberTree(['A', 7, 1], [[3,2], [2,1], [1,1]])
sage: KT
Kleber tree of Cartan type ['A', 7, 1] and B = ((3, 2), (2, 1), (1, 1))
sage: for x in set(KT.list()): x
Kleber tree node with weight [1, 0, 1, 0, 1, 0, 0] and upwards edge root [1, 2, 2, 1, 0, 0, 0]
Kleber tree node with weight [0, 0, 1, 0, 0, 1, 0] and upwards edge root [2, 3, 3, 2, 1, 0, 0]
Kleber tree node with weight [1, 1, 2, 0, 0, 0, 0] and upwards edge root [0, 0, 0, 0, 0, 0, 0]
Kleber tree node with weight [2, 0, 1, 1, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]
Kleber tree node with weight [1, 0, 0, 2, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]
Kleber tree node with weight [0, 0, 3, 0, 0, 0, 0] and upwards edge root [1, 1, 0, 0, 0, 0, 0]
Kleber tree node with weight [0, 0, 0, 1, 1, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]
Kleber tree node with weight [0, 1, 1, 1, 0, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]
-
class
sage.combinat.rigged_configurations.kleber_tree.
KleberTree
(cartan_type, B, classical_ct)¶ Bases:
sage.structure.parent.Parent
,sage.structure.unique_representation.UniqueRepresentation
The tree that is generated by Kleber’s algorithm.
A Kleber tree is a tree of weights generated by Kleber’s algorithm [Kleber1]. It is used to generate the set of all admissible rigged configurations for the simply-laced affine types
,
,
,
, and
.
See also
There is a modified version for non-simply-laced affine types at
VirtualKleberTree
.The nodes correspond to the weights in the positive Weyl chamber obtained by subtracting a (non-zero) positive root. The edges are labeled by the coefficients of the roots, and
is a child of
if
is the root else if the edge label of
to its parent
is greater (in every component) than the label from
to
.
For a Kleber tree, one needs to specify an affine (simply-laced) Cartan type and a sequence of pairs
, where
is any positive integer and
is a node in the Dynkin diagram. Each
can be viewed as a rectangle of width
and height
.
INPUT:
cartan_type
– an affine simply-laced Cartan typeB
– a list of dimensions of rectangles bywhere
is the number of rows and
is the number of columns
REFERENCES:
[Kleber1] (1, 2) Michael Kleber. Combinatorial structure of finite dimensional representations of Yangians: the simply-laced case. Internat. Math. Res. Notices. (1997) no. 4. 187-201. [Kleber2] Michael Kleber. Finite dimensional representations of quantum affine algebras. Ph.D. dissertation at University of California Berkeley. (1998). Arxiv math.QA/9809087. EXAMPLES:
Simply-laced example:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree sage: KT = KleberTree(['A', 3, 1], [[3,2], [1,1]]) sage: KT.list() [Kleber tree node with weight [1, 0, 2] and upwards edge root [0, 0, 0], Kleber tree node with weight [0, 0, 1] and upwards edge root [1, 1, 1]] sage: KT = KleberTree(['A', 3, 1], [[3,2], [2,1], [1,1], [1,1]]) sage: KT.cardinality() 10 sage: KT = KleberTree(['D', 4, 1], [[2,2]]) sage: KT.cardinality() 3 sage: KT = KleberTree(['D', 4, 1], [[4,5]]) sage: KT.cardinality() 1
From [Kleber2]:
sage: KT = KleberTree(['E', 6, 1], [[4, 2]]) # long time (9s on sage.math, 2012) sage: KT.cardinality() # long time 12
We check that relabelled types work (trac ticket #16876):
sage: ct = CartanType(['A',3,1]).relabel(lambda x: x+2) sage: kt = KleberTree(ct, [[3,1],[5,1]]) sage: list(kt) [Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 0, 0], Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 1, 1]] sage: kt = KleberTree(['A',3,1], [[1,1],[3,1]]) sage: list(kt) [Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 0, 0], Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 1, 1]]
-
Element
¶ alias of
KleberTreeNode
-
breadth_first_iter
()¶ Iterate over all nodes in the tree following a breadth-first traversal.
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree sage: KT = KleberTree(['A', 3, 1], [[2, 2], [2, 3]]) sage: for x in KT.breadth_first_iter(): x Kleber tree node with weight [0, 5, 0] and upwards edge root [0, 0, 0] Kleber tree node with weight [1, 3, 1] and upwards edge root [0, 1, 0] Kleber tree node with weight [0, 3, 0] and upwards edge root [1, 2, 1] Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 1, 0] Kleber tree node with weight [1, 1, 1] and upwards edge root [0, 1, 0] Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 2, 1]
-
cartan_type
()¶ Return the Cartan type of this Kleber tree.
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree sage: KT = KleberTree(['A', 3, 1], [[1,1]]) sage: KT.cartan_type() ['A', 3, 1]
-
depth_first_iter
()¶ Iterate (recursively) over the nodes in the tree following a depth-first traversal.
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree sage: KT = KleberTree(['A', 3, 1], [[2, 2], [2, 3]]) sage: for x in KT.depth_first_iter(): x Kleber tree node with weight [0, 5, 0] and upwards edge root [0, 0, 0] Kleber tree node with weight [1, 3, 1] and upwards edge root [0, 1, 0] Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 1, 0] Kleber tree node with weight [0, 3, 0] and upwards edge root [1, 2, 1] Kleber tree node with weight [1, 1, 1] and upwards edge root [0, 1, 0] Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 2, 1]
-
digraph
()¶ Return a DiGraph representation of this Kleber tree.
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree sage: KT = KleberTree(['D', 4, 1], [[2, 2]]) sage: KT.digraph() # optional - dot2tex graphviz Digraph on 3 vertices
-
latex_options
(**options)¶ Return the current latex options if no arguments are passed, otherwise set the corresponding latex option.
OPTIONS:
hspace
– (default:) the horizontal spacing of the tree nodes
vspace
– (default:x
) the vertical spacing of the tree nodes, herex
is the minimum ofor
where
is the rank of the classical type
edge_labels
– (default:True
) display edge labelsuse_vector_notation
– (default:False
) display edge labels using vector notation instead of a linear combination
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree sage: KT = KleberTree(['D', 3, 1], [[2,1], [2,1]]) sage: KT.latex_options(vspace=-4, use_vector_notation=True) sage: sorted(KT.latex_options().items()) [('edge_labels', True), ('hspace', 2.5), ('use_vector_notation', True), ('vspace', -4)]
-
plot
(**options)¶ Return the plot of self as a directed graph.
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree sage: KT = KleberTree(['D', 4, 1], [[2, 2]]) sage: print(KT.plot()) # optional - dot2tex graphviz Graphics object consisting of 8 graphics primitives
-
class
sage.combinat.rigged_configurations.kleber_tree.
KleberTreeNode
(parent_obj, node_weight, dominant_root, parent_node=None)¶ Bases:
sage.structure.element.Element
A node in the Kleber tree.
This class is meant to be used internally by the Kleber tree class and should not be created directly by the user.
For more on the Kleber tree and the nodes, see
KleberTree
.The dominating root is the
up_root
which is the difference between the parent node’s weight and this node’s weight.INPUT:
parent_obj
– The parent object of this elementnode_weight
– The weight of this nodedominant_root
– The dominating rootparent_node
– (default:None) The parent node of this node
-
depth
()¶ Return the depth of this node in the tree.
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree sage: RS = RootSystem(['A', 2]) sage: WS = RS.weight_space() sage: R = RS.root_space() sage: KT = KleberTree(['A', 2, 1], [[1,1]]) sage: n = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero()) sage: n.depth 0 sage: n2 = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero(), n) sage: n2.depth 1
-
multiplicity
()¶ Return the multiplicity of
self
.The multiplicity of a node
of depth
weight
in a simply-laced Kleber tree is equal to:
Recall that
where
is the weight node at depth
in the path to
from the root and we set
for all
.
Note that
for all
.
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree sage: KT = KleberTree(['A',3,1], [[3,2],[2,1],[1,1],[1,1]]) sage: for x in KT: x, x.multiplicity() (Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 0, 0], 1) (Kleber tree node with weight [0, 2, 2] and upwards edge root [1, 0, 0], 1) (Kleber tree node with weight [1, 0, 3] and upwards edge root [1, 1, 0], 2) (Kleber tree node with weight [1, 1, 1] and upwards edge root [1, 1, 1], 4) (Kleber tree node with weight [0, 0, 2] and upwards edge root [2, 2, 1], 2) (Kleber tree node with weight [3, 0, 1] and upwards edge root [0, 1, 1], 1) (Kleber tree node with weight [2, 0, 0] and upwards edge root [0, 1, 1], 2) (Kleber tree node with weight [0, 0, 2] and upwards edge root [1, 1, 0], 1) (Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 1, 1], 2) (Kleber tree node with weight [0, 1, 0] and upwards edge root [0, 0, 1], 1)
TESTS:
We check that trac ticket #16057 is fixed:
sage: RC = RiggedConfigurations(['D',4,1], [[1,3],[3,3],[4,3]]) sage: sum(x.multiplicity() for x in RC.kleber_tree()) == len(RC.module_generators) True
-
class
sage.combinat.rigged_configurations.kleber_tree.
KleberTreeTypeA2Even
(cartan_type, B)¶ Bases:
sage.combinat.rigged_configurations.kleber_tree.VirtualKleberTree
Kleber tree for types
and
.
Note that here for
we use
in place of
in constructing the virtual Kleber tree, and so we end up selecting all nodes since
for all
. For type
, we have
for all
.
See also
-
breadth_first_iter
(all_nodes=False)¶ Iterate over all nodes in the tree following a breadth-first traversal.
INPUT:
all_nodes
– (default:False
) ifTrue
, output all nodes in the tree
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree sage: KT = VirtualKleberTree(['A', 4, 2], [[2,1]]) sage: for x in KT.breadth_first_iter(): x Kleber tree node with weight [0, 2, 0] and upwards edge root [0, 0, 0] Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0] Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 2, 1] sage: for x in KT.breadth_first_iter(True): x Kleber tree node with weight [0, 2, 0] and upwards edge root [0, 0, 0] Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0] Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 2, 1]
-
depth_first_iter
(all_nodes=False)¶ Iterate (recursively) over the nodes in the tree following a depth-first traversal.
INPUT:
all_nodes
– (default:False
) ifTrue
, output all nodes in the tree
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree sage: KT = VirtualKleberTree(['A', 4, 2], [[2,1]]) sage: for x in KT.depth_first_iter(): x Kleber tree node with weight [0, 2, 0] and upwards edge root [0, 0, 0] Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0] Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 2, 1] sage: for x in KT.depth_first_iter(True): x Kleber tree node with weight [0, 2, 0] and upwards edge root [0, 0, 0] Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0] Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 2, 1]
-
-
class
sage.combinat.rigged_configurations.kleber_tree.
VirtualKleberTree
(cartan_type, B)¶ Bases:
sage.combinat.rigged_configurations.kleber_tree.KleberTree
A virtual Kleber tree.
We can use a modified version of the Kleber algorithm called the virtual Kleber algorithm [OSS03] to compute all admissible rigged configurations for non-simply-laced types. This uses the following embeddings into the simply-laced types:
One then selects the subset of admissible nodes which are translates of the virtual requirements. In the graph, the selected nodes are indicated by brackets
.
Note
Because these are virtual nodes, all information is given in the corresponding simply-laced type.
See also
For more on the Kleber algorithm, see
KleberTree
.REFERENCES:
[OSS03] Masato Okado, Anne Schilling, and Mark Shimozono. Virtual crystals and Klebers algorithm. Commun. Math. Phys. 238 (2003). 187-209. Arxiv math.QA/0209082. INPUT:
cartan_type
– an affine non-simply-laced Cartan typeB
– a list of dimensions of rectangles bywhere
is the number of rows and
is the number of columns
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree sage: KT = VirtualKleberTree(['C', 4, 1], [[2,2]]) sage: KT.cardinality() 3 sage: KT.base_tree().cardinality() 6 sage: KT = VirtualKleberTree(['C', 4, 1], [[4,5]]) sage: KT.cardinality() 1 sage: KT = VirtualKleberTree(['D', 5, 2], [[2,1], [1,1]]) sage: KT.cardinality() 8 sage: KT = VirtualKleberTree(CartanType(['A', 4, 2]).dual(), [[1,1], [2,2]]) sage: KT.cardinality() 15
-
base_tree
()¶ Return the underlying virtual Kleber tree associated to
self
.EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree sage: KT = VirtualKleberTree(['C', 4, 1], [[2,2]]) sage: KT.base_tree() Kleber tree of Cartan type ['A', 7, 1] and B = ((2, 2), (6, 2))
-
breadth_first_iter
(all_nodes=False)¶ Iterate over all nodes in the tree following a breadth-first traversal.
INPUT:
all_nodes
– (default:False
) ifTrue
, output all nodes in the tree
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree sage: KT = VirtualKleberTree(['C', 2, 1], [[1,1], [2,1]]) sage: for x in KT.breadth_first_iter(): x Kleber tree node with weight [1, 2, 1] and upwards edge root [0, 0, 0] Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0] sage: for x in KT.breadth_first_iter(True): x Kleber tree node with weight [1, 2, 1] and upwards edge root [0, 0, 0] Kleber tree node with weight [0, 2, 0] and upwards edge root [1, 1, 1] Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0]
-
depth_first_iter
(all_nodes=False)¶ Iterate (recursively) over the nodes in the tree following a depth-first traversal.
INPUT:
all_nodes
– (default:False
) ifTrue
, output all nodes in the tree
EXAMPLES:
sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree sage: KT = VirtualKleberTree(['C', 2, 1], [[1,1], [2,1]]) sage: for x in KT.depth_first_iter(): x Kleber tree node with weight [1, 2, 1] and upwards edge root [0, 0, 0] Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0] sage: for x in KT.depth_first_iter(True): x Kleber tree node with weight [1, 2, 1] and upwards edge root [0, 0, 0] Kleber tree node with weight [0, 2, 0] and upwards edge root [1, 1, 1] Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0]