Knutson-Tao Puzzles¶

This module implements a generic algorithm to solve Knutson-Tao puzzles. An instance of this class will be callable: the arguments are the labels of north-east and north-west sides of the puzzle boundary; the output is the list of the fillings of the puzzle with the specified pieces.

Acknowledgements¶

This code was written during Sage Days 45 at ICERM with Franco Saliola, Anne Schilling, and Avinash Dalal in discussions with Allen Knutson. The code was tested afterwards by Liz Beazley and Ed Richmond.

Todo

Functionality to add:

plotter will not plot edge labels higher than 2; e.g. in BK puzzles, the labels are 1,…, n and so in 3-step examples, none of the edge labels with 3 appear
we should also have a 3-step puzzle pieces constructor, taken from p22 of arXiv math/0610538
implement the bijection from puzzles to tableaux; see for example R. Vakil, A geometric Littlewood-Richardson rule, arXiv math/0302294 or K. Purbhoo, Puzzles, Tableaux and Mosaics, arXiv 0705.1184.

sage.combinat.knutson_tao_puzzles.BK_pieces(max_letter)¶

The puzzle pieces used in computing the Belkale-Kumar coefficients for any partial flag variety in type \(A\).

There are two types of puzzle pieces:

a triangle, with each edge labeled with the same letter;
a rhombus, with edges labeled \(i\), \(j\), \(i\), \(j\) in clockwise order with \(i > j\).

Each of these is rotated by 60 degrees, but not reflected.

We model the rhombus pieces as two triangles: a delta piece north-west label \(i\), north-east label \(j\) and south label \(i(j)\); and a nabla piece with south-east label \(i\), south-west label \(j\) and north label \(i(j)\).

INPUT:

max_letter – positive integer specifying the number of steps in the partial flag variety, equivalently, the number of elements in the alphabet for the edge labels. The smallest label is \(1\).

REFERENCES:

KnutsonPurbhoo10: A. Knutson, K. Purbhoo, Product and puzzle formulae for \(GL_n\) Belkale-Kumar coefficients, arXiv 1008.4979

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import BK_pieces
sage: BK_pieces(3)
Nablas : [1\1/1, 1\2(1)/2, 1\3(1)/3, 2(1)\2/1, 2\1/2(1), 2\2/2, 2\3(2)/3, 3(1)\3/1, 3(2)\3/2, 3\1/3(1), 3\2/3(2), 3\3/3]
Deltas : [1/1\1, 1/2\2(1), 1/3\3(1), 2(1)/1\2, 2/2(1)\1, 2/2\2, 2/3\3(2), 3(1)/1\3, 3(2)/2\3, 3/3(1)\1, 3/3(2)\2, 3/3\3]

class sage.combinat.knutson_tao_puzzles.DeltaPiece(south, north_west, north_east)¶

Bases: sage.combinat.knutson_tao_puzzles.PuzzlePiece

Delta Piece takes as input three labels, inputted as strings. They label the South, Northwest and Northeast edges, respectively.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece
sage: DeltaPiece('a','b','c')
b/a\c

clockwise_rotation()¶

Rotate the Delta piece by 120 degree clockwise.

OUTPUT:

Delta piece

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece
sage: delta = DeltaPiece('1','2','3')
sage: delta.clockwise_rotation()
1/3\2

edges()¶

Return the tuple of edge names.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece
sage: delta = DeltaPiece('1','2','3')
sage: delta.edges()
('south', 'north_west', 'north_east')

half_turn_rotation()¶

Rotate the Delta piece by 180 degree.

OUTPUT:

Nabla piece

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece
sage: delta = DeltaPiece('1','2','3')
sage: delta.half_turn_rotation()
3\1/2

sage.combinat.knutson_tao_puzzles.HT_grassmannian_pieces()¶

Define the puzzle pieces used in computing the torus-equivariant cohomology of the Grassmannian.

REFERENCES:

KT2003: Allen Knutson, Terence Tao, Puzzles and (equivariant) cohomology of Grassmannians, Duke Math. J. 119 (2003) 221

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import HT_grassmannian_pieces
sage: HT_grassmannian_pieces()
Nablas : [0\0/0, 0\10/1, 10\1/0, 1\0/10, 1\1/1, 1\T0|1/0]
Deltas : [0/0\0, 0/1\10, 0/T0|1\1, 1/10\0, 1/1\1, 10/0\1]

sage.combinat.knutson_tao_puzzles.HT_two_step_pieces()¶

Define the puzzle pieces used in computing the equivariant two step puzzle pieces.

For the puzzle pieces, see Figure 26 on page 22 of [CoskunVakil06].

REFERENCES:

CoskunVakil06: I. Coskun, R. Vakil, Geometric positivity in the cohomology of homogeneous spaces and generalized Schubert calculus, arXiv math/0610538

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import HT_two_step_pieces
sage: HT_two_step_pieces()
Nablas : [(21)0\21/0, 0\(21)0/21, 0\0/0, 0\10/1, 0\20/2, 10\1/0, 10\2(10)/2,
1\0/10, 1\1/1, 1\21/2, 1\T0|1/0, 2(10)\2/10, 20\2/0, 21\0/(21)0, 21\2/1, 21\T0|21/0,
21\T10|21/10, 2\0/20, 2\1/21, 2\10/2(10), 2\2/2, 2\T0|2/0, 2\T10|2/10, 2\T1|2/1]
Deltas : [(21)0/0\21, 0/0\0, 0/1\10, 0/21\(21)0, 0/2\20, 0/T0|1\1, 0/T0|21\21, 0/T0|2\2,
1/10\0, 1/1\1, 1/2\21, 1/T1|2\2, 10/0\1, 10/2\2(10), 10/T10|21\21, 10/T10|2\2, 2(10)/10\2,
2/2(10)\10, 2/20\0, 2/21\1, 2/2\2, 20/0\2, 21/(21)0\0, 21/1\2]

