Yang-Baxter Graphs

class sage.combinat.yang_baxter_graph.SwapIncreasingOperator(i)[source]

Bases: SwapOperator

class sage.combinat.yang_baxter_graph.SwapOperator(i)[source]

Bases: SageObject

The operator that swaps the items in positions i and i+1.

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapOperator
sage: s3 = SwapOperator(3)
sage: s3 == loads(dumps(s3))
True

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapOperator
>>> s3 = SwapOperator(Integer(3))
>>> s3 == loads(dumps(s3))
True

from sage.combinat.yang_baxter_graph import SwapOperator
s3 = SwapOperator(3)
s3 == loads(dumps(s3))
position()[source]

Return i where self is the operator that swaps positions i and i+1.

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapOperator
sage: s3 = SwapOperator(3)
sage: s3.position()
3

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapOperator
>>> s3 = SwapOperator(Integer(3))
>>> s3.position()
3

from sage.combinat.yang_baxter_graph import SwapOperator
s3 = SwapOperator(3)
s3.position()
sage.combinat.yang_baxter_graph.YangBaxterGraph(partition=None, root=None, operators=None)[source]

Construct the Yang-Baxter graph from root by repeated application of operators, or the Yang-Baxter graph associated to partition.

INPUT:

The user needs to provide either partition or both root and operators, where

  • partition – a partition of a positive integer

  • root – the root vertex

  • operator – a function that maps vertices \(u\) to a list of tuples of the form \((v, l)\) where \(v\) is a successor of \(u\) and \(l\) is the label of the edge from \(u\) to \(v\).

OUTPUT: either:

EXAMPLES:

The Yang-Baxter graph defined by a partition \([p_1,\dots,p_k]\) is the labelled directed graph with vertex set obtained by bubble-sorting \((p_k-1,p_k-2,\dots,0,\dots,p_1-1,p_1-2,\dots,0)\); there is an arrow from \(u\) to \(v\) labelled by \(i\) if \(v\) is obtained by swapping the \(i\)-th and \((i+1)\)-th elements of \(u\). For example, if the partition is \([3,1]\), then we begin with \((0,2,1,0)\) and generate all tuples obtained from it by swapping two adjacent entries if they are increasing:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: bubbleswaps = [SwapIncreasingOperator(i) for i in range(3)]
sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=bubbleswaps); Y
Yang-Baxter graph with root vertex (0, 2, 1, 0)
sage: Y.vertices(sort=True)
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> bubbleswaps = [SwapIncreasingOperator(i) for i in range(Integer(3))]
>>> Y = YangBaxterGraph(root=(Integer(0),Integer(2),Integer(1),Integer(0)), operators=bubbleswaps); Y
Yang-Baxter graph with root vertex (0, 2, 1, 0)
>>> Y.vertices(sort=True)
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
bubbleswaps = [SwapIncreasingOperator(i) for i in range(3)]
Y = YangBaxterGraph(root=(0,2,1,0), operators=bubbleswaps); Y
Y.vertices(sort=True)

The partition keyword is a shorthand for the above construction:

sage: Y = YangBaxterGraph(partition=[3,1]); Y                                   # needs sage.combinat
Yang-Baxter graph of [3, 1], with top vertex (0, 2, 1, 0)
sage: Y.vertices(sort=True)
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]

>>> from sage.all import *
>>> Y = YangBaxterGraph(partition=[Integer(3),Integer(1)]); Y                                   # needs sage.combinat
Yang-Baxter graph of [3, 1], with top vertex (0, 2, 1, 0)
>>> Y.vertices(sort=True)
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]

Y = YangBaxterGraph(partition=[3,1]); Y                                   # needs sage.combinat
Y.vertices(sort=True)

