Diagram and Partition Algebras¶

AUTHORS:

Mike Hansen (2007): Initial version
Stephen Doty, Aaron Lauve, George H. Seelinger (2012): Implementation of partition, Brauer, Temperley–Lieb, and ideal partition algebras
Stephen Doty, Aaron Lauve, George H. Seelinger (2015): Implementation of *Diagram classes and other methods to improve diagram algebras.

class sage.combinat.diagram_algebras.AbstractPartitionDiagram(parent, d)¶

Bases: sage.combinat.set_partition.SetPartition

Abstract base class for partition diagrams.

This class represents a single partition diagram, that is used as a basis key for a diagram algebra element. A partition diagram should be a partition of the set $\{1, \ldots, k, -1, \ldots, -k\}$ . Each such set partition is regarded as a graph on nodes $\{1, \ldots, k, -1, \ldots, -k\}$ arranged in two rows, with nodes $1, \ldots, k$ in the top row from left to right and with nodes $-1, \ldots, -k$ in the bottom row from left to right, and an edge connecting two nodes if and only if the nodes lie in the same subset of the set partition.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: pd = da.AbstractPartitionDiagrams(da.partition_diagrams, 2)
sage: pd1 = da.AbstractPartitionDiagram(pd, [[1,2],[-1,-2]])
sage: pd2 = da.AbstractPartitionDiagram(pd, [[1,2],[-1,-2]])
sage: pd1
{{-2, -1}, {1, 2}}
sage: pd1 == pd2
True
sage: pd1 == [[1,2],[-1,-2]]
True
sage: pd1 == ((-2,-1),(2,1))
True
sage: pd1 == SetPartition([[1,2],[-1,-2]])
True
sage: pd3 = da.AbstractPartitionDiagram(pd, [[1,-2],[-1,2]])
sage: pd1 == pd3
False
sage: pd4 = da.AbstractPartitionDiagram(pd, [[1,2],[3,4]])
Traceback (most recent call last):
...
ValueError: this does not represent two rows of vertices

base_diagram()¶

Return the underlying implementation of the diagram.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: pd = da.AbstractPartitionDiagrams(da.partition_diagrams, 2)
sage: pd([[1,2],[-1,-2]]).base_diagram() == ((-2,-1),(1,2))
True

check()¶

Check the validity of the input for the diagram.

TESTS:

sage: import sage.combinat.diagram_algebras as da
sage: pd = da.AbstractPartitionDiagrams(da.partition_diagrams, 2)
sage: pd1 = da.AbstractPartitionDiagram(pd, [[1,2],[-1,-2]]) # indirect doctest
sage: pd2 = da.AbstractPartitionDiagram(pd, [[1,2],[3,4]]) # indirect doctest
Traceback (most recent call last):
...
ValueError: this does not represent two rows of vertices

compose(other)¶

Compose self with other.

The composition of two diagrams $X$ and $Y$ is given by placing $X$ on top of $Y$ and removing all loops.

OUTPUT:

A tuple where the first entry is the composite diagram and the second entry is how many loop were removed.

Note

This is not really meant to be called directly, but it works to call it this way if desired.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: pd = da.AbstractPartitionDiagrams(da.partition_diagrams, 2)
sage: pd([[1,2],[-1,-2]]).compose(pd([[1,2],[-1,-2]]))
({{-2, -1}, {1, 2}}, 1)

diagram()¶

Return the underlying implementation of the diagram.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: pd = da.AbstractPartitionDiagrams(da.partition_diagrams, 2)
sage: pd([[1,2],[-1,-2]]).base_diagram() == pd([[1,2],[-1,-2]]).diagram()
True

global_options(*args, **kwds)¶: Deprecated: Use options() instead. See trac ticket #18555 for details.

options(*get_value, **set_value)¶

Set and display the global options for Brauer diagram (algebras). If no parameters are set, then the function returns a copy of the options dictionary.

The options to diagram algebras can be accessed as the method BrauerAlgebra.options of BrauerAlgebra and related classes.

OPTIONS:

display – (default: normal) Specifies how the Brauer diagrams should be printed
- compact – Using the compact representation
- normal – Using the normal representation

EXAMPLES:

sage: R.<q> = QQ[]
sage: BA = BrauerAlgebra(2, q)
sage: E = BA([[1,2],[-1,-2]])
sage: E
B{{-2, -1}, {1, 2}}
sage: BrauerAlgebra.options.display="compact"
sage: E
B[12/12;]
sage: BrauerAlgebra.options._reset()

See GlobalOptions for more features of these options.

propagating_number()¶

Return the propagating number of the diagram.

The propagating number is the number of blocks with both a positive and negative number.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: pd = da.AbstractPartitionDiagrams(da.partition_diagrams, 2)
sage: d1 = pd([[1,-2],[2,-1]])
sage: d1.propagating_number()
2
sage: d2 = pd([[1,2],[-2,-1]])
sage: d2.propagating_number()
0

class sage.combinat.diagram_algebras.AbstractPartitionDiagrams(diagram_func, order, category=None)¶

Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation

This is a class that generates partition diagrams.

Thee primary use of this class is to serve as basis keys for diagram algebras, but diagrams also have properties in their own right. Furthermore, this class is meant to be extended to create more efficient contains methods.

INPUT:

diagram_func – generator; a function that can create the type of diagram desired
order – integer or integer $+ 1/2$ ; the order of the diagrams

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: pd = da.AbstractPartitionDiagrams(da.partition_diagrams, 2)
sage: pd
Partition diagrams of order 2
sage: [i for i in pd]
[{{-2, -1, 1, 2}},
 {{-2, -1, 2}, {1}},
 {{-2, -1, 1}, {2}},
 {{-2}, {-1, 1, 2}},
 {{-2, 1, 2}, {-1}},
 {{-2, 1}, {-1, 2}},
 {{-2, 2}, {-1, 1}},
 {{-2, -1}, {1, 2}},
 {{-2, -1}, {1}, {2}},
 {{-2}, {-1, 2}, {1}},
 {{-2, 2}, {-1}, {1}},
 {{-2}, {-1, 1}, {2}},
 {{-2, 1}, {-1}, {2}},
 {{-2}, {-1}, {1, 2}},
 {{-2}, {-1}, {1}, {2}}]