sage.combinat.knutson_tao_puzzles.H_grassmannian_pieces()¶

Define the puzzle pieces used in computing the cohomology of the Grassmannian.

REFERENCES:

KTW: Allen Knutson, Terence Tao, Christopher Woodward, The honeycomb model of GL(n) tensor products II: Puzzles determine facets of the Littlewood-Richardson cone, arXiv math/0107011

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import H_grassmannian_pieces
sage: H_grassmannian_pieces()
Nablas : [0\0/0, 0\10/1, 10\1/0, 1\0/10, 1\1/1]
Deltas : [0/0\0, 0/1\10, 1/10\0, 1/1\1, 10/0\1]

sage.combinat.knutson_tao_puzzles.H_two_step_pieces()¶

Define the puzzle pieces used in two step flags.

This rule is currently only conjecturally true. See [BuchKreschTamvakis03].

REFERENCES:

BuchKreschTamvakis03: A. Buch, A. Kresch, H. Tamvakis, Gromov-Witten invariants on Grassmannian, arXiv math/0306388

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import H_two_step_pieces
sage: H_two_step_pieces()
Nablas : [(21)0\21/0, 0\(21)0/21, 0\0/0, 0\10/1, 0\20/2, 10\1/0, 10\2(10)/2, 1\0/10, 1\1/1, 1\21/2,
2(10)\2/10, 20\2/0, 21\0/(21)0, 21\2/1, 2\0/20, 2\1/21, 2\10/2(10), 2\2/2]
Deltas : [(21)0/0\21, 0/0\0, 0/1\10, 0/21\(21)0, 0/2\20, 1/10\0, 1/1\1, 1/2\21, 10/0\1, 10/2\2(10),
2(10)/10\2, 2/2(10)\10, 2/20\0, 2/21\1, 2/2\2, 20/0\2, 21/(21)0\0, 21/1\2]

sage.combinat.knutson_tao_puzzles.K_grassmannian_pieces()¶

Define the puzzle pieces used in computing the K-theory of the Grassmannian.

REFERENCES:

Buch00: A. Buch, A Littlewood-Richardson rule for the K-theory of Grassmannians, arXiv math.AG/0004137

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import K_grassmannian_pieces
sage: K_grassmannian_pieces()
Nablas : [0\0/0, 0\10/1, 0\K/1, 10\1/0, 1\0/10, 1\0/K, 1\1/1, K\1/0]
Deltas : [0/0\0, 0/1\10, 1/10\0, 1/1\1, 10/0\1, K/K\K]

class sage.combinat.knutson_tao_puzzles.KnutsonTaoPuzzleSolver(puzzle_pieces)¶

Bases: sage.structure.unique_representation.UniqueRepresentation

Return puzzle solver function used to create all puzzles with given boundary conditions.

This class implements a generic algorithm to solve Knutson-Tao puzzles. An instance of this class will be callable: the arguments are the labels of north-east and north-west sides of the puzzle boundary; the output is the list of the fillings of the puzzle with the specified pieces.

INPUT:

puzzle_pieces – takes either a collection of puzzle pieces or a string indicating a pre-programmed collection of puzzle pieces:
- H – cohomology of the Grassmannian
- HT – equivariant cohomology of the Grassmannian
- K – K-theory
- H2step – cohomology of the 2-step Grassmannian
- HT2step – equivariant cohomology of the 2-step Grassmannian
- BK – Belkale-Kumar puzzle pieces
max_letter – (default: None) None or a positive integer. This is only required only for Belkale-Kumar puzzles.

EXAMPLES:

Each puzzle piece is an edge-labelled triangle oriented in such a way that it has a south edge (called a delta piece) or a north edge (called a nabla piece). For example, the puzzle pieces corresponding to the cohomology of the Grassmannian are the following:

sage: from sage.combinat.knutson_tao_puzzles import H_grassmannian_pieces
sage: H_grassmannian_pieces()
Nablas : [0\0/0, 0\10/1, 10\1/0, 1\0/10, 1\1/1]
Deltas : [0/0\0, 0/1\10, 1/10\0, 1/1\1, 10/0\1]

In the string representation, the nabla pieces are depicted as c\a/b, where \(a\) is the label of the north edge, \(b\) is the label of the south-east edge, \(c\) is the label of the south-west edge. A similar string representation exists for the delta pieces.

To create a puzzle solver, one specifies a collection of puzzle pieces:

sage: KnutsonTaoPuzzleSolver(H_grassmannian_pieces())
Knutson-Tao puzzle solver with pieces:
Nablas : [0\0/0, 0\10/1, 10\1/0, 1\0/10, 1\1/1]
Deltas : [0/0\0, 0/1\10, 1/10\0, 1/1\1, 10/0\1]

The following shorthand to create the above puzzle solver is also supported:

sage: KnutsonTaoPuzzleSolver('H')
Knutson-Tao puzzle solver with pieces:
Nablas : [0\0/0, 0\10/1, 10\1/0, 1\0/10, 1\1/1]
Deltas : [0/0\0, 0/1\10, 1/10\0, 1/1\1, 10/0\1]

The solver will compute all fillings of the puzzle with the given puzzle pieces. The user specifies the labels of north-east and north-west sides of the puzzle boundary and the output is a list of the fillings of the puzzle with the specified pieces. For example, there is one solution to the puzzle whose north-west and north-east edges are both labeled ‘0’:

sage: ps = KnutsonTaoPuzzleSolver('H')
sage: ps('0', '0')
[{(1, 1): 0/0\0}]

There are two solutions to the puzzle whose north-west and north-east edges are both labeled ‘0101’:

sage: ps = KnutsonTaoPuzzleSolver('H')
sage: solns = ps('0101', '0101')
sage: len(solns)
2
sage: solns.sort(key=str)
sage: solns
[{(1, 1): 0/0\0,
  (1, 2): 1/\0  0\/1,
  (1, 3): 0/\0  0\/0,
  (1, 4): 1/\0  0\/1,
  (2, 2): 1/1\1,
  (2, 3): 0/\10  1\/1,
  (2, 4): 1/\1  10\/0,
  (3, 3): 1/1\1,
  (3, 4): 0/\0  1\/10,
  (4, 4): 10/0\1}, {(1, 1): 0/1\10,
  (1, 2): 1/\1  10\/0,
  (1, 3): 0/\0  1\/10,
  (1, 4): 1/\0  0\/1,
  (2, 2): 0/0\0,
  (2, 3): 10/\1  0\/0,
  (2, 4): 1/\1  1\/1,
  (3, 3): 0/0\0,
  (3, 4): 1/\0  0\/1,
  (4, 4): 1/1\1}]

The pieces in a puzzle filling are indexed by pairs of non-negative integers \((i, j)\) with \(1 \leq i \leq j \leq n\), where \(n\) is the length of the word labelling the triangle edge. The pieces indexed by \((i, i)\) are the triangles along the south edge of the puzzle.

sage: f = solns[0]
sage: [f[i, i] for i in range(1,5)]
[0/0\0, 1/1\1, 1/1\1, 10/0\1]

The pieces indexed by \((i, j)\) for \(j > i\) are a pair consisting of a delta piece and nabla piece glued together along the south edge and north edge, respectively (these pairs are called rhombi).

sage: f = solns[0]
sage: f[1, 2]
1/\0  0\/1

There are various methods and options to display puzzle solutions. A single puzzle can be displayed using the plot method of the puzzle:

sage: ps = KnutsonTaoPuzzleSolver("H")
sage: puzzle = ps('0101','1001')[0]
sage: puzzle.plot()  #not tested
sage: puzzle.plot(style='fill')  #not tested
sage: puzzle.plot(style='edges')  #not tested

To plot several puzzle solutions, use the plot method of the puzzle solver:

sage: ps = KnutsonTaoPuzzleSolver('K')
sage: solns = ps('0101', '0101')
sage: ps.plot(solns)        # not tested

The code can also generate a PDF of a puzzle (using LaTeX and tikz):

sage: latex.extra_preamble(r'''\usepackage{tikz}''')
sage: ps = KnutsonTaoPuzzleSolver('H')
sage: solns = ps('0101', '0101')
sage: view(solns[0], viewer='pdf')  # not tested

Below are examples of using each of the currently supported puzzles.

Cohomology of the Grassmannian:

sage: ps = KnutsonTaoPuzzleSolver("H")
sage: solns = ps('0101', '0101')
sage: sorted(solns, key=str)
[{(1, 1): 0/0\0,
  (1, 2): 1/\0  0\/1,
  (1, 3): 0/\0  0\/0,
  (1, 4): 1/\0  0\/1,
  (2, 2): 1/1\1,
  (2, 3): 0/\10  1\/1,
  (2, 4): 1/\1  10\/0,
  (3, 3): 1/1\1,
  (3, 4): 0/\0  1\/10,
  (4, 4): 10/0\1}, {(1, 1): 0/1\10,
  (1, 2): 1/\1  10\/0,
  (1, 3): 0/\0  1\/10,
  (1, 4): 1/\0  0\/1,
  (2, 2): 0/0\0,
  (2, 3): 10/\1  0\/0,
  (2, 4): 1/\1  1\/1,
  (3, 3): 0/0\0,
  (3, 4): 1/\0  0\/1,
  (4, 4): 1/1\1}]

Equivariant puzzles:

sage: ps = KnutsonTaoPuzzleSolver("HT")
sage: solns = ps('0101', '0101')
sage: sorted(solns, key=str)
[{(1, 1): 0/0\0,
  (1, 2): 1/\0  0\/1,
  (1, 3): 0/\0  0\/0,
  (1, 4): 1/\0  0\/1,
  (2, 2): 1/1\1,
  (2, 3): 0/\1  1\/0,
  (2, 4): 1/\1  1\/1,
  (3, 3): 0/0\0,
  (3, 4): 1/\0  0\/1,
  (4, 4): 1/1\1}, {(1, 1): 0/0\0,
  (1, 2): 1/\0  0\/1,
  (1, 3): 0/\0  0\/0,
  (1, 4): 1/\0  0\/1,
  (2, 2): 1/1\1,
  (2, 3): 0/\10  1\/1,
  (2, 4): 1/\1  10\/0,
  (3, 3): 1/1\1,
  (3, 4): 0/\0  1\/10,
  (4, 4): 10/0\1}, {(1, 1): 0/1\10,
  (1, 2): 1/\1  10\/0,
  (1, 3): 0/\0  1\/10,
  (1, 4): 1/\0  0\/1,
  (2, 2): 0/0\0,
  (2, 3): 10/\1  0\/0,
  (2, 4): 1/\1  1\/1,
  (3, 3): 0/0\0,
  (3, 4): 1/\0  0\/1,
  (4, 4): 1/1\1}]

K-Theory puzzles:

sage: ps = KnutsonTaoPuzzleSolver("K")
sage: solns = ps('0101', '0101')
sage: sorted(solns, key=str)
[{(1, 1): 0/0\0,
  (1, 2): 1/\0  0\/1,
  (1, 3): 0/\0  0\/0,
  (1, 4): 1/\0  0\/1,
  (2, 2): 1/1\1,
  (2, 3): 0/\10  1\/1,
  (2, 4): 1/\1  10\/0,
  (3, 3): 1/1\1,
  (3, 4): 0/\0  1\/10,
  (4, 4): 10/0\1}, {(1, 1): 0/1\10,
  (1, 2): 1/\1  10\/0,
  (1, 3): 0/\0  1\/10,
  (1, 4): 1/\0  0\/1,
  (2, 2): 0/0\0,
  (2, 3): 10/\1  0\/0,
  (2, 4): 1/\1  1\/1,
  (3, 3): 0/0\0,
  (3, 4): 1/\0  0\/1,
  (4, 4): 1/1\1}, {(1, 1): 0/1\10,
  (1, 2): 1/\1  10\/0,
  (1, 3): 0/\0  1\/K,
  (1, 4): 1/\0  0\/1,
  (2, 2): 0/0\0,
  (2, 3): K/\K  0\/1,
  (2, 4): 1/\1  K\/0,
  (3, 3): 1/1\1,
  (3, 4): 0/\0  1\/10,
  (4, 4): 10/0\1}]

Two-step puzzles:

sage: ps = KnutsonTaoPuzzleSolver("H2step")
sage: solns = ps('01201', '01021')
sage: sorted(solns, key=str)
[{(1, 1): 0/0\0,
  (1, 2): 1/\0  0\/1,
  (1, 3): 2/\0  0\/2,
  (1, 4): 0/\0  0\/0,
  (1, 5): 1/\0  0\/1,
  (2, 2): 1/2\21,
  (2, 3): 2/\2  21\/1,
  (2, 4): 0/\10  2\/21,
  (2, 5): 1/\1  10\/0,
  (3, 3): 1/1\1,
  (3, 4): 21/\2  1\/1,
  (3, 5): 0/\0  2\/20,
  (4, 4): 1/1\1,
  (4, 5): 20/\2  1\/10,
  (5, 5): 10/0\1}, {(1, 1): 0/1\10,
  (1, 2): 1/\1  10\/0,
  (1, 3): 2/\1  1\/2,
  (1, 4): 0/\0  1\/10,
  (1, 5): 1/\0  0\/1,
  (2, 2): 0/2\20,
  (2, 3): 2/\2  20\/0,
  (2, 4): 10/\1  2\/20,
  (2, 5): 1/\1  1\/1,
  (3, 3): 0/0\0,
  (3, 4): 20/\2  0\/0,
  (3, 5): 1/\0  2\/2(10),
  (4, 4): 0/0\0,
  (4, 5): 2(10)/\2  0\/1,
  (5, 5): 1/1\1}, {(1, 1): 0/2\20,
  (1, 2): 1/\21  20\/0,
  (1, 3): 2/\2  21\/1,
  (1, 4): 0/\0  2\/20,
  (1, 5): 1/\0  0\/1,
  (2, 2): 0/0\0,
  (2, 3): 1/\0  0\/1,
  (2, 4): 20/\2  0\/0,
  (2, 5): 1/\1  2\/21,
  (3, 3): 1/1\1,
  (3, 4): 0/\0  1\/10,
  (3, 5): 21/\0  0\/21,
  (4, 4): 10/0\1,
  (4, 5): 21/\2  1\/1,
  (5, 5): 1/1\1}]

Two-step equivariant puzzles:

