# Copyright (C) 2013-2021 Yuchen Pei.

# Permission is granted to copy, distribute and/or modify this
# document under the terms of the GNU Free Documentation License,
# Version 1.3 or any later version published by the Free Software
# Foundation; with no Invariant Sections, no Front-Cover Texts, and
# no Back-Cover Texts. You should have received a copy of the GNU
# Free Documentation License. If not, see <https://www.gnu.org/licenses/>.

# This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/4.0/ or send a letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA.

#+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/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}\).