posts/2014-04-01-q-robinson-schensted-symmetry-paper.org


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#+title: Symmetry property of \(q\)-weighted Robinson-Schensted algorithms and branching algorithms
#+date: <2014-04-01>

In [[http://link.springer.com/article/10.1007/s10801-014-0505-x][this
paper]] a symmetry property analogous to the well known symmetry
property of the normal Robinson-Schensted algorithm has been shown for
the \(q\)-weighted Robinson-Schensted algorithm. The proof uses a
generalisation of the growth diagram approach introduced by Fomin. This
approach, which uses "growth graphs", can also be applied to a wider
class of insertion algorithms which have a branching structure.

#+caption: Growth graph of q-RS for 1423
[[../assets/resources/1423graph.jpg]]

Above is the growth graph of the \(q\)-weighted Robinson-Schensted
algorithm for the permutation \({1 2 3 4\choose1 4 2 3}\).