The permutahedron can be realized as a Yang-Baxter graph:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: swappers = [SwapIncreasingOperator(i) for i in range(3)]
sage: Y = YangBaxterGraph(root=(1,2,3,4), operators=swappers); Y
Yang-Baxter graph with root vertex (1, 2, 3, 4)
sage: Y.plot()                                                                  # needs sage.plot
Graphics object consisting of 97 graphics primitives

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> swappers = [SwapIncreasingOperator(i) for i in range(Integer(3))]
>>> Y = YangBaxterGraph(root=(Integer(1),Integer(2),Integer(3),Integer(4)), operators=swappers); Y
Yang-Baxter graph with root vertex (1, 2, 3, 4)
>>> Y.plot()                                                                  # needs sage.plot
Graphics object consisting of 97 graphics primitives

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
swappers = [SwapIncreasingOperator(i) for i in range(3)]
Y = YangBaxterGraph(root=(1,2,3,4), operators=swappers); Y
Y.plot()                                                                  # needs sage.plot

The Cayley graph of a finite group can be realized as a Yang-Baxter graph:

sage: # needs sage.groups
sage: def left_multiplication_by(g):
....:     return lambda h: h*g
sage: G = CyclicPermutationGroup(4)
sage: operators = [ left_multiplication_by(gen) for gen in G.gens() ]
sage: Y = YangBaxterGraph(root=G.identity(), operators=operators); Y
Yang-Baxter graph with root vertex ()
sage: Y.plot(edge_labels=False)                                                 # needs sage.plot
Graphics object consisting of 9 graphics primitives

sage: # needs sage.groups
sage: G = SymmetricGroup(4)
sage: operators = [left_multiplication_by(gen) for gen in G.gens()]
sage: Y = YangBaxterGraph(root=G.identity(), operators=operators); Y
Yang-Baxter graph with root vertex ()
sage: Y.plot(edge_labels=False)                                                 # needs sage.plot
Graphics object consisting of 96 graphics primitives

>>> from sage.all import *
>>> # needs sage.groups
>>> def left_multiplication_by(g):
...     return lambda h: h*g
>>> G = CyclicPermutationGroup(Integer(4))
>>> operators = [ left_multiplication_by(gen) for gen in G.gens() ]
>>> Y = YangBaxterGraph(root=G.identity(), operators=operators); Y
Yang-Baxter graph with root vertex ()
>>> Y.plot(edge_labels=False)                                                 # needs sage.plot
Graphics object consisting of 9 graphics primitives

>>> # needs sage.groups
>>> G = SymmetricGroup(Integer(4))
>>> operators = [left_multiplication_by(gen) for gen in G.gens()]
>>> Y = YangBaxterGraph(root=G.identity(), operators=operators); Y
Yang-Baxter graph with root vertex ()
>>> Y.plot(edge_labels=False)                                                 # needs sage.plot
Graphics object consisting of 96 graphics primitives

# needs sage.groups
def left_multiplication_by(g):
    return lambda h: h*g
G = CyclicPermutationGroup(4)
operators = [ left_multiplication_by(gen) for gen in G.gens() ]
Y = YangBaxterGraph(root=G.identity(), operators=operators); Y
Y.plot(edge_labels=False)                                                 # needs sage.plot
# needs sage.groups
G = SymmetricGroup(4)
operators = [left_multiplication_by(gen) for gen in G.gens()]
Y = YangBaxterGraph(root=G.identity(), operators=operators); Y
Y.plot(edge_labels=False)                                                 # needs sage.plot

AUTHORS:

  • Franco Saliola (2009-04-23)

class sage.combinat.yang_baxter_graph.YangBaxterGraph_generic(root, operators)[source]

Bases: SageObject

A class to model the Yang-Baxter graph defined by root and operators.

INPUT:

  • root – the root vertex of the graph

  • operators – list of callables that map vertices to (new) vertices

Note