sage: pd.an_element() in pd
True
sage: elm = pd([[1,2],[-1,-2]])
sage: elm in pd
True

Element¶: alias of AbstractPartitionDiagram

class sage.combinat.diagram_algebras.BrauerAlgebra(k, q, base_ring, prefix)¶

Bases: sage.combinat.diagram_algebras.SubPartitionAlgebra

A Brauer algebra.

The Brauer algebra of rank $k$ is an algebra with basis indexed by the collection of set partitions of $\{1, \ldots, k, -1, \ldots, -k\}$ with block size 2.

This algebra is a subalgebra of the partition algebra. For more information, see PartitionAlgebra.

INPUT:

k – rank of the algebra
q – the deformation parameter $q$

OPTIONAL ARGUMENTS:

base_ring – (default None) a ring containing q; if None then just takes the parent of q
prefix – (default "B") a label for the basis elements

EXAMPLES:

We now define the Brauer algebra of rank $2$ with parameter x over $\ZZ$ :

sage: R.<x> = ZZ[]
sage: B = BrauerAlgebra(2, x, R)
sage: B
Brauer Algebra of rank 2 with parameter x
 over Univariate Polynomial Ring in x over Integer Ring
sage: B.basis()
Lazy family (Term map from Brauer diagrams of order 2 to Brauer Algebra
 of rank 2 with parameter x over Univariate Polynomial Ring in x
 over Integer Ring(i))_{i in Brauer diagrams of order 2}
sage: b = B.basis().list()
sage: b
[B{{-2, 1}, {-1, 2}}, B{{-2, 2}, {-1, 1}}, B{{-2, -1}, {1, 2}}]
sage: b[2]
B{{-2, -1}, {1, 2}}
sage: b[2]^2
x*B{{-2, -1}, {1, 2}}
sage: b[2]^5
x^4*B{{-2, -1}, {1, 2}}

Note, also that since the symmetric group algebra is contained in the Brauer algebra, there is also a conversion between the two.

sage: R.<x> = ZZ[]
sage: B = BrauerAlgebra(2, x, R)
sage: S = SymmetricGroupAlgebra(R, 2)
sage: S([2,1])*B([[1,-1],[2,-2]])
B{{-2, 1}, {-1, 2}}

jucys_murphy(j)¶

Return the j-th generalized Jucys-Murphy element of self.

The $j$ -th Jucys-Murphy element of a Brauer algebra is simply the $j$ -th Jucys-Murphy element of the symmetric group algebra with an extra $(z-1)/2$ term, where z is the parameter of the Brauer algebra.

REFERENCES:

[Naz96]

Maxim Nazarov, Young’s Orthogonal Form for Brauer’s Centralizer Algebra. Journal of Algebra 182 (1996), 664–693.

EXAMPLES:

sage: z = var('z')
sage: B = BrauerAlgebra(3,z)
sage: B.jucys_murphy(1)
(1/2*z-1/2)*B{{-3, 3}, {-2, 2}, {-1, 1}}
sage: B.jucys_murphy(3)
-B{{-3, -2}, {-1, 1}, {2, 3}} - B{{-3, -1}, {-2, 2}, {1, 3}}
 + B{{-3, 1}, {-2, 2}, {-1, 3}} + B{{-3, 2}, {-2, 3}, {-1, 1}}
 + (1/2*z-1/2)*B{{-3, 3}, {-2, 2}, {-1, 1}}

class sage.combinat.diagram_algebras.BrauerDiagram(parent, d)¶

Bases: sage.combinat.diagram_algebras.AbstractPartitionDiagram

A Brauer diagram.

A Brauer diagram for an integer $k$ is a partition of the set $\{1, \ldots, k, -1, \ldots, -k\}$ with block size 2.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: bd = da.BrauerDiagrams(2)
sage: bd1 = bd([[1,2],[-1,-2]])
sage: bd2 = bd([[1,2,-1,-2]])
Traceback (most recent call last):
...
ValueError: all blocks must be of size 2

bijection_on_free_nodes(two_line=False)¶

Return the induced bijection - as a list of $(x,f(x))$ values - from the free nodes on the top at the Brauer diagram to the free nodes at the bottom of self.

OUTPUT:

If two_line is True, then the output is the induced bijection as a two-row list (inputs, outputs).

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: bd = da.BrauerDiagrams(3)
sage: elm = bd([[1,2],[-2,-3],[3,-1]])
sage: elm.bijection_on_free_nodes()
[[3, -1]]
sage: elm2 = bd([[1,-2],[2,-3],[3,-1]])
sage: elm2.bijection_on_free_nodes(two_line=True)
[[1, 2, 3], [-2, -3, -1]]

check()¶

Check the validity of the input for self.

TESTS:

sage: import sage.combinat.diagram_algebras as da
sage: bd = da.BrauerDiagrams(2)
sage: bd1 = bd([[1,2],[-1,-2]])  # indirect doctest
sage: bd2 = bd([[1,2,-1,-2]])    # indirect doctest
Traceback (most recent call last):
...
ValueError: all blocks must be of size 2

involution_permutation_triple(curt=True)¶

Return the involution permutation triple of self.

From Graham-Lehrer (see BrauerDiagrams), a Brauer diagram is a triple $(D_1, D_2, \pi)$ , where:

$D_1$ is a partition of the top nodes;
$D_2$ is a partition of the bottom nodes;
$\pi$ is the induced permutation on the free nodes.

INPUT:

curt – (default: True) if True, then return bijection on free nodes as a one-line notation (standardized to look like a permutation), else, return the honest mapping, a list of pairs $(i, -j)$ describing the bijection on free nodes

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: bd = da.BrauerDiagrams(3)
sage: elm = bd([[1,2],[-2,-3],[3,-1]])
sage: elm.involution_permutation_triple()
([(1, 2)], [(-3, -2)], [1])
sage: elm.involution_permutation_triple(curt=False)
([(1, 2)], [(-3, -2)], [[3, -1]])

