blob: 782412bed8dfd12e80c37674d57a70fd430e8693 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
# 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}\).
|