This is a lazy implementation: the digraph is only computed when it is needed.

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: ops = [SwapIncreasingOperator(i) for i in range(4)]
sage: Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops); Y
Yang-Baxter graph with root vertex (1, 0, 2, 1, 0)
sage: loads(dumps(Y)) == Y
True

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> ops = [SwapIncreasingOperator(i) for i in range(Integer(4))]
>>> Y = YangBaxterGraph(root=(Integer(1),Integer(0),Integer(2),Integer(1),Integer(0)), operators=ops); Y
Yang-Baxter graph with root vertex (1, 0, 2, 1, 0)
>>> loads(dumps(Y)) == Y
True

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
ops = [SwapIncreasingOperator(i) for i in range(4)]
Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops); Y
loads(dumps(Y)) == Y

AUTHORS:

  • Franco Saliola (2009-04-23)

edges()[source]

Return the (labelled) edges of self.

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: ops = [SwapIncreasingOperator(i) for i in range(3)]
sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)
sage: Y.edges()
[((0, 2, 1, 0), (2, 0, 1, 0), Swap-if-increasing at position 0), ((2, 0, 1, 0), (2, 1, 0, 0), Swap-if-increasing at position 1)]

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> ops = [SwapIncreasingOperator(i) for i in range(Integer(3))]
>>> Y = YangBaxterGraph(root=(Integer(0),Integer(2),Integer(1),Integer(0)), operators=ops)
>>> Y.edges()
[((0, 2, 1, 0), (2, 0, 1, 0), Swap-if-increasing at position 0), ((2, 0, 1, 0), (2, 1, 0, 0), Swap-if-increasing at position 1)]

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
ops = [SwapIncreasingOperator(i) for i in range(3)]
Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)
Y.edges()
plot(*args, **kwds)[source]

Plot self as a digraph.

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: ops = [SwapIncreasingOperator(i) for i in range(4)]
sage: Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops)
sage: Y.plot()                                                              # needs sage.plot
Graphics object consisting of 16 graphics primitives
sage: Y.plot(edge_labels=False)                                             # needs sage.plot
Graphics object consisting of 11 graphics primitives

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> ops = [SwapIncreasingOperator(i) for i in range(Integer(4))]
>>> Y = YangBaxterGraph(root=(Integer(1),Integer(0),Integer(2),Integer(1),Integer(0)), operators=ops)
>>> Y.plot()                                                              # needs sage.plot
Graphics object consisting of 16 graphics primitives
>>> Y.plot(edge_labels=False)                                             # needs sage.plot
Graphics object consisting of 11 graphics primitives

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
ops = [SwapIncreasingOperator(i) for i in range(4)]
Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops)
Y.plot()                                                              # needs sage.plot
Y.plot(edge_labels=False)                                             # needs sage.plot
relabel_edges(edge_dict, inplace=True)[source]

Relabel the edges of self.

