Yang-Baxter Graphs

class sage.combinat.yang_baxter_graph.SwapIncreasingOperator(i)

Bases: sage.combinat.yang_baxter_graph.SwapOperator

class sage.combinat.yang_baxter_graph.SwapOperator(i)

Bases: sage.structure.sage_object.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
position()

self is the operator that swaps positions i and i+1. This method returns i.

EXAMPLES:

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

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:

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

The partition keyword is a shorthand for the above construction:

sage: Y = YangBaxterGraph(partition=[3,1]); Y
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)]

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()
Graphics object consisting of 97 graphics primitives

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

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)
Graphics object consisting of 9 graphics primitives

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)
Graphics object consisting of 96 graphics primitives

AUTHORS:

  • Franco Saliola (2009-04-23)
class sage.combinat.yang_baxter_graph.YangBaxterGraph_generic(root, operators)

Bases: sage.structure.sage_object.SageObject

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

INPUT:

  • root – the root vertex of the graph
  • operators – a 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

AUTHORS:

  • Franco Saliola (2009-04-23)
edges()

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)]
plot(*args, **kwds)

Plots 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()
Graphics object consisting of 16 graphics primitives
sage: Y.plot(edge_labels=False)
Graphics object consisting of 11 graphics primitives
relabel_edges(edge_dict, inplace=True)

Relabel the edges of self.

INPUT:

  • edge_dict – a 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)]
relabel_vertices(v, relabel_operator, inplace=True)

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, CombinatorialObject
  • 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)]
root()

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])
sage: Y.root()
(1, 0, 2, 1, 0)
successors(v)

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: Y.successors((1, 2, 0, 1, 0))
[(1, 2, 1, 0, 0), (2, 1, 0, 1, 0)]
vertex_relabelling_dict(v, relabel_operator)

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)}
vertices(sort=False)

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)]
class sage.combinat.yang_baxter_graph.YangBaxterGraph_partition(partition)

Bases: sage.combinat.yang_baxter_graph.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
Yang-Baxter graph of [3, 2, 1], with top vertex (0, 1, 0, 2, 1, 0)
sage: loads(dumps(Y)) == Y
True

AUTHORS:

  • Franco Saliola (2009-04-23)
relabel_vertices(v, inplace=True)

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, CombinatorialObject
  • inplace – if True, modifies self; otherwise returns a modified copy of self.

EXAMPLES:

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()
[(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()
[(1, 2, 3, 4), (2, 1, 3, 4), (2, 3, 1, 4)]
vertex_relabelling_dict(v)

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])
sage: Y.vertex_relabelling_dict((1,2,3,4))
{(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))
{(0, 2, 1, 0): (4, 3, 2, 1),
 (2, 0, 1, 0): (3, 4, 2, 1),
 (2, 1, 0, 0): (3, 2, 4, 1)}