Questions tagged [robinson-schensted-knuth]

Filter by
Sorted by
Tagged with
15 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 ...
user avatar
8 votes
1 answer
344 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 ...
user avatar
  • 320
10 votes
1 answer
292 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$...
user avatar
6 votes
1 answer
153 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 \...
user avatar
  • 6,897
3 votes
0 answers
117 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 ...
user avatar
  • 911
6 votes
2 answers
276 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) \...
user avatar
  • 331
5 votes
0 answers
364 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 ...
user avatar
  • 1,721
12 votes
2 answers
473 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 ...
user avatar
  • 18.8k
4 votes
0 answers
139 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$...
user avatar
  • 7,432
20 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\...
user avatar
7 votes
1 answer
406 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$...
user avatar
  • 73
13 votes
4 answers
1k 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)...
user avatar
  • 1,721
1 vote
0 answers
166 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?
user avatar
10 votes
2 answers
715 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 ...
user avatar
20 votes
1 answer
896 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 ...
user avatar
  • 2,582
5 votes
3 answers
996 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-...
user avatar
24 votes
1 answer
602 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 ...
user avatar
8 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 ...
user avatar