is_elementary_symmetric()¶

Check if is elementary symmetric.

Let $(D_1, D_2, \pi)$ be the Graham-Lehrer representation of the Brauer diagram $d$ . We say $d$ is elementary symmetric if $D_1 = D_2$ and $\pi$ is the identity.

Todo

Come up with a better name?

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: bd = da.BrauerDiagrams(3)
sage: elm = bd([[1,2],[-1,-2],[3,-3]])
sage: elm.is_elementary_symmetric()
True
sage: elm2 = bd([[1,2],[-1,-3],[3,-2]])
sage: elm2.is_elementary_symmetric()
False

perm()¶

Return the induced bijection on the free nodes of self in one-line notation, re-indexed and treated as a permutation.

See also

bijection_on_free_nodes()

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: bd = da.BrauerDiagrams(3)
sage: elm = bd([[1,2],[-2,-3],[3,-1]])
sage: elm.perm()
[1]

class sage.combinat.diagram_algebras.BrauerDiagrams(order, category=None)¶

Bases: sage.combinat.diagram_algebras.AbstractPartitionDiagrams

This class represents all Brauer diagrams of integer or integer $+1/2$ order. For more information on Brauer diagrams, see BrauerAlgebra.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: bd = da.BrauerDiagrams(3)
sage: bd.an_element() in bd
True
sage: bd.cardinality() == len(bd.list())
True

These diagrams also come equipped with a compact representation based on their bipartition triple representation. See the from_involution_permutation_triple() method for more information.

sage: bd = da.BrauerDiagrams(3)
sage: bd.options.display="compact"
sage: bd.list()
[[/;321],
 [/;312],
 [23/12;1],
 [/;231],
 [/;132],
 [13/12;1],
 [/;213],
 [/;123],
 [12/12;1],
 [23/23;1],
 [13/23;1],
 [12/23;1],
 [23/13;1],
 [13/13;1],
 [12/13;1]]
sage: bd.options._reset()

Element¶: alias of BrauerDiagram

cardinality()¶

Return the cardinality of self.

The number of Brauer diagrams of integer order $k$ is $(2k-1)!!$ .

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: bd = da.BrauerDiagrams(3)
sage: bd.cardinality()
15

from_involution_permutation_triple(D1_D2_pi)¶

Construct a Bruaer diagram of self from an involution permutation triple.

A Brauer diagram can be represented as a triple where the first entry is a list of arcs on the top row of the diagram, the second entry is a list of arcs on the bottom row of the diagram, and the third entry is a permutation on the remaining nodes. This triple is called the involution permutation triple. For more information, see [GL1996].

INPUT:

D1_D2_pi– a list or tuple where the first entry is a list of arcs on the top of the diagram, the second entry is a list of arcs on the bottom of the diagram, and the third entry is a permutation on the free nodes.

REFERENCES:

[GL1996]

J.J. Graham and G.I. Lehrer, Cellular algebras. Inventiones mathematicae 123 (1996), 1–34.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: bd = da.BrauerDiagrams(4)
sage: bd.from_involution_permutation_triple([[[1,2]],[[3,4]],[2,1]])
{{-4, -3}, {-2, 3}, {-1, 4}, {1, 2}}

global_options(*args, **kwds)¶: Deprecated: Use options() instead. See trac ticket #18555 for details.

options(*get_value, **set_value)¶

Set and display the global options for Brauer diagram (algebras). If no parameters are set, then the function returns a copy of the options dictionary.

The options to diagram algebras can be accessed as the method BrauerAlgebra.options of BrauerAlgebra and related classes.

OPTIONS:

display – (default: normal) Specifies how the Brauer diagrams should be printed
- compact – Using the compact representation
- normal – Using the normal representation

EXAMPLES:

sage: R.<q> = QQ[]
sage: BA = BrauerAlgebra(2, q)
sage: E = BA([[1,2],[-1,-2]])
sage: E
B{{-2, -1}, {1, 2}}
sage: BrauerAlgebra.options.display="compact"
sage: E
B[12/12;]
sage: BrauerAlgebra.options._reset()

See GlobalOptions for more features of these options.

symmetric_diagrams(l=None, perm=None)¶

Return the list of brauer diagrams with symmetric placement of $l$ arcs, and with free nodes permuted according to $perm$ .

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: bd = da.BrauerDiagrams(4)
sage: bd.symmetric_diagrams(l=1,perm=[2,1])
[{{-4, -3}, {-2, 1}, {-1, 2}, {3, 4}},
 {{-4, -2}, {-3, 1}, {-1, 3}, {2, 4}},
 {{-4, 1}, {-3, -2}, {-1, 4}, {2, 3}},
 {{-4, -1}, {-3, 2}, {-2, 3}, {1, 4}},
 {{-4, 2}, {-3, -1}, {-2, 4}, {1, 3}},
 {{-4, 3}, {-3, 4}, {-2, -1}, {1, 2}}]

class sage.combinat.diagram_algebras.DiagramAlgebra(k, q, base_ring, prefix, diagrams, category=None)¶

Bases: sage.combinat.free_module.CombinatorialFreeModule

Abstract class for diagram algebras and is not designed to be used directly. If used directly, the class could create an “algebra” that is not actually an algebra.

TESTS:

sage: import sage.combinat.diagram_algebras as da
sage: R.<x> = QQ[]
sage: D = da.DiagramAlgebra(2, x, R, 'P', da.PartitionDiagrams(2))
sage: sorted(D.basis())
[P{{-2}, {-1}, {1}, {2}},
 P{{-2}, {-1}, {1, 2}},
 P{{-2}, {-1, 1}, {2}},
 P{{-2}, {-1, 1, 2}},
 P{{-2}, {-1, 2}, {1}},
 P{{-2, -1}, {1}, {2}},
 P{{-2, -1}, {1, 2}},
 P{{-2, -1, 1}, {2}},
 P{{-2, -1, 1, 2}},
 P{{-2, -1, 2}, {1}},
 P{{-2, 1}, {-1}, {2}},
 P{{-2, 1}, {-1, 2}},
 P{{-2, 1, 2}, {-1}},
 P{{-2, 2}, {-1}, {1}},
 P{{-2, 2}, {-1, 1}}]