sage: ps = KnutsonTaoPuzzleSolver("HT2step")
sage: solns = ps('10212', '12012')
sage: sorted(solns, key=str)
[{(1, 1): 1/1\1,
  (1, 2): 0/\(21)0  1\/2,
  (1, 3): 2/\1  (21)0\/0,
  (1, 4): 1/\1  1\/1,
  (1, 5): 2/\1  1\/2,
  (2, 2): 2/2\2,
  (2, 3): 0/\2  2\/0,
  (2, 4): 1/\2  2\/1,
  (2, 5): 2/\2  2\/2,
  (3, 3): 0/0\0,
  (3, 4): 1/\0  0\/1,
  (3, 5): 2/\0  0\/2,
  (4, 4): 1/1\1,
  (4, 5): 2/\1  1\/2,
  (5, 5): 2/2\2}, {(1, 1): 1/1\1,
  (1, 2): 0/\(21)0  1\/2,
  (1, 3): 2/\1  (21)0\/0,
  (1, 4): 1/\1  1\/1,
  (1, 5): 2/\1  1\/2,
  (2, 2): 2/2\2,
  (2, 3): 0/\2  2\/0,
  (2, 4): 1/\21  2\/2,
  (2, 5): 2/\2  21\/1,
  (3, 3): 0/0\0,
  (3, 4): 2/\0  0\/2,
  (3, 5): 1/\0  0\/1,
  (4, 4): 2/2\2,
  (4, 5): 1/\1  2\/21,
  (5, 5): 21/1\2}, {(1, 1): 1/1\1,
  (1, 2): 0/\(21)0  1\/2,
  (1, 3): 2/\1  (21)0\/0,
  (1, 4): 1/\1  1\/1,
  (1, 5): 2/\1  1\/2,
  (2, 2): 2/2\2,
  (2, 3): 0/\20  2\/2,
  (2, 4): 1/\21  20\/0,
  (2, 5): 2/\2  21\/1,
  (3, 3): 2/2\2,
  (3, 4): 0/\0  2\/20,
  (3, 5): 1/\0  0\/1,
  (4, 4): 20/0\2,
  (4, 5): 1/\1  2\/21,
  (5, 5): 21/1\2}, {(1, 1): 1/1\1,
  (1, 2): 0/\1  1\/0,
  (1, 3): 2/\1  1\/2,
  (1, 4): 1/\1  1\/1,
  (1, 5): 2/\1  1\/2,
  (2, 2): 0/2\20,
  (2, 3): 2/\2  20\/0,
  (2, 4): 1/\2  2\/1,
  (2, 5): 2/\2  2\/2,
  (3, 3): 0/0\0,
  (3, 4): 1/\0  0\/1,
  (3, 5): 2/\0  0\/2,
  (4, 4): 1/1\1,
  (4, 5): 2/\1  1\/2,
  (5, 5): 2/2\2}, {(1, 1): 1/1\1,
  (1, 2): 0/\1  1\/0,
  (1, 3): 2/\1  1\/2,
  (1, 4): 1/\1  1\/1,
  (1, 5): 2/\1  1\/2,
  (2, 2): 0/2\20,
  (2, 3): 2/\2  20\/0,
  (2, 4): 1/\21  2\/2,
  (2, 5): 2/\2  21\/1,
  (3, 3): 0/0\0,
  (3, 4): 2/\0  0\/2,
  (3, 5): 1/\0  0\/1,
  (4, 4): 2/2\2,
  (4, 5): 1/\1  2\/21,
  (5, 5): 21/1\2}, {(1, 1): 1/1\1,
  (1, 2): 0/\10  1\/1,
  (1, 3): 2/\10  10\/2,
  (1, 4): 1/\1  10\/0,
  (1, 5): 2/\1  1\/2,
  (2, 2): 1/2\21,
  (2, 3): 2/\2  21\/1,
  (2, 4): 0/\2  2\/0,
  (2, 5): 2/\2  2\/2,
  (3, 3): 1/1\1,
  (3, 4): 0/\0  1\/10,
  (3, 5): 2/\0  0\/2,
  (4, 4): 10/0\1,
  (4, 5): 2/\1  1\/2,
  (5, 5): 2/2\2}, {(1, 1): 1/1\1,
  (1, 2): 0/\10  1\/1,
  (1, 3): 2/\10  10\/2,
  (1, 4): 1/\1  10\/0,
  (1, 5): 2/\1  1\/2,
  (2, 2): 1/2\21,
  (2, 3): 2/\2  21\/1,
  (2, 4): 0/\20  2\/2,
  (2, 5): 2/\2  20\/0,
  (3, 3): 1/1\1,
  (3, 4): 2/\1  1\/2,
  (3, 5): 0/\0  1\/10,
  (4, 4): 2/2\2,
  (4, 5): 10/\1  2\/20,
  (5, 5): 20/0\2}, {(1, 1): 1/2\21,
  (1, 2): 0/\20  21\/1,
  (1, 3): 2/\2  20\/0,
  (1, 4): 1/\1  2\/21,
  (1, 5): 2/\1  1\/2,
  (2, 2): 1/1\1,
  (2, 3): 0/\1  1\/0,
  (2, 4): 21/\2  1\/1,
  (2, 5): 2/\2  2\/2,
  (3, 3): 0/0\0,
  (3, 4): 1/\0  0\/1,
  (3, 5): 2/\0  0\/2,
  (4, 4): 1/1\1,
  (4, 5): 2/\1  1\/2,
  (5, 5): 2/2\2}, {(1, 1): 1/2\21,
  (1, 2): 0/\20  21\/1,
  (1, 3): 2/\2  20\/0,
  (1, 4): 1/\1  2\/21,
  (1, 5): 2/\1  1\/2,
  (2, 2): 1/1\1,
  (2, 3): 0/\10  1\/1,
  (2, 4): 21/\2  10\/0,
  (2, 5): 2/\2  2\/2,
  (3, 3): 1/1\1,
  (3, 4): 0/\0  1\/10,
  (3, 5): 2/\0  0\/2,
  (4, 4): 10/0\1,
  (4, 5): 2/\1  1\/2,
  (5, 5): 2/2\2}, {(1, 1): 1/2\21,
  (1, 2): 0/\21  21\/0,
  (1, 3): 2/\2  21\/1,
  (1, 4): 1/\1  2\/21,
  (1, 5): 2/\1  1\/2,
  (2, 2): 0/1\10,
  (2, 3): 1/\1  10\/0,
  (2, 4): 21/\2  1\/1,
  (2, 5): 2/\2  2\/2,
  (3, 3): 0/0\0,
  (3, 4): 1/\0  0\/1,
  (3, 5): 2/\0  0\/2,
  (4, 4): 1/1\1,
  (4, 5): 2/\1  1\/2,
  (5, 5): 2/2\2}]

Belkale-Kumar puzzles (the following example is Figure 2 of [KnutsonPurbhoo10]):

sage: ps = KnutsonTaoPuzzleSolver('BK', 3)
sage: solns = ps('12132', '23112')
sage: len(solns)
1
sage: solns[0].south_labels()
('3', '2', '1', '2', '1')
sage: solns
[{(1, 1): 1/3\3(1),
  (1, 2): 2/\3(2)  3(1)\/1,
  (1, 3): 1/\3(1)  3(2)\/2,
  (1, 4): 3/\3  3(1)\/1,
  (1, 5): 2/\2  3\/3(2),
  (2, 2): 1/2\2(1),
  (2, 3): 2/\2  2(1)\/1,
  (2, 4): 1/\2(1)  2\/2,
  (2, 5): 3(2)/\3  2(1)\/1,
  (3, 3): 1/1\1,
  (3, 4): 2/\1  1\/2,
  (3, 5): 1/\1  1\/1,
  (4, 4): 2/2\2,
  (4, 5): 1/\1  2\/2(1),
  (5, 5): 2(1)/1\2}]

