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
28
29
30
31
32
33
34
35
36
37
38
39
|
# 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: A \(q\)-weighted Robinson-Schensted algorithm
#+date: <2013-06-01>
In [[https://projecteuclid.org/euclid.ejp/1465064320][this paper]] with
[[http://www.bristol.ac.uk/maths/people/neil-m-oconnell/][Neil]] we
construct a \(q\)-version of the Robinson-Schensted algorithm with
column insertion. Like the
[[http://en.wikipedia.org/wiki/Robinson–Schensted_correspondence][usual
RS correspondence]] with column insertion, this algorithm could take
words as input. Unlike the usual RS algorithm, the output is a set of
weighted pairs of semistandard and standard Young tableaux \((P,Q)\)
with the same shape. The weights are rational functions of indeterminant
\(q\).
If \(q\in[0,1]\), the algorithm can be considered as a randomised RS
algorithm, with 0 and 1 being two interesting cases. When \(q\to0\), it
is reduced to the latter usual RS algorithm; while when \(q\to1\) with
proper scaling it should scale to directed random polymer model in
[[http://arxiv.org/abs/0910.0069][(O'Connell 2012)]]. When the input
word \(w\) is a random walk:
\begin{align*}\mathbb
P(w=v)=\prod_{i=1}^na_{v_i},\qquad\sum_ja_j=1\end{align*}
the shape of output evolves as a Markov chain with kernel related to
\(q\)-Whittaker functions, which are Macdonald functions when \(t=0\)
with a factor.
|
