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. - Mike Zabrocki (2018): Implementation of individual element diagram classes
- Aaron Lauve, Mike Zabrocki (2018): Implementation of orbit basis for Partition algebra.
-
sage.combinat.diagram_algebras.
AbstractPartitionDiagram
¶ 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(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: {{1, 2}, {3, 4}} does not represent two rows of vertices of order 2
-
sage.combinat.diagram_algebras.
AbstractPartitionDiagrams
¶ This is an abstract base class for partition diagrams.
The 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:
order
– integer or integer \(+ 1/2\); the order of the diagramscategory
– (default:FiniteEnumeratedSets()
); the category
All concrete classes should implement attributes
_name
– the name of the class_diagram_func
– an iterator function that takes the order as its only input
EXAMPLES:
sage: import sage.combinat.diagram_algebras as da sage: pd = da.PartitionDiagrams(2) sage: pd Partition diagrams of order 2 sage: pd.an_element() in pd True sage: elm = pd([[1,2],[-1,-2]]) sage: elm in pd True
-
sage.combinat.diagram_algebras.
BrauerAlgebra
¶ 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 algebraq
– the deformation parameter \(q\)
OPTIONAL ARGUMENTS:
base_ring
– (defaultNone
) a ring containingq
; ifNone
then just takes the parent ofq
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.basis().keys() Brauer diagrams of order 2 sage: B.basis().keys()([[-2, 1], [2, -1]]) {{-2, 1}, {-1, 2}} sage: b = B.basis().list(); b [B{{-2, -1}, {1, 2}}, B{{-2, 1}, {-1, 2}}, B{{-2, 2}, {-1, 1}}] sage: b[0] B{{-2, -1}, {1, 2}} sage: b[0]^2 x*B{{-2, -1}, {1, 2}} sage: b[0]^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}}
-
sage.combinat.diagram_algebras.
BrauerDiagram
¶ 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 of {{-2, -1, 1, 2}} must be of size 2
-
sage.combinat.diagram_algebras.
BrauerDiagrams
¶ 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(2); bd Brauer diagrams of order 2 sage: bd.list() [{{-2, -1}, {1, 2}}, {{-2, 1}, {-1, 2}}, {{-2, 2}, {-1, 1}}] sage: bd = da.BrauerDiagrams(5/2); bd Brauer diagrams of order 5/2 sage: bd.list() [{{-3, 3}, {-2, -1}, {1, 2}}, {{-3, 3}, {-2, 1}, {-1, 2}}, {{-3, 3}, {-2, 2}, {-1, 1}}]
sage: bd = da.BrauerDiagrams(3) sage: bd.options.display="compact" sage: bd.list() [[12/12;1], [13/12;1], [23/12;1], [23/13;1], [23/23;1], [/;132], [/;231], [/;321], [13/13;1], [12/13;1], [12/23;1], [13/23;1], [/;312], [/;213], [/;123]] sage: bd.options._reset()
-
sage.combinat.diagram_algebras.
DiagramAlgebra
¶ Abstract class for diagram algebras and is not designed to be used directly.
-
sage.combinat.diagram_algebras.
DiagramBasis
¶ Abstract base class for diagram algebras in the diagram basis.
-
sage.combinat.diagram_algebras.
IdealDiagram
¶ The element class for a ideal diagram.
An ideal diagram for an integer \(k\) is a partition of the set \(\{1, \ldots, k, -1, \ldots, -k\}\) where the propagating number is strictly smaller than the order.
EXAMPLES:
sage: from sage.combinat.diagram_algebras import IdealDiagrams as IDs sage: IDs(2) Ideal diagrams of order 2 sage: IDs(2).list() [{{-2, -1, 1, 2}}, {{-2, 1, 2}, {-1}}, {{-2}, {-1, 1, 2}}, {{-2, -1}, {1, 2}}, {{-2}, {-1}, {1, 2}}, {{-2, -1, 1}, {2}}, {{-2, 1}, {-1}, {2}}, {{-2, -1, 2}, {1}}, {{-2, 2}, {-1}, {1}}, {{-2}, {-1, 1}, {2}}, {{-2}, {-1, 2}, {1}}, {{-2, -1}, {1}, {2}}, {{-2}, {-1}, {1}, {2}}] sage: from sage.combinat.diagram_algebras import PartitionDiagrams as PDs sage: PDs(4).cardinality() == factorial(4) + IDs(4).cardinality() True
-
sage.combinat.diagram_algebras.
IdealDiagrams
¶ All “ideal” diagrams of integer or integer \(+1/2\) order.
If \(k\) is an integer then 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: id = da.IdealDiagrams(3) sage: id.an_element() in id True sage: id.cardinality() == len(id.list()) True sage: da.IdealDiagrams(3/2).list() [{{-2, -1, 1, 2}}, {{-2, 1, 2}, {-1}}, {{-2, -1, 2}, {1}}, {{-2, 2}, {-1}, {1}}]
-
sage.combinat.diagram_algebras.
OrbitBasis
¶ The orbit basis of the partition algebra.
Let \(D_\pi\) represent the diagram basis element indexed by the partition \(\pi\), then (see equations (2.14), (2.17) and (2.18) of [BH2017])
\[D_\pi = \sum_{\tau \geq \pi} O_\tau,\]where the sum is over all partitions \(\tau\) which are coarser than \(\pi\) and \(O_\tau\) is the orbit basis element indexed by the partition \(\tau\).
If \(\mu_{2k}(\pi,\tau)\) represents the mobius function of the partition lattice, then
\[O_\pi = \sum_{\tau \geq \pi} \mu_{2k}(\pi, \tau) D_\tau.\]If \(\tau\) is a partition of \(\ell\) blocks and the \(i^{th}\) block of \(\tau\) is a union of \(b_i\) blocks of \(\pi\), then
\[\mu_{2k}(\pi, \tau) = \prod_{i=1}^\ell (-1)^{b_i-1} (b_i-1)! .\]EXAMPLES:
sage: R.<x> = QQ[] sage: P2 = PartitionAlgebra(2, x, R) sage: O2 = P2.orbit_basis(); O2 Orbit basis of Partition Algebra of rank 2 with parameter x over Univariate Polynomial Ring in x over Rational Field sage: oa = O2([[1],[-1],[2,-2]]); ob = O2([[-1,-2,2],[1]]); oa, ob (O{{-2, 2}, {-1}, {1}}, O{{-2, -1, 2}, {1}}) sage: oa * ob (x-2)*O{{-2, -1, 2}, {1}}
We can convert between the two bases:
sage: pa = P2(oa); pa 2*P{{-2, -1, 1, 2}} - P{{-2, -1, 2}, {1}} - P{{-2, 1, 2}, {-1}} + P{{-2, 2}, {-1}, {1}} - P{{-2, 2}, {-1, 1}} sage: pa * ob (-x+2)*P{{-2, -1, 1, 2}} + (x-2)*P{{-2, -1, 2}, {1}} sage: _ == pa * P2(ob) True sage: O2(pa * ob) (x-2)*O{{-2, -1, 2}, {1}}
Note that the unit in the orbit basis is not a single diagram, in contrast to the natural diagram basis:
sage: P2.one() P{{-2, 2}, {-1, 1}} sage: O2.one() O{{-2, -1, 1, 2}} + O{{-2, 2}, {-1, 1}} sage: O2.one() == P2.one() True
-
sage.combinat.diagram_algebras.
PartitionAlgebra
¶ 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 algebraq
– the deformation parameter \(q\)
OPTIONAL ARGUMENTS:
base_ring
– (defaultNone
) a ring containingq
; ifNone
, then Sage automatically chooses the parent ofq
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\) in the usual (diagram) basis:sage: R.<x> = ZZ[] sage: A2 = PartitionAlgebra(2, x, R) sage: A2 Partition Algebra of rank 2 with parameter x over Univariate Polynomial Ring in x over Integer Ring sage: A2.basis().keys() Partition diagrams of order 2 sage: A2.basis().keys()([[-2, 1, 2], [-1]]) {{-2, 1, 2}, {-1}} sage: A2.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}, {1, 2}}, P{{-2, -1, 1}, {2}}, P{{-2, 1}, {-1, 2}}, P{{-2, 1}, {-1}, {2}}, P{{-2, 2}, {-1, 1}}, P{{-2, -1, 2}, {1}}, P{{-2, 2}, {-1}, {1}}, P{{-2}, {-1, 1}, {2}}, P{{-2}, {-1, 2}, {1}}, P{{-2, -1}, {1}, {2}}, P{{-2}, {-1}, {1}, {2}}] sage: E = A2([[1,2],[-2,-1]]); E P{{-2, -1}, {1, 2}} sage: E in A2.basis().list() True sage: E^2 x*P{{-2, -1}, {1, 2}} sage: E^5 x^4*P{{-2, -1}, {1, 2}} sage: (A2([[2,-2],[-1,1]]) - 2*A2([[1,2],[-1,-2]]))^2 (4*x-4)*P{{-2, -1}, {1, 2}} + P{{-2, 2}, {-1, 1}}
Next, we construct an element:
sage: a2 = A2.an_element(); a2 3*P{{-2}, {-1, 1, 2}} + 2*P{{-2, -1, 1, 2}} + 2*P{{-2, 1, 2}, {-1}}
There is a natural embedding into partition algebras on more elements, by adding identity strands:
sage: A4 = PartitionAlgebra(4, x, R) sage: A4(a2) 3*P{{-4, 4}, {-3, 3}, {-2}, {-1, 1, 2}} + 2*P{{-4, 4}, {-3, 3}, {-2, -1, 1, 2}} + 2*P{{-4, 4}, {-3, 3}, {-2, 1, 2}, {-1}}
Thus, the empty partition corresponds to the identity:
sage: A4([]) P{{-4, 4}, {-3, 3}, {-2, 2}, {-1, 1}} sage: A4(5) 5*P{{-4, 4}, {-3, 3}, {-2, 2}, {-1, 1}}
The group algebra of the symmetric group is a subalgebra:
sage: S3 = SymmetricGroupAlgebra(ZZ, 3) sage: s3 = S3.an_element(); s3 [1, 2, 3] + 2*[1, 3, 2] + 3*[2, 1, 3] + [3, 1, 2] sage: A4(s3) P{{-4, 4}, {-3, 1}, {-2, 3}, {-1, 2}} + 2*P{{-4, 4}, {-3, 2}, {-2, 3}, {-1, 1}} + 3*P{{-4, 4}, {-3, 3}, {-2, 1}, {-1, 2}} + P{{-4, 4}, {-3, 3}, {-2, 2}, {-1, 1}} sage: A4([2,1]) P{{-4, 4}, {-3, 3}, {-2, 1}, {-1, 2}}
Be careful not to confuse the embedding of the group algebra of the symmetric group with the embedding of partial set partitions. The latter are embedded by adding the parts \(\{i,-i\}\) if possible, and singletons sets for the remaining parts:
sage: A4([[2,1]]) P{{-4, 4}, {-3, 3}, {-2}, {-1}, {1, 2}} sage: A4([[-1,3],[-2,-3,1]]) P{{-4, 4}, {-3, -2, 1}, {-1, 3}, {2}}
Another subalgebra is the Brauer algebra, which has perfect matchings as basis elements. The group algebra of the symmetric group is in fact a subalgebra of the Brauer algebra:
sage: B3 = BrauerAlgebra(3, x, R) sage: b3 = B3(s3); b3 B{{-3, 1}, {-2, 3}, {-1, 2}} + 2*B{{-3, 2}, {-2, 3}, {-1, 1}} + 3*B{{-3, 3}, {-2, 1}, {-1, 2}} + B{{-3, 3}, {-2, 2}, {-1, 1}}
An important basis of the partition algebra is the
orbit basis
:sage: O2 = A2.orbit_basis() sage: o2 = O2([[1,2],[-1,-2]]) + O2([[1,2,-1,-2]]); o2 O{{-2, -1}, {1, 2}} + O{{-2, -1, 1, 2}}
The diagram basis element corresponds to the sum of all orbit basis elements indexed by coarser set partitions:
sage: A2(o2) P{{-2, -1}, {1, 2}}
We can convert back from the orbit basis to the diagram basis:
sage: o2 = O2.an_element(); o2 3*O{{-2}, {-1, 1, 2}} + 2*O{{-2, -1, 1, 2}} + 2*O{{-2, 1, 2}, {-1}} sage: A2(o2) 3*P{{-2}, {-1, 1, 2}} - 3*P{{-2, -1, 1, 2}} + 2*P{{-2, 1, 2}, {-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
Symmetric group algebra elements and elements from other subalgebras of the partition algebra (e.g.,
BrauerAlgebra
andTemperleyLiebAlgebra
) can also be coerced into the partition algebra:sage: S = SymmetricGroupAlgebra(SR, 2) sage: B = BrauerAlgebra(2, x, SR) sage: A = PartitionAlgebra(2, x, SR) sage: S([2,1])*A([[1,-1],[2,-2]]) P{{-2, 1}, {-1, 2}} sage: B([[-1,-2],[2,1]]) * A([[1],[-1],[2,-2]]) P{{-2}, {-1}, {1, 2}} sage: A([[1],[-1],[2,-2]]) * B([[-1,-2],[2,1]]) P{{-2, -1}, {1}, {2}}
The same is true if the elements come from a subalgebra of a partition algebra of smaller order, or if they are defined over a different base ring:
sage: R = FractionField(ZZ['q']); q = R.gen() sage: S = SymmetricGroupAlgebra(ZZ, 2) sage: B = BrauerAlgebra(2, q, ZZ[q]) sage: A = PartitionAlgebra(3, q, R) sage: S([2,1])*A([[1,-1],[2,-3],[3,-2]]) P{{-3, 1}, {-2, 3}, {-1, 2}} sage: A(B([[-1,-2],[2,1]])) P{{-3, 3}, {-2, -1}, {1, 2}}
REFERENCES:
[HR2005] (1, 2) Tom Halverson and Arun Ram, Partition algebras. European Journal of Combinatorics 26 (2005), 869–921.
-
sage.combinat.diagram_algebras.
PartitionDiagram
¶ The element class for a partition diagram.
A partition diagram for an integer \(k\) is a partition of the set \(\{1, \ldots, k, -1, \ldots, -k\}\)
EXAMPLES:
sage: from sage.combinat.diagram_algebras import PartitionDiagram, PartitionDiagrams sage: PartitionDiagrams(1) Partition diagrams of order 1 sage: PartitionDiagrams(1).list() [{{-1, 1}}, {{-1}, {1}}] sage: PartitionDiagram([[1,-1]]) {{-1, 1}} sage: PartitionDiagram(((1,-2),(2,-1))).parent() Partition diagrams of order 2
-
sage.combinat.diagram_algebras.
PartitionDiagrams
¶ 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(1); pd Partition diagrams of order 1 sage: pd.list() [{{-1, 1}}, {{-1}, {1}}] sage: pd = da.PartitionDiagrams(3/2); pd Partition diagrams of order 3/2 sage: pd.list() [{{-2, -1, 1, 2}}, {{-2, 1, 2}, {-1}}, {{-2, 2}, {-1, 1}}, {{-2, -1, 2}, {1}}, {{-2, 2}, {-1}, {1}}]
-
sage.combinat.diagram_algebras.
PlanarAlgebra
¶ 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 algebraq
– the deformation parameter \(q\)
OPTIONAL ARGUMENTS:
base_ring
– (defaultNone
) a ring containingq
; ifNone
then just takes the parent ofq
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().keys() Planar diagrams of order 2 sage: Pl.basis().keys()([[-1, 1], [2, -2]]) {{-2, 2}, {-1, 1}} 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}, {1, 2}}, Pl{{-2, -1, 1}, {2}}, Pl{{-2, 1}, {-1}, {2}}, Pl{{-2, 2}, {-1, 1}}, Pl{{-2, -1, 2}, {1}}, Pl{{-2, 2}, {-1}, {1}}, Pl{{-2}, {-1, 1}, {2}}, Pl{{-2}, {-1, 2}, {1}}, 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
-
sage.combinat.diagram_algebras.
PlanarDiagram
¶ The element class for a planar diagram.
A planar diagram for an integer \(k\) is a partition of the set \(\{1, \ldots, k, -1, \ldots, -k\}\) so that the diagram is non-crossing.
EXAMPLES:
sage: from sage.combinat.diagram_algebras import PlanarDiagrams sage: PlanarDiagrams(2) Planar diagrams of order 2 sage: PlanarDiagrams(2).list() [{{-2, -1, 1, 2}}, {{-2, 1, 2}, {-1}}, {{-2}, {-1, 1, 2}}, {{-2, -1}, {1, 2}}, {{-2}, {-1}, {1, 2}}, {{-2, -1, 1}, {2}}, {{-2, 1}, {-1}, {2}}, {{-2, 2}, {-1, 1}}, {{-2, -1, 2}, {1}}, {{-2, 2}, {-1}, {1}}, {{-2}, {-1, 1}, {2}}, {{-2}, {-1, 2}, {1}}, {{-2, -1}, {1}, {2}}, {{-2}, {-1}, {1}, {2}}]
-
sage.combinat.diagram_algebras.
PlanarDiagrams
¶ All planar diagrams of integer or integer \(+1/2\) order.
EXAMPLES:
sage: import sage.combinat.diagram_algebras as da sage: pld = da.PlanarDiagrams(1); pld Planar diagrams of order 1 sage: pld.list() [{{-1, 1}}, {{-1}, {1}}] sage: pld = da.PlanarDiagrams(3/2); pld Planar diagrams of order 3/2 sage: pld.list() [{{-2, -1, 1, 2}}, {{-2, 1, 2}, {-1}}, {{-2, 2}, {-1, 1}}, {{-2, -1, 2}, {1}}, {{-2, 2}, {-1}, {1}}]
-
sage.combinat.diagram_algebras.
PropagatingIdeal
¶ 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().keys() Ideal diagrams of order 2 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}, {1, 2}}, 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, 2}, {1}}, 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
-
sage.combinat.diagram_algebras.
SubPartitionAlgebra
¶ A subalgebra of the partition algebra in the diagram basis indexed by a subset of the diagrams.
-
sage.combinat.diagram_algebras.
TemperleyLiebAlgebra
¶ 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 algebraq
– the deformation parameter \(q\)
OPTIONAL ARGUMENTS:
base_ring
– (defaultNone
) a ring containingq
; ifNone
then just takes the parent ofq
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 Temperley Lieb 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 Temperley Lieb diagrams of order 2} sage: T.basis().keys() Temperley Lieb diagrams of order 2 sage: T.basis().keys()([[-1, 1], [2, -2]]) {{-2, 2}, {-1, 1}} sage: b = T.basis().list(); b [T{{-2, -1}, {1, 2}}, T{{-2, 2}, {-1, 1}}] sage: b[0] T{{-2, -1}, {1, 2}} sage: b[0]^2 == x*b[0] True sage: b[0]^5 == x^4*b[0] True
-
sage.combinat.diagram_algebras.
TemperleyLiebDiagram
¶ The element class for a Temperley-Lieb diagram.
A Temperley-Lieb diagram for an integer \(k\) is a partition of the set \(\{1, \ldots, k, -1, \ldots, -k\}\) so that the blocks are all of size 2 and the diagram is planar.
EXAMPLES:
sage: from sage.combinat.diagram_algebras import TemperleyLiebDiagrams sage: TemperleyLiebDiagrams(2) Temperley Lieb diagrams of order 2 sage: TemperleyLiebDiagrams(2).list() [{{-2, -1}, {1, 2}}, {{-2, 2}, {-1, 1}}]
-
sage.combinat.diagram_algebras.
TemperleyLiebDiagrams
¶ 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); td Temperley Lieb diagrams of order 3 sage: td.list() [{{-3, 3}, {-2, -1}, {1, 2}}, {{-3, 1}, {-2, -1}, {2, 3}}, {{-3, -2}, {-1, 1}, {2, 3}}, {{-3, -2}, {-1, 3}, {1, 2}}, {{-3, 3}, {-2, 2}, {-1, 1}}] sage: td = da.TemperleyLiebDiagrams(5/2); td Temperley Lieb diagrams of order 5/2 sage: td.list() [{{-3, 3}, {-2, -1}, {1, 2}}, {{-3, 3}, {-2, 2}, {-1, 1}}]
-
class
sage.combinat.diagram_algebras.
UnitDiagramMixin
¶ Bases:
object
Mixin class for diagram algebras that have the unit indexed by the
identity_set_partition()
.-
one_basis
()¶ The following constructs the identity element of
self
.It is not called directly; instead one should use
DA.one()
ifDA
is a defined diagram algebra.EXAMPLES:
sage: R.<x> = QQ[] sage: P = PartitionAlgebra(2, x, R) sage: P.one_basis() {{-2, 2}, {-1, 1}}
-
-
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, 1}, {-1, 2}}, {{-2, 2}, {-1, 1}}] sage: [SetPartition(p) for p in da.brauer_diagrams(5/2)] [{{-3, 3}, {-2, -1}, {1, 2}}, {{-3, 3}, {-2, 1}, {-1, 2}}, {{-3, 3}, {-2, 2}, {-1, 1}}]
-
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: all_diagrams = da.partition_diagrams(2) sage: [SetPartition(p) for p in all_diagrams if p not in da.ideal_diagrams(2)] [{{-2, 1}, {-1, 2}}, {{-2, 2}, {-1, 1}}] sage: all_diagrams = da.partition_diagrams(3/2) sage: [SetPartition(p) for p in all_diagrams if p not in da.ideal_diagrams(3/2)] [{{-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 partitionsp
is planar; otherwise, returnFalse
.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
andsp2
along with edges joining the bottom row (negative numbers) ofsp1
to the top row (positive numbers) ofsp2
.The vertices of the graph
sp1
appear in the result as pairs(k, 1)
, whereas the vertices of the graphsp2
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}, {1, 2}}, {{-2, -1, 1}, {2}}, {{-2, 1}, {-1, 2}}, {{-2, 1}, {-1}, {2}}, {{-2, 2}, {-1, 1}}, {{-2, -1, 2}, {1}}, {{-2, 2}, {-1}, {1}}, {{-2}, {-1, 1}, {2}}, {{-2}, {-1, 2}, {1}}, {{-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: all_diagrams = da.partition_diagrams(2) sage: [SetPartition(p) for p in all_diagrams if p not in da.planar_diagrams(2)] [{{-2, 1}, {-1, 2}}] sage: all_diagrams = da.partition_diagrams(5/2) sage: [SetPartition(p) for p in all_diagrams if p not in da.planar_diagrams(5/2)] [{{-3, -1, 3}, {-2, 1, 2}}, {{-3, -2, 1, 3}, {-1, 2}}, {{-3, -1, 1, 3}, {-2, 2}}, {{-3, 1, 3}, {-2, -1, 2}}, {{-3, 1, 3}, {-2, 2}, {-1}}, {{-3, 1, 3}, {-2}, {-1, 2}}, {{-3, -1, 2, 3}, {-2, 1}}, {{-3, 3}, {-2, 1}, {-1, 2}}, {{-3, -1, 3}, {-2, 1}, {2}}, {{-3, -1, 3}, {-2, 2}, {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
andsp2
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, -1}, {1, 2}}, {{-2, 2}, {-1, 1}}] sage: [SetPartition(p) for p in da.temperley_lieb_diagrams(5/2)] [{{-3, 3}, {-2, -1}, {1, 2}}, {{-3, 3}, {-2, 2}, {-1, 1}}]
-
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 input to a set partition of \(\{1, \ldots, k, -1, \ldots, -k\}\)
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.
INPUT:
l
- a list of lists of integersk
- integer (optional, defaultNone
)
OUTPUT:
- a list of sets
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 sage: da.to_set_partition([[1]]) [{1}, {-1}] sage: da.to_set_partition([[1,-1],[-2,3]],9/2) [{-1, 1}, {-2, 3}, {2}, {-4, 4}, {-5, 5}, {-3}]