Questions tagged [robinson-schensted-knuth]
The robinson-schensted-knuth tag has no usage guidance.
24 questions
2
votes
1
answer
136
views
Relative position of flags and the Robinson-Schensted correspondence
This question is related my question in An example of a Deligne–Lusztig variety for a general linear group, and the obtained answer.
I am currently reading Steinberg, Robert, An occurrence of the ...
- 153
7
votes
1
answer
281
views
Robinson-Schensted-Knuth (RSK) under restriction
I am curious about the following result concerning the Robinson-Schensted insertion procedure. I can formulate a proof via the Schützenberger evacuation operator, but I have struggled to find such an ...
- 111
3
votes
0
answers
153
views
The Grassmann twist-map, an associated semi-group action, and RSK
Let me begin by setting some notation: Let $\mathrm{Mat}_{k,n}(\Bbb{R})$ denote the vector space of all $k \times n$
real-valued matrices. Given $g \in \mathrm{Mat}_{k,n}(\Bbb{R})$ and two (ordered) ...
- 2,137
16
votes
2
answers
1k
views
Year of birth of Craige Schensted
For a paper I am writing related to the history of combinatorics, I am
looking for the year of birth of Craige Eugene
Schensted, the eponym for the
Schensted correspondence. According to this
site, a ...
- 50.8k
8
votes
1
answer
511
views
RSK correspondence
Up to now, what are the difference ways we know to define RSK correspondence? I already know:
By insertion and recording tableau.
Ball construction or Viennot's geometric construction.
Growth diagram ...
- 320
10
votes
1
answer
325
views
About $K$-rectification of increasing tableaux
Let $T$ be a standard Young tableaux on $[n]$. Denote the RSK algorithm $\text{RSK}(w)=(P(T),Q(T))$ for $w\in\mathfrak{S}_n$, where $P(T)$ is the Schencted insertion tableaux.
For $1\leq i\leq j\leq n$...
6
votes
1
answer
181
views
Can $S_n$ be partitioned into subsets containing an involution and satisfying $∀σ≠τ, ∃j$ s.t. $σ(j)≠τ(j),σ^{−1}(j)=τ^{−1}(j)$?
Background
Let $\sigma, \tau \in S_n$. We will say that $\sigma$ and $\tau$ are locally orthogonal and write $\sigma \perp \tau$ if there exists $j \in \{1, 2, \ldots, n\}$ such that $\sigma(j) \neq \...
- 7,237
3
votes
0
answers
135
views
RSK on matrices with non-integer values
In the usual RSK algorithm, matrices with non-negative integer valued entries are mapped bijectively to a pair of tableaux. The length of the top row of either of the tableaux gives the maximal weight ...
- 941
6
votes
2
answers
325
views
Correspondence between $SBT (n)$ and $W(B_n)$
Let $W(B_n)$ be a Weyl group of type $B_n$ and $SBT (n)$ the set of standard bitableaux of size $n$. Similar to Robinson-Schensted correspondences, I know that there exists a map $W(B_n) \to SBT (n) \...
- 331
5
votes
0
answers
403
views
Staircase Schur functions squared
Let $\Delta_n$ be the staircase-shaped partition $(n-1,n-2,\dots,1)$. Are there any non-obvious combinatorial objects that index $s_{\Delta_n}^2$? Here, $s_\lambda$ is the Schur function indexed by ...
- 1,989
12
votes
2
answers
495
views
Dynamics of RSK
There is a way of viewing the RSK correspondence as a map (in fact, bijection) $A \overset{RSK}\longrightarrow \widehat{A}$ from $n\times n$ matrices with entries $\mathbb{N}$ to (weak) reverse plane ...
- 24.2k
4
votes
0
answers
156
views
Degeneration of modules over the affine symmetric group and jeu de taquin
Let $H_n$ be the group algebra of the affine Coxeter group of type A (feel free to replace it by the affine Hecke algebra). This is generated by elements $y_i$'s, $i=1,\dots,n$ and transpositions $s_i$...
- 8,524
21
votes
2
answers
2k
views
Has Reifegerste's Theorem on RSK and Knuth relations received a slick proof by now?
For the notations I am using, I refer to the Appendix at the end of this post.
Here is what, for the sake of this post, I consider to be Reifegerste's theorem:
Theorem 1. Let $n\in\mathbb N$ and $i\...
- 33.8k
7
votes
1
answer
425
views
Does this lattice have a name (and literature)?
The "lattice" in the title appears to be a lattice. At least it's a poset, which I define now.
Fix a partition $\lambda$ of $n$ and consider the set of all standard Young tableaux (each of $1,\dots,n$...
- 73
13
votes
4
answers
2k
views
Generalization's of Greene's Theorem for the Robinson-Schensted correspondence
One important property of the Robinson-Schensted correspondence (RS) is that the longest increasing subsequence of the permutation $\sigma$ is $\lambda_1$, the first entry of the shape $\lambda(\sigma)...
- 1,989
1
vote
0
answers
171
views
What is the RSK correspondence for $G\wr S_n.$
What is the RSK correspondence for $G\wr S_n$?. Where can I read about this?
- 11
10
votes
2
answers
811
views
Viennot-type geometric description for dual RSK correspondence?
Is a geometric construction of the dual RSK correspondence along the lines of Viennot's "light and shadows construction" written up somewhere? This is a bijective correspondence between 0-1 matrices ...
- 5,654
21
votes
1
answer
1k
views
Bruhat order and the Robinson-Schensted correspondence
The Robinson-Schensted correspondence is a bijection between elements of the symmetric group $S_n$ and pairs of standard tableaux of the same shape. The symmetric group is partially ordered by the ...
- 2,721
5
votes
3
answers
1k
views
RS to RSK correspondence
The RS correspondence is a correspondence which associates to each permutation a pair of standard Young tableaux of the same shape.
The RSK correspondence associates to each integer matrix (with non-...
- 5,654
24
votes
1
answer
615
views
Permutations, stopping times, Bessel functions, hook formula and Robinson-Schensted
For given counting number $n$, consider all permutations $\pi$ of {$1,\ldots,n$}, generate for every $\pi$ its Robinson-Schensted pair of standard tableaux $(P_\pi,Q_\pi)$ and average together all the ...
- 17.6k
9
votes
2
answers
624
views
Number of longest decreasing subsequences and RSK
It is well known via the RSK-correspondence that the length of the longest decreasing subsequence in a permutation $\pi \in S_n$ is the length of the longest column of the insertion tableau of $\pi$. (...
- 771
9
votes
6
answers
2k
views
Geometric proof of Robinson-Schensted-Knuth correspondence?
Famous Robinson Schensted Knuth correspondence gives a correspondence between the matrices with non-negative integer entries and pair of semi standard tableaux. The proof that I have seen is highly ...
- 899
5
votes
5
answers
2k
views
Implementation of the Robinson-Schensted correspondence
Has the Robinson-Schensted correspondence, as explained by Wikipedia or Richard Stanley, been implemented in any of the standard programming languages. I'm using Python, but I'm open to Java, C++, ...
- 22.8k
15
votes
3
answers
867
views
What bijection on permutations corresponds under RS to transpose?
The Robinson-Schensted correspondence is a bijection between elements of the symmetric group and ordered pairs of standard tableaux of the same shape.
Some simple operations on tableaux correspond to ...
- 44.7k