class Element(M, x)¶

Bases: sage.combinat.free_module.CombinatorialFreeModuleElement

An element of a diagram algebra.

This subclass provides a few additional methods for partition algebra elements. Most element methods are already implemented elsewhere.

diagram()¶

Return the underlying diagram of self if self is a basis element. Raises an error if self is not a basis element.

EXAMPLES:

sage: R.<x> = ZZ[]
sage: P = PartitionAlgebra(2, x, R)
sage: elt = 3*P([[1,2],[-2,-1]])
sage: elt.diagram()
{{-2, -1}, {1, 2}}

diagrams()¶

Return the diagrams in the support of self.

EXAMPLES:

sage: R.<x> = ZZ[]
sage: P = PartitionAlgebra(2, x, R)
sage: elt = 3*P([[1,2],[-2,-1]]) + P([[1,2],[-2], [-1]])
sage: elt.diagrams()
[{{-2}, {-1}, {1, 2}}, {{-2, -1}, {1, 2}}]

DiagramAlgebra.one_basis()¶

The following constructs the identity element of self.

It is not called directly; instead one should use DA.one() if DA is a defined diagram algebra.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: R.<x> = QQ[]
sage: D = da.DiagramAlgebra(2, x, R, 'P', da.PartitionDiagrams(2))
sage: D.one_basis()
{{-2, 2}, {-1, 1}}

DiagramAlgebra.order()¶

Return the order of self.

The order of a partition algebra is defined as half of the number of nodes in the diagrams.

EXAMPLES:

sage: q = var('q')
sage: PA = PartitionAlgebra(2, q)
sage: PA.order()
2

DiagramAlgebra.product_on_basis(d1, d2)¶

Return the product $D_{d_1} D_{d_2}$ by two basis diagrams.

TESTS:

sage: import sage.combinat.diagram_algebras as da
sage: R.<x> = QQ[]
sage: D = da.DiagramAlgebra(2, x, R, 'P', da.PartitionDiagrams(2))
sage: sp = da.PartitionDiagrams(2)([[1,2],[-1,-2]])
sage: D.product_on_basis(sp, sp)
x*P{{-2, -1}, {1, 2}}

DiagramAlgebra.set_partitions()¶

Return the collection of underlying set partitions indexing the basis elements of a given diagram algebra.

Todo

Is this really necessary?

TESTS:

sage: import sage.combinat.diagram_algebras as da
sage: R.<x> = QQ[]
sage: D = da.DiagramAlgebra(2, x, R, 'P', da.PartitionDiagrams(2))
sage: list(D.set_partitions()) == list(da.PartitionDiagrams(2))
True

class sage.combinat.diagram_algebras.IdealDiagrams(order)¶

Bases: sage.combinat.diagram_algebras.AbstractPartitionDiagrams

All “ideal” diagrams of integer or integer $+1/2$ order.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: id = da.IdealDiagrams(3)
sage: id.an_element() in id
True
sage: id.cardinality() == len(id.list())
True

class sage.combinat.diagram_algebras.PartitionAlgebra(k, q, base_ring, prefix)¶

Bases: sage.combinat.diagram_algebras.DiagramAlgebra

A partition algebra.

A partition algebra of rank $k$ over a given ground ring $R$ is an algebra with ( $R$ -module) basis indexed by the collection of set partitions of $\{1, \ldots, k, -1, \ldots, -k\}$ . Each such set partition can be represented by a graph on nodes $\{1, \ldots, k, -1, \ldots, -k\}$ arranged in two rows, with nodes $1, \ldots, k$ in the top row from left to right and with nodes $-1, \ldots, -k$ in the bottom row from left to right, and edges drawn such that the connected components of the graph are precisely the parts of the set partition. (This choice of edges is often not unique, and so there are often many graphs representing one and the same set partition; the representation nevertheless is useful and vivid. We often speak of “diagrams” to mean graphs up to such equivalence of choices of edges; of course, we could just as well speak of set partitions.)

There is not just one partition algebra of given rank over a given ground ring, but rather a whole family of them, indexed by the elements of $R$ . More precisely, for every $q \in R$ , the partition algebra of rank $k$ over $R$ with parameter $q$ is defined to be the $R$ -algebra with basis the collection of all set partitions of $\{1, \ldots, k, -1, \ldots, -k\}$ , where the product of two basis elements is given by the rule

$a \cdot b = q^N (a \circ b),$

where $a \circ b$ is the composite set partition obtained by placing the diagram (i.e., graph) of $a$ above the diagram of $b$ , identifying the bottom row nodes of $a$ with the top row nodes of $b$ , and omitting any closed “loops” in the middle. The number $N$ is the number of connected components formed by the omitted loops.

The parameter $q$ is a deformation parameter. Taking $q = 1$ produces the semigroup algebra (over the base ring) of the partition monoid, in which the product of two set partitions is simply given by their composition.

The Iwahori–Hecke algebra of type $A$ (with a single parameter) is naturally a subalgebra of the partition algebra.

The partition algebra is regarded as an example of a “diagram algebra” due to the fact that its natural basis is given by certain graphs often called diagrams.

An excellent reference for partition algebras and their various subalgebras (Brauer algebra, Temperley–Lieb algebra, etc) is the paper [HR2005].

INPUT:

k – rank of the algebra
q – the deformation parameter $q$

OPTIONAL ARGUMENTS:

base_ring – (default None) a ring containing q; if None, then Sage automatically chooses the parent of q
prefix – (default "P") a label for the basis elements

EXAMPLES:

The following shorthand simultaneously defines the univariate polynomial ring over the rationals as well as the variable x:

sage: R.<x> = PolynomialRing(QQ)
sage: R
Univariate Polynomial Ring in x over Rational Field
sage: x
x
sage: x.parent() is R
True

We now define the partition algebra of rank $2$ with parameter x over $\ZZ$ :

sage: R.<x> = ZZ[]
sage: P = PartitionAlgebra(2, x, R)
sage: P
Partition Algebra of rank 2 with parameter x
 over Univariate Polynomial Ring in x over Integer Ring
sage: P.basis().list()
[P{{-2, -1, 1, 2}}, P{{-2, -1, 2}, {1}},
 P{{-2, -1, 1}, {2}}, P{{-2}, {-1, 1, 2}},
 P{{-2, 1, 2}, {-1}}, P{{-2, 1}, {-1, 2}},
 P{{-2, 2}, {-1, 1}}, P{{-2, -1}, {1, 2}},
 P{{-2, -1}, {1}, {2}}, P{{-2}, {-1, 2}, {1}},
 P{{-2, 2}, {-1}, {1}}, P{{-2}, {-1, 1}, {2}},
 P{{-2, 1}, {-1}, {2}}, P{{-2}, {-1}, {1, 2}},
 P{{-2}, {-1}, {1}, {2}}]
sage: E = P([[1,2],[-2,-1]]); E
P{{-2, -1}, {1, 2}}
sage: E in P.basis().list()
True
sage: E^2
x*P{{-2, -1}, {1, 2}}
sage: E^5
x^4*P{{-2, -1}, {1, 2}}
sage: (P([[2,-2],[-1,1]]) - 2*P([[1,2],[-1,-2]]))^2
(4*x-4)*P{{-2, -1}, {1, 2}} + P{{-2, 2}, {-1, 1}}

One can work with partition algebras using a symbol for the parameter, leaving the base ring unspecified. This implies that the underlying base ring is Sage’s symbolic ring.

sage: q = var('q')
sage: PA = PartitionAlgebra(2, q); PA
Partition Algebra of rank 2 with parameter q over Symbolic Ring
sage: PA([[1,2],[-2,-1]])^2 == q*PA([[1,2],[-2,-1]])
True
sage: (PA([[2, -2], [1, -1]]) - 2*PA([[-2, -1], [1, 2]]))^2 == (4*q-4)*PA([[1, 2], [-2, -1]]) + PA([[2, -2], [1, -1]])
True

The identity element of the partition algebra is the set partition $\{\{1,-1\}, \{2,-2\}, \ldots, \{k,-k\}\}$ :

sage: P = PA.basis().list()
sage: PA.one()
P{{-2, 2}, {-1, 1}}
sage: PA.one()*P[7] == P[7]
True
sage: P[7]*PA.one() == P[7]
True

We now give some further examples of the use of the other arguments. One may wish to “specialize” the parameter to a chosen element of the base ring:

sage: R.<q> = RR[]
sage: PA = PartitionAlgebra(2, q, R, prefix='B')
sage: PA
Partition Algebra of rank 2 with parameter q over
 Univariate Polynomial Ring in q over Real Field with 53 bits of precision
sage: PA([[1,2],[-1,-2]])
1.00000000000000*B{{-2, -1}, {1, 2}}
sage: PA = PartitionAlgebra(2, 5, base_ring=ZZ, prefix='B')
sage: PA
Partition Algebra of rank 2 with parameter 5 over Integer Ring
sage: (PA([[2, -2], [1, -1]]) - 2*PA([[-2, -1], [1, 2]]))^2 == 16*PA([[-2, -1], [1, 2]]) + PA([[2, -2], [1, -1]])
True

TESTS:

A computation that returned an incorrect result until trac ticket #15958:

sage: A = PartitionAlgebra(1,17)
sage: g = SetPartitionsAk(1).list()
sage: a = A[g[1]]
sage: a
P{{-1}, {1}}
sage: a*a
17*P{{-1}, {1}}

Symmetric group algebra elements can also be coerced into the partition algebra:

sage: S = SymmetricGroupAlgebra(SR, 2)
sage: A = PartitionAlgebra(2, x, SR)
sage: S([2,1])*A([[1,-1],[2,-2]])
P{{-2, 1}, {-1, 2}}

REFERENCES:

[HR2005]

(1, 2) Tom Halverson and Arun Ram, Partition algebras. European Journal of Combinatorics 26 (2005), 869–921.

class sage.combinat.diagram_algebras.PartitionDiagrams(order, category=None)¶

Bases: sage.combinat.diagram_algebras.AbstractPartitionDiagrams

This class represents all partition diagrams of integer or integer $+ 1/2$ order.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: pd = da.PartitionDiagrams(3)
sage: pd.an_element() in pd
True
sage: pd.cardinality() == len(pd.list())
True

cardinality()¶

The cardinality of partition diagrams of integer order $n$ is the $2n$ -th Bell number.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: pd = da.PartitionDiagrams(3)
sage: pd.cardinality()
203

class sage.combinat.diagram_algebras.PlanarAlgebra(k, q, base_ring, prefix)¶

Bases: sage.combinat.diagram_algebras.SubPartitionAlgebra

A planar algebra.

The planar algebra of rank $k$ is an algebra with basis indexed by the collection of all planar set partitions of $\{1, \ldots, k, -1, \ldots, -k\}$ .

This algebra is thus a subalgebra of the partition algebra. For more information, see PartitionAlgebra.

INPUT:

k – rank of the algebra
q – the deformation parameter $q$

OPTIONAL ARGUMENTS:

base_ring – (default None) a ring containing q; if None then just takes the parent of q
prefix – (default "Pl") a label for the basis elements

EXAMPLES:

We define the planar algebra of rank $2$ with parameter $x$ over $\ZZ$ :