plot(puzzles)¶

Return plot of puzzles.

INPUT:

puzzles – list of puzzles

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import KnutsonTaoPuzzleSolver
sage: ps = KnutsonTaoPuzzleSolver('K')
sage: solns = ps('0101', '0101')
sage: ps.plot(solns)        # not tested

puzzle_pieces()¶

The puzzle pieces used for filling in the puzzles.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import KnutsonTaoPuzzleSolver
sage: ps = KnutsonTaoPuzzleSolver('H')
sage: ps.puzzle_pieces()
Nablas : [0\0/0, 0\10/1, 10\1/0, 1\0/10, 1\1/1]
Deltas : [0/0\0, 0/1\10, 1/10\0, 1/1\1, 10/0\1]

solutions(lamda, mu, algorithm='strips')¶

structure_constants(lamda, mu, nu=None)¶

Compute cohomology structure coefficients from puzzles.

INPUT:

pieces – puzzle pieces to be used
lambda, mu – edge labels of puzzle for northwest and north east side
nu – (default: None) If nu is not specified a dictionary is returned with the structure coefficients corresponding to all south labels; if nu is given, only the coefficients with the specified label is returned.

OUTPUT: dictionary

EXAMPLES:

Note: In order to standardize the output of the following examples, we output a sorted list of items from the dictionary instead of the dictionary itself.

Grassmannian cohomology:

sage: ps = KnutsonTaoPuzzleSolver('H')
sage: cp = ps.structure_constants('0101', '0101')
sage: sorted(cp.items(), key=str)
[(('0', '1', '1', '0'), 1), (('1', '0', '0', '1'), 1)]
sage: ps.structure_constants('001001', '001010', '010100')
1

Equivariant cohomology:

sage: ps = KnutsonTaoPuzzleSolver('HT')
sage: cp = ps.structure_constants('0101', '0101')
sage: sorted(cp.items(), key=str)
[(('0', '1', '0', '1'), y2 - y3),
(('0', '1', '1', '0'), 1),
(('1', '0', '0', '1'), 1)]

K-theory:

sage: ps = KnutsonTaoPuzzleSolver('K')
sage: cp = ps.structure_constants('0101', '0101')
sage: sorted(cp.items(), key=str)
[(('0', '1', '1', '0'), 1), (('1', '0', '0', '1'), 1), (('1', '0', '1', '0'), -1)]

Two-step:

sage: ps = KnutsonTaoPuzzleSolver('H2step')
sage: cp = ps.structure_constants('01122', '01122')
sage: sorted(cp.items(), key=str)
[(('0', '1', '1', '2', '2'), 1)]
sage: cp = ps.structure_constants('01201', '01021')
sage: sorted(cp.items(), key=str)
[(('0', '2', '1', '1', '0'), 1),
 (('1', '2', '0', '0', '1'), 1),
 (('2', '0', '1', '0', '1'), 1)]

Two-step equivariant:

sage: ps = KnutsonTaoPuzzleSolver('HT2step')
sage: cp = ps.structure_constants('10212', '12012')
sage: sorted(cp.items(), key=str)
[(('1', '2', '0', '1', '2'), y1*y2 - y2*y3 - y1*y4 + y3*y4),
 (('1', '2', '0', '2', '1'), y1 - y3),
 (('1', '2', '1', '0', '2'), y2 - y4),
 (('1', '2', '1', '2', '0'), 1),
 (('1', '2', '2', '0', '1'), 1),
 (('2', '1', '0', '1', '2'), y1 - y3),
 (('2', '1', '1', '0', '2'), 1)]

class sage.combinat.knutson_tao_puzzles.NablaPiece(north, south_east, south_west)¶

Bases: sage.combinat.knutson_tao_puzzles.PuzzlePiece

Nabla Piece takes as input three labels, inputted as strings. They label the North, Southeast and Southwest edges, respectively.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import NablaPiece
sage: NablaPiece('a','b','c')
c\a/b

clockwise_rotation()¶

Rotate the Nabla piece by 120 degree clockwise.

OUTPUT:

Nabla piece

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import NablaPiece
sage: nabla = NablaPiece('1','2','3')
sage: nabla.clockwise_rotation()
2\3/1

edges()¶

Return the tuple of edge names.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import NablaPiece
sage: nabla = NablaPiece('1','2','3')
sage: nabla.edges()
('north', 'south_east', 'south_west')

half_turn_rotation()¶

Rotate the Nabla piece by 180 degree.

OUTPUT:

Delta piece

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import NablaPiece
sage: nabla = NablaPiece('1','2','3')
sage: nabla.half_turn_rotation()
2/1\3

class sage.combinat.knutson_tao_puzzles.PuzzleFilling(north_west_labels, north_east_labels)¶

Bases: object

Create partial puzzles and provides methods to build puzzles from them.

add_piece(piece)¶

Add piece to partial puzzle.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece, PuzzleFilling
sage: piece = DeltaPiece('0','1','0')
sage: P = PuzzleFilling('0101','0101'); P
{}
sage: P.add_piece(piece); P
{(1, 4): 1/0\0}

add_pieces(pieces)¶

Add piece to partial puzzle.

INPUT:

pieces – tuple of pieces

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece, PuzzleFilling
sage: P = PuzzleFilling('0101','0101'); P
{}
sage: piece = DeltaPiece('0','1','0')
sage: pieces = [piece,piece]
sage: P.add_pieces(pieces)
sage: P
{(1, 4): 1/0\0, (2, 4): 1/0\0}