INPUT:

  • edge_dict – dictionary keyed by the (unlabelled) edges

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: ops = [SwapIncreasingOperator(i) for i in range(3)]
sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)
sage: def relabel_op(op, u):
....:     i = op.position()
....:     return u[:i] + u[i:i+2][::-1] + u[i+2:]
sage: Y.edges()
[((0, 2, 1, 0), (2, 0, 1, 0), Swap-if-increasing at position 0), ((2, 0, 1, 0), (2, 1, 0, 0), Swap-if-increasing at position 1)]
sage: d = {((0,2,1,0),(2,0,1,0)):17, ((2,0,1,0),(2,1,0,0)):27}
sage: Y.relabel_edges(d, inplace=False).edges()
[((0, 2, 1, 0), (2, 0, 1, 0), 17), ((2, 0, 1, 0), (2, 1, 0, 0), 27)]
sage: Y.edges()
[((0, 2, 1, 0), (2, 0, 1, 0), Swap-if-increasing at position 0), ((2, 0, 1, 0), (2, 1, 0, 0), Swap-if-increasing at position 1)]
sage: Y.relabel_edges(d, inplace=True)
sage: Y.edges()
[((0, 2, 1, 0), (2, 0, 1, 0), 17), ((2, 0, 1, 0), (2, 1, 0, 0), 27)]

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> ops = [SwapIncreasingOperator(i) for i in range(Integer(3))]
>>> Y = YangBaxterGraph(root=(Integer(0),Integer(2),Integer(1),Integer(0)), operators=ops)
>>> def relabel_op(op, u):
...     i = op.position()
...     return u[:i] + u[i:i+Integer(2)][::-Integer(1)] + u[i+Integer(2):]
>>> Y.edges()
[((0, 2, 1, 0), (2, 0, 1, 0), Swap-if-increasing at position 0), ((2, 0, 1, 0), (2, 1, 0, 0), Swap-if-increasing at position 1)]
>>> d = {((Integer(0),Integer(2),Integer(1),Integer(0)),(Integer(2),Integer(0),Integer(1),Integer(0))):Integer(17), ((Integer(2),Integer(0),Integer(1),Integer(0)),(Integer(2),Integer(1),Integer(0),Integer(0))):Integer(27)}
>>> Y.relabel_edges(d, inplace=False).edges()
[((0, 2, 1, 0), (2, 0, 1, 0), 17), ((2, 0, 1, 0), (2, 1, 0, 0), 27)]
>>> Y.edges()
[((0, 2, 1, 0), (2, 0, 1, 0), Swap-if-increasing at position 0), ((2, 0, 1, 0), (2, 1, 0, 0), Swap-if-increasing at position 1)]
>>> Y.relabel_edges(d, inplace=True)
>>> Y.edges()
[((0, 2, 1, 0), (2, 0, 1, 0), 17), ((2, 0, 1, 0), (2, 1, 0, 0), 27)]

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
ops = [SwapIncreasingOperator(i) for i in range(3)]
Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)
def relabel_op(op, u):
    i = op.position()
    return u[:i] + u[i:i+2][::-1] + u[i+2:]
Y.edges()
d = {((0,2,1,0),(2,0,1,0)):17, ((2,0,1,0),(2,1,0,0)):27}
Y.relabel_edges(d, inplace=False).edges()
Y.edges()
Y.relabel_edges(d, inplace=True)
Y.edges()
relabel_vertices(v, relabel_operator, inplace=True)[source]

Relabel the vertices u of self by the object obtained from u by applying the relabel_operator to v along a path from self.root() to u.

Note that the self.root() is paired with v.

INPUT:

  • v – tuple, Permutation, etc.

  • inplace – if True, modifies self; otherwise returns a modified copy of self

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: ops = [SwapIncreasingOperator(i) for i in range(3)]
sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)
sage: def relabel_op(op, u):
....:     i = op.position()
....:     return u[:i] + u[i:i+2][::-1] + u[i+2:]
sage: d = Y.relabel_vertices((1,2,3,4), relabel_op, inplace=False); d
Yang-Baxter graph with root vertex (1, 2, 3, 4)
sage: Y.vertices(sort=True)
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]
sage: e = Y.relabel_vertices((1,2,3,4), relabel_op); e
sage: Y.vertices(sort=True)
[(1, 2, 3, 4), (2, 1, 3, 4), (2, 3, 1, 4)]

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> ops = [SwapIncreasingOperator(i) for i in range(Integer(3))]
>>> Y = YangBaxterGraph(root=(Integer(0),Integer(2),Integer(1),Integer(0)), operators=ops)
>>> def relabel_op(op, u):
...     i = op.position()
...     return u[:i] + u[i:i+Integer(2)][::-Integer(1)] + u[i+Integer(2):]
>>> d = Y.relabel_vertices((Integer(1),Integer(2),Integer(3),Integer(4)), relabel_op, inplace=False); d
Yang-Baxter graph with root vertex (1, 2, 3, 4)
>>> Y.vertices(sort=True)
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]
>>> e = Y.relabel_vertices((Integer(1),Integer(2),Integer(3),Integer(4)), relabel_op); e
>>> Y.vertices(sort=True)
[(1, 2, 3, 4), (2, 1, 3, 4), (2, 3, 1, 4)]

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
ops = [SwapIncreasingOperator(i) for i in range(3)]
Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)
def relabel_op(op, u):
    i = op.position()
    return u[:i] + u[i:i+2][::-1] + u[i+2:]