sage: R.<x> = ZZ[]
sage: Pl = PlanarAlgebra(2, x, R); Pl
Planar Algebra of rank 2 with parameter x over Univariate Polynomial Ring in x over Integer Ring
sage: Pl.basis().list()
[Pl{{-2, -1, 1, 2}}, Pl{{-2, -1, 2}, {1}},
 Pl{{-2, -1, 1}, {2}}, Pl{{-2}, {-1, 1, 2}},
 Pl{{-2, 1, 2}, {-1}}, Pl{{-2, 2}, {-1, 1}},
 Pl{{-2, -1}, {1, 2}}, Pl{{-2, -1}, {1}, {2}},
 Pl{{-2}, {-1, 2}, {1}}, Pl{{-2, 2}, {-1}, {1}},
 Pl{{-2}, {-1, 1}, {2}}, Pl{{-2, 1}, {-1}, {2}},
 Pl{{-2}, {-1}, {1, 2}}, Pl{{-2}, {-1}, {1}, {2}}]
sage: E = Pl([[1,2],[-1,-2]])
sage: E^2 == x*E
True
sage: E^5 == x^4*E
True

class sage.combinat.diagram_algebras.PlanarDiagrams(order)¶

Bases: sage.combinat.diagram_algebras.AbstractPartitionDiagrams

All planar diagrams of integer or integer $+1/2$ order.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: pld = da.PlanarDiagrams(3)
sage: pld.an_element() in pld
True
sage: pld.cardinality() == len(pld.list())
True

cardinality()¶

Return the cardinality of self.

The number of all planar diagrams of order $k$ is the $2k$ -th Catalan number.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: pld = da.PlanarDiagrams(3)
sage: pld.cardinality()
132

class sage.combinat.diagram_algebras.PropagatingIdeal(k, q, base_ring, prefix)¶

Bases: sage.combinat.diagram_algebras.SubPartitionAlgebra

A propagating ideal.

The propagating ideal of rank $k$ is a non-unital algebra with basis indexed by the collection of ideal set partitions of $\{1, \ldots, k, -1, \ldots, -k\}$ . We say a set partition is ideal if its propagating number is less than $k$ .

This algebra is a non-unital subalgebra and an ideal of the partition algebra. For more information, see PartitionAlgebra.

EXAMPLES:

We now define the propagating ideal of rank $2$ with parameter $x$ over $\ZZ$ :

sage: R.<x> = QQ[]
sage: I = PropagatingIdeal(2, x, R); I
Propagating Ideal of rank 2 with parameter x
 over Univariate Polynomial Ring in x over Rational Field
sage: I.basis().list()
[I{{-2, -1, 1, 2}}, I{{-2, -1, 2}, {1}},
 I{{-2, -1, 1}, {2}}, I{{-2}, {-1, 1, 2}},
 I{{-2, 1, 2}, {-1}}, I{{-2, -1}, {1, 2}},
 I{{-2, -1}, {1}, {2}}, I{{-2}, {-1, 2}, {1}},
 I{{-2, 2}, {-1}, {1}}, I{{-2}, {-1, 1}, {2}},
 I{{-2, 1}, {-1}, {2}}, I{{-2}, {-1}, {1, 2}},
 I{{-2}, {-1}, {1}, {2}}]
sage: E = I([[1,2],[-1,-2]])
sage: E^2 == x*E
True
sage: E^5 == x^4*E
True

class Element(M, x)¶

Bases: sage.combinat.diagram_algebras.DiagramAlgebra.Element

An element of a propagating ideal.

We need to take care of exponents since we are not unital.

PropagatingIdeal.one_basis()¶

The propagating ideal is a non-unital algebra, i.e. it does not have a multiplicative identity.

EXAMPLES:

sage: R.<q> = QQ[]
sage: I = PropagatingIdeal(2, q, R)
sage: I.one_basis()
Traceback (most recent call last):
...
ValueError: The ideal partition algebra is not unital
sage: I.one()
Traceback (most recent call last):
...
ValueError: The ideal partition algebra is not unital

class sage.combinat.diagram_algebras.SubPartitionAlgebra(k, q, base_ring, prefix, diagrams, category=None)¶

Bases: sage.combinat.diagram_algebras.DiagramAlgebra

A subalgebra of the partition algebra indexed by a subset of the diagrams.

ambient()¶

Return the partition algebra self is a sub-algebra of.

EXAMPLES:

sage: x = var('x')
sage: BA = BrauerAlgebra(2, x)
sage: BA.ambient()
Partition Algebra of rank 2 with parameter x over Symbolic Ring

lift()¶

Return the lift map from diagram subalgebra to the ambient space.

EXAMPLES:

sage: R.<x> = QQ[]
sage: BA = BrauerAlgebra(2, x, R)
sage: E = BA([[1,2],[-1,-2]])
sage: lifted = BA.lift(E); lifted
B{{-2, -1}, {1, 2}}
sage: lifted.parent() is BA.ambient()
True

retract(x)¶

Retract an appropriate partition algebra element to the corresponding element in the partition subalgebra.

EXAMPLES:

sage: R.<x> = QQ[]
sage: BA = BrauerAlgebra(2, x, R)
sage: PA = BA.ambient()
sage: E = PA([[1,2], [-1,-2]])
sage: BA.retract(E) in BA
True

class sage.combinat.diagram_algebras.TemperleyLiebAlgebra(k, q, base_ring, prefix)¶

Bases: sage.combinat.diagram_algebras.SubPartitionAlgebra

A Temperley–Lieb algebra.

The Temperley–Lieb algebra of rank $k$ is an algebra with basis indexed by the collection of planar set partitions of $\{1, \ldots, k, -1, \ldots, -k\}$ with block size 2.

This algebra is thus a subalgebra of the partition algebra. For more information, see PartitionAlgebra.

INPUT:

k – rank of the algebra
q – the deformation parameter $q$

OPTIONAL ARGUMENTS:

base_ring – (default None) a ring containing q; if None then just takes the parent of q
prefix – (default "T") a label for the basis elements

EXAMPLES:

We define the Temperley–Lieb algebra of rank $2$ with parameter $x$ over $\ZZ$ :

sage: R.<x> = ZZ[]
sage: T = TemperleyLiebAlgebra(2, x, R); T
Temperley-Lieb Algebra of rank 2 with parameter x
 over Univariate Polynomial Ring in x over Integer Ring