contribution()¶

Return equivariant contributions from self in polynomial ring.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import KnutsonTaoPuzzleSolver
sage: ps = KnutsonTaoPuzzleSolver("HT")
sage: puzzles = ps('0101','1001')
sage: sorted([p.contribution() for p in puzzles], key=str)
[1, y1 - y3]

copy()¶

Return copy of self.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece, PuzzleFilling
sage: piece = DeltaPiece('0','1','0')
sage: P = PuzzleFilling('0101','0101'); P
{}
sage: PP = P.copy()
sage: P.add_piece(piece); P
{(1, 4): 1/0\0}
sage: PP
{}

is_completed()¶

Whether partial puzzle is complete (completely filled) or not.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzleFilling
sage: P = PuzzleFilling('0101','0101')
sage: P.is_completed()
False

sage: from sage.combinat.knutson_tao_puzzles import KnutsonTaoPuzzleSolver
sage: ps = KnutsonTaoPuzzleSolver("H")
sage: puzzle = ps('0101','1001')[0]
sage: puzzle.is_completed()
True

is_in_south_edge()¶

Check whether kink coordinates of partial puzzle is in south corner.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzleFilling
sage: P = PuzzleFilling('0101','0101')
sage: P.is_in_south_edge()
False

kink_coordinates()¶

Provide the coordinates of the kinks.

The kink coordinates are the coordinates up to which the puzzle has already been built. The kink starts in the north corner and then moves down the diagonals as the puzzles is built.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzleFilling
sage: P = PuzzleFilling('0101','0101')
sage: P
{}
sage: P.kink_coordinates()
(1, 4)

north_east_label_of_kink()¶

Return north east label of kink.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzleFilling
sage: P = PuzzleFilling('0101','0101')
sage: P.north_east_label_of_kink()
'0'

north_west_label_of_kink()¶

Return north-west label of kink.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzleFilling
sage: P = PuzzleFilling('0101','0101')
sage: P.north_west_label_of_kink()
'1'

plot(labels=True, style='fill')¶

Plot completed puzzle.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import KnutsonTaoPuzzleSolver
sage: ps = KnutsonTaoPuzzleSolver("H")
sage: puzzle = ps('0101','1001')[0]
sage: puzzle.plot()  #not tested
sage: puzzle.plot(style='fill')  #not tested
sage: puzzle.plot(style='edges')  #not tested

south_labels()¶

Return south labels for completed puzzle.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import KnutsonTaoPuzzleSolver
sage: ps = KnutsonTaoPuzzleSolver("H")
sage: ps('0101','1001')[0].south_labels()
('1', '0', '1', '0')

class sage.combinat.knutson_tao_puzzles.PuzzlePiece¶

Bases: object

Abstract class for puzzle pieces.

This abstract class contains information on how to test equality of puzzle pieces, and sets color and plotting options.

border()¶

Return the border of self.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece
sage: delta = DeltaPiece('a','b','c')
sage: delta.border()
('a', 'b', 'c')

color()¶

Return the color of self.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece
sage: delta = DeltaPiece('a','b','c')
sage: delta.color()
'white'
sage: delta = DeltaPiece('0','0','0')
sage: delta.color()
'red'
sage: delta = DeltaPiece('1','1','1')
sage: delta.color()
'blue'
sage: delta = DeltaPiece('2','2','2')
sage: delta.color()
'green'
sage: delta = DeltaPiece('2','K','2')
sage: delta.color()
'orange'
sage: delta = DeltaPiece('2','T1/2','2')
sage: delta.color()
'yellow'

edge_color(edge)¶

Color of the specified edge of self (to be used when plotting the piece).

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece
sage: delta = DeltaPiece('1','0','10')
sage: delta.edge_color('south')
'blue'
sage: delta.edge_color('north_west')
'red'
sage: delta.edge_color('north_east')
'white'

edge_label(edge)¶

Return the edge label of edge.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece
sage: delta = DeltaPiece('2','K','2')
sage: delta.edge_label('south')
'2'
sage: delta.edge_label('north_east')
'2'
sage: delta.edge_label('north_west')
'K'

class sage.combinat.knutson_tao_puzzles.PuzzlePieces(forbidden_border_labels=None)¶

Bases: object

Construct a valid set of puzzle pieces.

This class constructs the set of valid puzzle pieces. It can take a list of forbidden border labels as input. These labels are forbidden from appearing on the south edge of a puzzle filling. The user can add valid nabla or delta pieces and specify which rotations of these pieces are legal. For example, rotations=0 does not add any additional pieces (only the piece itself), rotations=60 adds six pieces (the pieces and its rotations by 60, 120, 180, 240, 300), etc..

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzlePieces, NablaPiece
sage: forbidden_border_labels = ['10']
sage: pieces = PuzzlePieces(forbidden_border_labels)
sage: pieces.add_piece(NablaPiece('0','0','0'), rotations=60)
sage: pieces.add_piece(NablaPiece('1','1','1'), rotations=60)
sage: pieces.add_piece(NablaPiece('1','0','10'), rotations=60)
sage: pieces
Nablas : [0\0/0, 0\10/1, 10\1/0, 1\0/10, 1\1/1]
Deltas : [0/0\0, 0/1\10, 1/10\0, 1/1\1, 10/0\1]

The user can obtain the list of valid rhombi pieces as follows:

sage: sorted([p for p in pieces.rhombus_pieces()], key=str)
[0/\0  0\/0, 0/\0  1\/10, 0/\10  10\/0, 0/\10  1\/1, 1/\0  0\/1,
1/\1  10\/0, 1/\1  1\/1, 10/\1  0\/0, 10/\1  1\/10]