d = Y.relabel_vertices((1,2,3,4), relabel_op, inplace=False); d
Y.vertices(sort=True)
e = Y.relabel_vertices((1,2,3,4), relabel_op); e
Y.vertices(sort=True)
root()[source]

Return the root vertex of self.

If self is the Yang-Baxter graph of the partition \([p_1,p_2,\dots,p_k]\), then this is the vertex \((p_k-1,p_k-2,\dots,0,\dots,p_1-1,p_1-2,\dots,0)\).

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: ops = [SwapIncreasingOperator(i) for i in range(4)]
sage: Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops)
sage: Y.root()
(1, 0, 2, 1, 0)
sage: Y = YangBaxterGraph(root=(0,1,0,2,1,0), operators=ops)
sage: Y.root()
(0, 1, 0, 2, 1, 0)
sage: Y = YangBaxterGraph(root=(1,0,3,2,1,0), operators=ops)
sage: Y.root()
(1, 0, 3, 2, 1, 0)
sage: Y = YangBaxterGraph(partition=[3,2])                                  # needs sage.combinat
sage: Y.root()                                                              # needs sage.combinat
(1, 0, 2, 1, 0)

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> ops = [SwapIncreasingOperator(i) for i in range(Integer(4))]
>>> Y = YangBaxterGraph(root=(Integer(1),Integer(0),Integer(2),Integer(1),Integer(0)), operators=ops)
>>> Y.root()
(1, 0, 2, 1, 0)
>>> Y = YangBaxterGraph(root=(Integer(0),Integer(1),Integer(0),Integer(2),Integer(1),Integer(0)), operators=ops)
>>> Y.root()
(0, 1, 0, 2, 1, 0)
>>> Y = YangBaxterGraph(root=(Integer(1),Integer(0),Integer(3),Integer(2),Integer(1),Integer(0)), operators=ops)
>>> Y.root()
(1, 0, 3, 2, 1, 0)
>>> Y = YangBaxterGraph(partition=[Integer(3),Integer(2)])                                  # needs sage.combinat
>>> Y.root()                                                              # needs sage.combinat
(1, 0, 2, 1, 0)

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
ops = [SwapIncreasingOperator(i) for i in range(4)]
Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops)
Y.root()
Y = YangBaxterGraph(root=(0,1,0,2,1,0), operators=ops)
Y.root()
Y = YangBaxterGraph(root=(1,0,3,2,1,0), operators=ops)
Y.root()
Y = YangBaxterGraph(partition=[3,2])                                  # needs sage.combinat
Y.root()                                                              # needs sage.combinat
successors(v)[source]

Return the successors of the vertex v.

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: ops = [SwapIncreasingOperator(i) for i in range(4)]
sage: Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops)
sage: Y.successors(Y.root())
[(1, 2, 0, 1, 0)]
sage: sorted(Y.successors((1, 2, 0, 1, 0)))
[(1, 2, 1, 0, 0), (2, 1, 0, 1, 0)]

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> ops = [SwapIncreasingOperator(i) for i in range(Integer(4))]
>>> Y = YangBaxterGraph(root=(Integer(1),Integer(0),Integer(2),Integer(1),Integer(0)), operators=ops)
>>> Y.successors(Y.root())
[(1, 2, 0, 1, 0)]
>>> sorted(Y.successors((Integer(1), Integer(2), Integer(0), Integer(1), Integer(0))))
[(1, 2, 1, 0, 0), (2, 1, 0, 1, 0)]

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
ops = [SwapIncreasingOperator(i) for i in range(4)]
Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops)
Y.successors(Y.root())
sorted(Y.successors((1, 2, 0, 1, 0)))
vertex_relabelling_dict(v, relabel_operator)[source]

Return a dictionary pairing vertices u of self with the object obtained from v by applying the relabel_operator along a path from the root to u.

Note that the root is paired with v.