sage: T.basis()
Lazy family (Term map from Temperleylieb diagrams of order 2
 to Temperley-Lieb Algebra of rank 2 with parameter x
 over Univariate Polynomial Ring in x over
 Integer Ring(i))_{i in Temperleylieb diagrams of order 2}
sage: b = T.basis().list()
sage: b
[T{{-2, 2}, {-1, 1}}, T{{-2, -1}, {1, 2}}]
sage: b[1]
T{{-2, -1}, {1, 2}}
sage: b[1]^2 == x*b[1]
True
sage: b[1]^5 == x^4*b[1]
True

class sage.combinat.diagram_algebras.TemperleyLiebDiagrams(order)¶

Bases: sage.combinat.diagram_algebras.AbstractPartitionDiagrams

All Temperley-Lieb diagrams of integer or integer $+1/2$ order.

For more information on Temperley-Lieb diagrams, see TemperleyLiebAlgebra.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: td = da.TemperleyLiebDiagrams(3)
sage: td.an_element() in td
True
sage: td.cardinality() == len(td.list())
True

cardinality()¶

Return the cardinality of self.

The number of Temperley–Lieb diagrams of integer order $k$ is the $k$ -th Catalan number.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: td = da.TemperleyLiebDiagrams(3)
sage: td.cardinality()
5

sage.combinat.diagram_algebras.brauer_diagrams(k)¶

Return a generator of all Brauer diagrams of order k.

A Brauer diagram of order $k$ is a partition diagram of order $k$ with block size 2.

INPUT:

k – the order of the Brauer diagrams

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: [SetPartition(p) for p in da.brauer_diagrams(2)]
[{{-2, 1}, {-1, 2}}, {{-2, 2}, {-1, 1}}, {{-2, -1}, {1, 2}}]
sage: [SetPartition(p) for p in da.brauer_diagrams(5/2)]
[{{-3, 3}, {-2, 1}, {-1, 2}}, {{-3, 3}, {-2, 2}, {-1, 1}}, {{-3, 3}, {-2, -1}, {1, 2}}]

sage.combinat.diagram_algebras.ideal_diagrams(k)¶

Return a generator of all “ideal” diagrams of order k.

An ideal diagram of order $k$ is a partition diagram of order $k$ with propagating number less than $k$ .

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: [SetPartition(p) for p in da.ideal_diagrams(2)]
[{{-2, -1, 1, 2}}, {{-2, -1, 2}, {1}}, {{-2, -1, 1}, {2}}, {{-2}, {-1, 1, 2}},
 {{-2, 1, 2}, {-1}}, {{-2, -1}, {1, 2}}, {{-2, -1}, {1}, {2}},
 {{-2}, {-1, 2}, {1}}, {{-2, 2}, {-1}, {1}}, {{-2}, {-1, 1}, {2}}, {{-2, 1},
 {-1}, {2}}, {{-2}, {-1}, {1, 2}}, {{-2}, {-1}, {1}, {2}}]
sage: [SetPartition(p) for p in da.ideal_diagrams(3/2)]
[{{-2, -1, 1, 2}}, {{-2, -1, 2}, {1}}, {{-2, 1, 2}, {-1}}, {{-2, 2}, {-1}, {1}}]

sage.combinat.diagram_algebras.identity_set_partition(k)¶

Return the identity set partition $\{\{1, -1\}, \ldots, \{k, -k\}\}$

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: SetPartition(da.identity_set_partition(2))
{{-2, 2}, {-1, 1}}

sage.combinat.diagram_algebras.is_planar(sp)¶

Return True if the diagram corresponding to the set partition sp is planar; otherwise, return False.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: da.is_planar( da.to_set_partition([[1,-2],[2,-1]]))
False
sage: da.is_planar( da.to_set_partition([[1,-1],[2,-2]]))
True

sage.combinat.diagram_algebras.pair_to_graph(sp1, sp2)¶

Return a graph consisting of the disjoint union of the graphs of set partitions sp1 and sp2 along with edges joining the bottom row (negative numbers) of sp1 to the top row (positive numbers) of sp2.

The vertices of the graph sp1 appear in the result as pairs (k, 1), whereas the vertices of the graph sp2 appear as pairs (k, 2).

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: sp1 = da.to_set_partition([[1,-2],[2,-1]])
sage: sp2 = da.to_set_partition([[1,-2],[2,-1]])
sage: g = da.pair_to_graph( sp1, sp2 ); g
Graph on 8 vertices

sage: g.vertices()
[(-2, 1), (-2, 2), (-1, 1), (-1, 2), (1, 1), (1, 2), (2, 1), (2, 2)]
sage: g.edges()
[((-2, 1), (1, 1), None), ((-2, 1), (2, 2), None),
 ((-2, 2), (1, 2), None), ((-1, 1), (1, 2), None),
 ((-1, 1), (2, 1), None), ((-1, 2), (2, 2), None)]

Another example which used to be wrong until trac ticket #15958:

sage: sp3 = da.to_set_partition([[1, -1], [2], [-2]])
sage: sp4 = da.to_set_partition([[1], [-1], [2], [-2]])
sage: g = da.pair_to_graph( sp3, sp4 ); g
Graph on 8 vertices

sage: g.vertices()
[(-2, 1), (-2, 2), (-1, 1), (-1, 2), (1, 1), (1, 2), (2, 1), (2, 2)]
sage: g.edges()
[((-2, 1), (2, 2), None), ((-1, 1), (1, 1), None),
 ((-1, 1), (1, 2), None)]

sage.combinat.diagram_algebras.partition_diagrams(k)¶

Return a generator of all partition diagrams of order k.

A partition diagram of order $k \in \ZZ$ to is a set partition of $\{1, \ldots, k, -1, \ldots, -k\}$ . If we have $k - 1/2 \in ZZ$ , then a partition diagram of order $k \in 1/2 \ZZ$ is a set partition of $\{1, \ldots, k+1/2, -1, \ldots, -(k+1/2)\}$ with $k+1/2$ and $-(k+1/2)$ in the same block. See [HR2005].