add_T_piece(label1, label2)¶

Add a nabla and delta piece with label1 and label2.

This method adds a nabla piece with edges label2T``label1``|``label2`` / label1. and a delta piece with edges label1/ T``label1``|``label2`` label2. It also adds T``label1``|``label2`` to the forbidden list.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzlePieces
sage: pieces = PuzzlePieces()
sage: pieces.add_T_piece('1','3')
sage: pieces
Nablas : [3\T1|3/1]
Deltas : [1/T1|3\3]
sage: pieces._forbidden_border_labels
['T1|3']

add_forbidden_label(label)¶

Add forbidden border labels.

INPUT:

label – string specifying a new forbidden label

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzlePieces
sage: pieces = PuzzlePieces()
sage: pieces.add_forbidden_label('1')
sage: pieces._forbidden_border_labels
['1']
sage: pieces.add_forbidden_label('2')
sage: pieces._forbidden_border_labels
['1', '2']

add_piece(piece, rotations=120)¶

Add piece to the list of pieces.

INPUT:

piece – a nabla piece or a delta piece
rotations – (default: 120) 0, 60, 120, 180

The user can add valid nabla or delta pieces and specify which rotations of these pieces are legal. For example, rotations=0 does not add any additional pieces (only the piece itself), rotations=60 adds six pieces (namely three delta and three nabla pieces), while rotations=120 adds only delta or nabla (depending on which piece self is). rotations=180 adds the piece and its 180 degree rotation, i.e. one delta and one nabla piece.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzlePieces, DeltaPiece
sage: delta = DeltaPiece('a','b','c')
sage: pieces = PuzzlePieces()
sage: pieces
Nablas : []
Deltas : []
sage: pieces.add_piece(delta)
sage: pieces
Nablas : []
Deltas : [a/c\b, b/a\c, c/b\a]

sage: pieces = PuzzlePieces()
sage: pieces.add_piece(delta,rotations=0)
sage: pieces
Nablas : []
Deltas : [b/a\c]

sage: pieces = PuzzlePieces()
sage: pieces.add_piece(delta,rotations=60)
sage: pieces
Nablas : [a\b/c, b\c/a, c\a/b]
Deltas : [a/c\b, b/a\c, c/b\a]

boundary_deltas()¶

Return deltas with south edges not in the forbidden list.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzlePieces, DeltaPiece
sage: pieces = PuzzlePieces(['a'])
sage: delta = DeltaPiece('a','b','c')
sage: pieces.add_piece(delta,rotations=60)
sage: sorted([p for p in pieces.boundary_deltas()], key=str)
[a/c\b, c/b\a]

delta_pieces()¶

Return the delta pieces as a set.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzlePieces, DeltaPiece
sage: pieces = PuzzlePieces()
sage: delta = DeltaPiece('a','b','c')
sage: pieces.add_piece(delta,rotations=60)
sage: sorted([p for p in pieces.delta_pieces()], key=str)
[a/c\b, b/a\c, c/b\a]

nabla_pieces()¶

Return the nabla pieces as a set.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzlePieces, DeltaPiece
sage: pieces = PuzzlePieces()
sage: delta = DeltaPiece('a','b','c')
sage: pieces.add_piece(delta,rotations=60)
sage: sorted([p for p in pieces.nabla_pieces()], key=str)
[a\b/c, b\c/a, c\a/b]

rhombus_pieces()¶

Return a set of all allowable rhombus pieces.

Allowable rhombus pieces are those where the south edge of the delta piece equals the north edge of the nabla piece.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import PuzzlePieces, DeltaPiece
sage: pieces = PuzzlePieces()
sage: delta = DeltaPiece('a','b','c')
sage: pieces.add_piece(delta,rotations=60)
sage: sorted([p for p in pieces.rhombus_pieces()], key=str)
[a/\b  b\/a, b/\c  c\/b, c/\a  a\/c]

class sage.combinat.knutson_tao_puzzles.RhombusPiece(north_piece, south_piece)¶

Bases: sage.combinat.knutson_tao_puzzles.PuzzlePiece

Class of rhombi pieces.

To construct a rhombus piece we input a delta and a nabla piece. The delta and nabla pieces are joined along the south and north edge, respectively.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece, NablaPiece, RhombusPiece
sage: delta = DeltaPiece('1','2','3')
sage: nabla = NablaPiece('4','5','6')
sage: RhombusPiece(delta,nabla)
2/\3  6\/5

edges()¶

Return the tuple of edge names.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece, NablaPiece, RhombusPiece
sage: delta = DeltaPiece('1','2','3')
sage: nabla = NablaPiece('4','5','6')
sage: RhombusPiece(delta,nabla).edges()
('north_west', 'north_east', 'south_east', 'south_west')

north_piece()¶

Return the north piece.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece, NablaPiece, RhombusPiece
sage: delta = DeltaPiece('1','2','3')
sage: nabla = NablaPiece('4','5','6')
sage: r = RhombusPiece(delta,nabla)
sage: r.north_piece()
2/1\3

south_piece()¶

Return the south piece.

EXAMPLES:

sage: from sage.combinat.knutson_tao_puzzles import DeltaPiece, NablaPiece, RhombusPiece
sage: delta = DeltaPiece('1','2','3')
sage: nabla = NablaPiece('4','5','6')
sage: r = RhombusPiece(delta,nabla)
sage: r.south_piece()
6\4/5

Knutson-Tao Puzzles¶

Acknowledgements¶

Table of Contents

Previous topic

Next topic

This Page