INPUT:

  • v – an object

  • relabel_operator – function mapping a vertex and a label to the image of the vertex

OUTPUT: dictionary pairing vertices with the corresponding image of v

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: ops = [SwapIncreasingOperator(i) for i in range(3)]
sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)
sage: def relabel_operator(op, u):
....:     i = op.position()
....:     return u[:i] + u[i:i+2][::-1] + u[i+2:]
sage: Y.vertex_relabelling_dict((1,2,3,4), relabel_operator)
{(0, 2, 1, 0): (1, 2, 3, 4),
 (2, 0, 1, 0): (2, 1, 3, 4),
 (2, 1, 0, 0): (2, 3, 1, 4)}

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> ops = [SwapIncreasingOperator(i) for i in range(Integer(3))]
>>> Y = YangBaxterGraph(root=(Integer(0),Integer(2),Integer(1),Integer(0)), operators=ops)
>>> def relabel_operator(op, u):
...     i = op.position()
...     return u[:i] + u[i:i+Integer(2)][::-Integer(1)] + u[i+Integer(2):]
>>> Y.vertex_relabelling_dict((Integer(1),Integer(2),Integer(3),Integer(4)), relabel_operator)
{(0, 2, 1, 0): (1, 2, 3, 4),
 (2, 0, 1, 0): (2, 1, 3, 4),
 (2, 1, 0, 0): (2, 3, 1, 4)}

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
ops = [SwapIncreasingOperator(i) for i in range(3)]
Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)
def relabel_operator(op, u):
    i = op.position()
    return u[:i] + u[i:i+2][::-1] + u[i+2:]
Y.vertex_relabelling_dict((1,2,3,4), relabel_operator)
vertices(sort=False)[source]

Return the vertices of self.

INPUT:

  • sort – boolean (default: False); whether to sort the vertices

EXAMPLES:

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: ops = [SwapIncreasingOperator(i) for i in range(3)]
sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)
sage: Y.vertices(sort=True)
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]

>>> from sage.all import *
>>> from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
>>> ops = [SwapIncreasingOperator(i) for i in range(Integer(3))]
>>> Y = YangBaxterGraph(root=(Integer(0),Integer(2),Integer(1),Integer(0)), operators=ops)
>>> Y.vertices(sort=True)
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]

from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
ops = [SwapIncreasingOperator(i) for i in range(3)]
Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)
Y.vertices(sort=True)
class sage.combinat.yang_baxter_graph.YangBaxterGraph_partition(partition)[source]

Bases: YangBaxterGraph_generic

A class to model the Yang-Baxter graph of a partition.

The Yang-Baxter graph defined by a partition \([p_1,\dots,p_k]\) is the labelled directed graph with vertex set obtained by bubble-sorting \((p_k-1,p_k-2,\dots,0,\dots,p_1-1,p_1-2,\dots,0)\); there is an arrow from \(u\) to \(v\) labelled by \(i\) if \(v\) is obtained by swapping the \(i\)-th and \((i+1)\)-th elements of \(u\).

Note

This is a lazy implementation: the digraph is only computed when it is needed.

EXAMPLES:

sage: Y = YangBaxterGraph(partition=[3,2,1]); Y                             # needs sage.combinat
Yang-Baxter graph of [3, 2, 1], with top vertex (0, 1, 0, 2, 1, 0)
sage: loads(dumps(Y)) == Y                                                  # needs sage.combinat
True

>>> from sage.all import *
>>> Y = YangBaxterGraph(partition=[Integer(3),Integer(2),Integer(1)]); Y                             # needs sage.combinat
Yang-Baxter graph of [3, 2, 1], with top vertex (0, 1, 0, 2, 1, 0)
>>> loads(dumps(Y)) == Y                                                  # needs sage.combinat
True

Y = YangBaxterGraph(partition=[3,2,1]); Y                             # needs sage.combinat
loads(dumps(Y)) == Y                                                  # needs sage.combinat

AUTHORS:

  • Franco Saliola (2009-04-23)