INPUT:

k – the order of the partition diagrams

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: [SetPartition(p) for p in da.partition_diagrams(2)]
[{{-2, -1, 1, 2}}, {{-2, -1, 2}, {1}}, {{-2, -1, 1}, {2}},
 {{-2}, {-1, 1, 2}}, {{-2, 1, 2}, {-1}}, {{-2, 1}, {-1, 2}},
 {{-2, 2}, {-1, 1}}, {{-2, -1}, {1, 2}}, {{-2, -1}, {1}, {2}},
 {{-2}, {-1, 2}, {1}}, {{-2, 2}, {-1}, {1}}, {{-2}, {-1, 1}, {2}},
 {{-2, 1}, {-1}, {2}}, {{-2}, {-1}, {1, 2}}, {{-2}, {-1}, {1}, {2}}]
sage: [SetPartition(p) for p in da.partition_diagrams(3/2)]
[{{-2, -1, 1, 2}}, {{-2, -1, 2}, {1}}, {{-2, 2}, {-1, 1}},
 {{-2, 1, 2}, {-1}}, {{-2, 2}, {-1}, {1}}]

sage.combinat.diagram_algebras.planar_diagrams(k)¶

Return a generator of all planar diagrams of order k.

A planar diagram of order $k$ is a partition diagram of order $k$ that has no crossings.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: [SetPartition(p) for p in da.planar_diagrams(2)]
[{{-2, -1, 1, 2}}, {{-2, -1, 2}, {1}}, {{-2, -1, 1}, {2}},
 {{-2}, {-1, 1, 2}}, {{-2, 1, 2}, {-1}}, {{-2, 2}, {-1, 1}},
 {{-2, -1}, {1, 2}}, {{-2, -1}, {1}, {2}}, {{-2}, {-1, 2}, {1}},
 {{-2, 2}, {-1}, {1}}, {{-2}, {-1, 1}, {2}}, {{-2, 1}, {-1}, {2}},
 {{-2}, {-1}, {1, 2}}, {{-2}, {-1}, {1}, {2}}]
sage: [SetPartition(p) for p in da.planar_diagrams(3/2)]
[{{-2, -1, 1, 2}}, {{-2, -1, 2}, {1}}, {{-2, 2}, {-1, 1}},
 {{-2, 1, 2}, {-1}}, {{-2, 2}, {-1}, {1}}]

sage.combinat.diagram_algebras.propagating_number(sp)¶

Return the propagating number of the set partition sp.

The propagating number is the number of blocks with both a positive and negative number.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: sp1 = da.to_set_partition([[1,-2],[2,-1]])
sage: sp2 = da.to_set_partition([[1,2],[-2,-1]])
sage: da.propagating_number(sp1)
2
sage: da.propagating_number(sp2)
0

sage.combinat.diagram_algebras.set_partition_composition(sp1, sp2)¶

Return a tuple consisting of the composition of the set partitions sp1 and sp2 and the number of components removed from the middle rows of the graph.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: sp1 = da.to_set_partition([[1,-2],[2,-1]])
sage: sp2 = da.to_set_partition([[1,-2],[2,-1]])
sage: p, c = da.set_partition_composition(sp1, sp2)
sage: (SetPartition(p), c) == (SetPartition(da.identity_set_partition(2)), 0)
True

sage.combinat.diagram_algebras.temperley_lieb_diagrams(k)¶

Return a generator of all Temperley–Lieb diagrams of order k.

A Temperley–Lieb diagram of order $k$ is a partition diagram of order $k$ with block size 2 and is planar.

INPUT:

k – the order of the Temperley–Lieb diagrams

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: [SetPartition(p) for p in da.temperley_lieb_diagrams(2)]
[{{-2, 2}, {-1, 1}}, {{-2, -1}, {1, 2}}]
sage: [SetPartition(p) for p in da.temperley_lieb_diagrams(5/2)]
[{{-3, 3}, {-2, 2}, {-1, 1}}, {{-3, 3}, {-2, -1}, {1, 2}}]

sage.combinat.diagram_algebras.to_Brauer_partition(l, k=None)¶

Same as to_set_partition() but assumes omitted elements are connected straight through.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: f = lambda sp: SetPartition(da.to_Brauer_partition(sp))
sage: f([[1,2],[-1,-2]]) == SetPartition([[1,2],[-1,-2]])
True
sage: f([[1,3],[-1,-3]]) == SetPartition([[1,3],[-3,-1],[2,-2]])
True
sage: f([[1,-4],[-3,-1],[3,4]]) == SetPartition([[-3,-1],[2,-2],[1,-4],[3,4]])
True
sage: p = SetPartition([[1,2],[-1,-2],[3,-3],[4,-4]])
sage: SetPartition(da.to_Brauer_partition([[1,2],[-1,-2]], k=4)) == p
True

sage.combinat.diagram_algebras.to_graph(sp)¶

Return a graph representing the set partition sp.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: g = da.to_graph( da.to_set_partition([[1,-2],[2,-1]])); g
Graph on 4 vertices

sage: g.vertices()
[-2, -1, 1, 2]
sage: g.edges()
[(-2, 1, None), (-1, 2, None)]

sage.combinat.diagram_algebras.to_set_partition(l, k=None)¶

Convert a list of a list of numbers to a set partitions. Each list of numbers in the outer list specifies the numbers contained in one of the blocks in the set partition.

If $k$ is specified, then the set partition will be a set partition of $\{1, \ldots, k, -1, \ldots, -k\}$ . Otherwise, $k$ will default to the minimum number needed to contain all of the specified numbers.

EXAMPLES:

sage: import sage.combinat.diagram_algebras as da
sage: f = lambda sp: SetPartition(da.to_set_partition(sp))
sage: f([[1,-1],[2,-2]]) == SetPartition(da.identity_set_partition(2))
True

Diagram and Partition Algebras¶

Previous topic

Next topic

This Page