Yang-Baxter Graphs

class sage.combinat.yang_baxter_graph.SwapIncreasingOperator(i)

Bases: SwapOperator

class sage.combinat.yang_baxter_graph.SwapOperator(i)

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

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:

• Either:

  • YangBaxterGraph_partition - if partition is defined

  • YangBaxterGraph_generic - if partition is None

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

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()
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, …

• 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: sorted(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: 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, …

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

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