relabel_vertices(v, inplace=True)[source]

Relabel the vertices of self with the object obtained from v by applying the transpositions corresponding to the edge labels along some path from the root to the vertex.

INPUT:

  • v – tuple, Permutation, etc.

  • inplace – if True, modifies self; otherwise returns a modified copy of self

EXAMPLES:

sage: # needs sage.combinat
sage: Y = YangBaxterGraph(partition=[3,1]); Y
Yang-Baxter graph of [3, 1], with top vertex (0, 2, 1, 0)
sage: d = Y.relabel_vertices((1,2,3,4), inplace=False); d
Digraph on 3 vertices
sage: Y.vertices(sort=True)
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]
sage: e = Y.relabel_vertices((1,2,3,4)); e
sage: Y.vertices(sort=True)
[(1, 2, 3, 4), (2, 1, 3, 4), (2, 3, 1, 4)]

>>> from sage.all import *
>>> # needs sage.combinat
>>> Y = YangBaxterGraph(partition=[Integer(3),Integer(1)]); Y
Yang-Baxter graph of [3, 1], with top vertex (0, 2, 1, 0)
>>> d = Y.relabel_vertices((Integer(1),Integer(2),Integer(3),Integer(4)), inplace=False); d
Digraph on 3 vertices
>>> Y.vertices(sort=True)
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]
>>> e = Y.relabel_vertices((Integer(1),Integer(2),Integer(3),Integer(4))); e
>>> Y.vertices(sort=True)
[(1, 2, 3, 4), (2, 1, 3, 4), (2, 3, 1, 4)]

# needs sage.combinat
Y = YangBaxterGraph(partition=[3,1]); Y
d = Y.relabel_vertices((1,2,3,4), inplace=False); d
Y.vertices(sort=True)
e = Y.relabel_vertices((1,2,3,4)); e
Y.vertices(sort=True)
vertex_relabelling_dict(v)[source]

Return a dictionary pairing vertices u of self with the object obtained from v by applying transpositions corresponding to the edges labels along a path from the root to u.

Note that the root is paired with v.

INPUT:

  • v – an object

OUTPUT: dictionary pairing vertices with the corresponding image of v

EXAMPLES:

sage: Y = YangBaxterGraph(partition=[3,1])                                  # needs sage.combinat
sage: Y.vertex_relabelling_dict((1,2,3,4))                                  # needs sage.combinat
{(0, 2, 1, 0): (1, 2, 3, 4),
 (2, 0, 1, 0): (2, 1, 3, 4),
 (2, 1, 0, 0): (2, 3, 1, 4)}
sage: Y.vertex_relabelling_dict((4,3,2,1))                                  # needs sage.combinat
{(0, 2, 1, 0): (4, 3, 2, 1),
 (2, 0, 1, 0): (3, 4, 2, 1),
 (2, 1, 0, 0): (3, 2, 4, 1)}

>>> from sage.all import *
>>> Y = YangBaxterGraph(partition=[Integer(3),Integer(1)])                                  # needs sage.combinat
>>> Y.vertex_relabelling_dict((Integer(1),Integer(2),Integer(3),Integer(4)))                                  # needs sage.combinat
{(0, 2, 1, 0): (1, 2, 3, 4),
 (2, 0, 1, 0): (2, 1, 3, 4),
 (2, 1, 0, 0): (2, 3, 1, 4)}
>>> Y.vertex_relabelling_dict((Integer(4),Integer(3),Integer(2),Integer(1)))                                  # needs sage.combinat
{(0, 2, 1, 0): (4, 3, 2, 1),
 (2, 0, 1, 0): (3, 4, 2, 1),
 (2, 1, 0, 0): (3, 2, 4, 1)}

Y = YangBaxterGraph(partition=[3,1])                                  # needs sage.combinat
Y.vertex_relabelling_dict((1,2,3,4))                                  # needs sage.combinat
Y.vertex_relabelling_dict((4,3,2,1))                                  # needs sage.combinat