ロビンソンとシェンステッドの書簡

数学において、ロビンソン・シェンステッド対応とは、順列と同一形状の標準ヤング表のペアとの間の全単射対応である。この対応には様々な記述があり、いずれもアルゴリズム的な性質を持ち、多くの注目すべき特性を備え、組み合わせ論や表現論などの分野に応用されている。この対応は数多くの方法で一般化されており、特にクヌースによるロビンソン・シェンステッド・クヌース対応への一般化や、ゼレヴィンスキーによる図へのさらなる一般化などが挙げられる。

この対応関係を最も簡単に説明する方法は、シェンステッドアルゴリズム（Schensted 1961 ）を使用することです。この手順では、特定の規則に従って順列の値を順次挿入して一方のタブローを構築し、もう一方のタブローには構築中の形状の変化を記録します。この対応関係は、かなり以前にロビンソン（Robinson 1938 ）によって、リトルウッド・リチャードソン規則を証明しようとして、かなり異なる形で記述されていました。この対応関係は、ロビンソンが使用した手順はシェンステッドアルゴリズムとは根本的に異なり、ほとんど完全に忘れ去られているにもかかわらず、しばしばロビンソン・シェンステッドアルゴリズムと呼ばれます。この対応関係を定義する他の方法には、ジュ・ド・タキンの観点からの非決定論的アルゴリズムが含まれます。

この対応関係の全単射性は、列挙的同一性に関係している。

\sum _{\lambda \in {\mathcal {P}}_{n}}(t_{\lambda })^{2}=n!

どこ ${\mathcal {P}}_{n}$ $はn$ の分割(または $n$ 個の正方形を持つヤング図)の集合を表し、 $t$ $λ は$ $形状λ$ の標準ヤング表の数を表します。

シェンステッドアルゴリズム

シェンステッドアルゴリズムは、 2行表記で書かれた順列 $σから始まります。$

\sigma ={\begin{pmatrix}1&2&3&\cdots &n\\\sigma _{1}&\sigma _{2}&\sigma _{3}&\cdots &\sigma _{n}\end{pmatrix}}

ここで $σ i = σ (i)$ であり、同じ形状の (中間) 順序付きヤング表のシーケンスを順次構築することによって進行します。

(P_{0},Q_{0}),(P_{1},Q_{1}),\ldots ,(P_{n},Q_{n}),

ここで、 $P 0 = Q 0$ は空のタブローです。出力タブローは $P = P n$ および $Q = Q n$ です。P i −1 が構築されたら $、 P$ $i$ $-1$ $に$ σ $i$ $を$ 挿入して $P i$ を形成し $、$ 次に挿入によって形状に追加された正方形にエントリ $i を$ $Q$ $i$ $-1$ に追加して $Q$ $i$ $を形成します (これにより、すべてのiに対して$ $P$ $i$ と $Q$ $i は$ 同じ形状になります)。タブロー $Q$ $i$ の役割がより受動的であるため、出力の一部であり、以前の $Q$ $i$ を容易に読み取ることができる最後のタブロー $Q$ $n$ は記録タブローと呼ばれます。対照的に、タブロー $P$ $i$ は挿入タブローと呼ばれます。

挿入

$各σ i$ を挿入するために使用される基本的な手順は、 Schensted 挿入または行挿入(列挿入と呼ばれる変種手順と区別するため)と呼ばれます。その最も単純な形式は、「不完全な標準タブロー」で定義されます。標準タブローと同様に、行と列が増加する個別のエントリがありますが、一部の値 (まだ挿入されていない) はエントリとして存在しない場合があります。この手順は、そのようなタブロー $Tと、$ $T$ のエントリとして存在しない値 $x を引数として受け取ります。出力として、$ $T$ $\leftarrow$ $x$ と表記される新しいタブローと、その形状が拡大した正方形 $s$ を生成します。値 $x は、$ $T$ $\leftarrow$ $x$ の最初の行に現れます。これは、末尾に追加された場合 ( $xより大きいエントリが存在しない場合)、またはそれ以外の場合は、$ $T$ の最初の行の最初のエントリ $y$ $>$ $x$ を置き換えた場合のいずれかです。前者の場合 $、sは$ $x$ が追加される正方形であり、挿入が完了します。後者の場合、置き換えられたエントリ $yは同様に$ $T$ の 2 行目に挿入され、その後、ある段階で最初のケースが適用されるまで続きます ( $T$ の空の行に到達した場合は必ず発生します)。

より厳密には、次の擬似コードは、新しい値 $xを$ $T$ に行挿入することを示しています。^{[ 1 ]}

$i = 1$ とし、 $jを$ $T$ の最初の行の長さより 1 大きい値に設定します。
$j > 1$ かつ $x < T i 、 j -1$ の間、 $j$ を 1 減らす。（これで $(i 、 j)は、$ $T$ の $x$ より大きい値を持つか、または値がまったくない $i$ 行目の最初の正方形となる。）
$T$ の正方形 $(i, j)$ が空の場合、正方形 $($ $i$ $,$ $j$ $)に$ $x を$ $T$ に追加し、 $s$ $= ($ $i$ $,$ $j$ $)$ と設定した後、処理を終了します。
$x$ と $T i, j$ の値を入れ替えます。（これにより、古い $xが$ $i$ 行目に挿入され、置き換えられる値は次の行に挿入するために保存されます。）
$iを$ 1増やして、ステップ2に戻る。

$T$ の形状はちょうど 1 平方だけ大きくなります。つまり $s$ です。

正確さ

$T \leftarrow x の$ 行と列が増加していることは、 $T$ についても同様であれば、この手順からは明らかではありません (同じ列のエントリは比較すらされません)。しかし、次のように考えることができます。ステップ 4 の直後を除き、常にマス目 $(i, j)は$ $T$ では空であるか、 $x$ より大きい値を保持しています。ステップ5 では、 $($ $i$ $,$ $j$ $)が$ $T$ で元々 $x を$ 含んでいたマス目のすぐ下のマス目であるため、この性質が再び確立されます。したがって、ステップ 4 での置換が $T$ $i, j の$ 値に及ぼす影響は、その値を小さくすることです。特に、右または下の隣接マス目よりも大きくなることはありません。一方、新しい値は、左の隣接マス目 (存在する場合) よりも小さくなることはありません。これは、ステップ2 を終了させた比較によって保証されています。最後に、新しい値がその上位隣接値 $T$ $i$ $-1,$ $j$ （存在する場合）よりも大きいことを確認するには、ステップ 5 の後も $T$ $i$ $-1,$ $j$ が維持され、ステップ 2 で $j を$ 減少させると対応する値 $T$ $i$ $-1,$ $j$ だけが減少することに注意してください。

場面構成の構築

置換 $σ$ に適用される完全なシェンステッドアルゴリズムは、次のように進行します。

$P$ と $Qの$ 両方を空のタブローに設定する
$i が$ $1から$ $n$ まで増加するにつれて、挿入手順によって $P \leftarrow σ i$ と平方 $s$ を計算します。次に、 $Pを$ $P \leftarrow σ i$ に置き換え、平方 $s$ 内のタブロー $Q$ にエントリ $i$ を追加します。
終了し、ペア $(P 、 Q)$ を返します。

このアルゴリズムは、標準的なヤング表のペアを生成する。

構造の反転可能性

同じ形状の標準ヤング表の任意のペア $(P 、 Q)が与えられた場合、シェンステッドアルゴリズムによって$ $(P 、 Q)$ を生成する順列を生成する逆手順が存在することがわかります。これは基本的に、アルゴリズムの手順を逆方向にたどり、毎回 $Qのエントリを使用して逆挿入を開始すべきマスを見つけ、対応する$ $P$ のエントリを前の行に移動させ、最初の行のエントリが置き換えられるまで行を上方向にたどり続けることで構成されます。置き換えられた値は、構築アルゴリズムの対応する手順で挿入された値です。これら 2 つの逆アルゴリズムは、一方では $n$ の順列と、他方では同じ形状で $n個のマスを含む標準ヤング表のペアとの間に全単射対応を定義します。$

物件

最も基本的な特性の一つだが、アルゴリズムの構成からは明らかではないのが対称性である。

ロビンソン・シェンステッド対応がタブロー $（ P 、 Q ）$ を置換 $σ$ に対応させる場合、 $（ Q 、 P ）$ を逆置換 $σ -1$ に対応させる。

これは、例えばヴィエノーの幾何学的構成法を用いることで証明できる。

さらに、対応関係がタブロー $(P 、 Q)$ を順列 $σ = (σ 1 、 ...、 σ n)$ に対応付けていると仮定して、以下の特性を示します。

逆順列 $($ $σ$ $n$ $, ...,$ $σ$ $1$ $)$ に関連付けられたタブローのペア $(P', Q' )$ では、タブロー $P$ $'はタブロー$ $P$ の転置であり、 $Q$ $'は$ $P$ とは独立して $Q$ によって決定されるタブローです(つまり、シューツェンベルガーの対合によって $Q$ から得られたタブローの転置です)。
$σ$ $1$ $、 ...、$ $σ$ $n$ の最長増加部分列の長さは、 $P$ (および $Q$ )の最初の行の長さに等しい。
$σ 1 、 ...、 σ n$ の最長減少部分列の長さは、前の 2 つの性質からわかるように、 $P$ (および $Q$ )の最初の列の長さに等しい。
$σ$ の降下集合 ${i : σ i > σ i +1$ }は、 $Q$ の降下集合 ${$ $i$ $:$ $i +1 は$ $i$ $の行より厳密に下の行にある$ }と等しい。
$π$ の部分列とそのインデックスの集合を識別します。任意の $k \geq 1$ に対して、最大 $k 個$ の増加部分列の和集合として表せる最大の集合のサイズは $λ 1 + ... + λ k$ であるという Greeneの定理があります。特に、 $λ 1 は$ $π$ の増加部分列の最大長に等しくなります。
$σが$ 対合である場合、 $σ$ の不動点の数は $λ$ の奇数長の列の数に等しい。

アプリケーション

エルデシュ・セーケレスの定理への応用

ロビンソン・シェンステッド対応を用いると、エルデシュ・セケレスの定理の簡単な証明を与えることができる。

注記

↑ D.E. クヌース(1973) 『コンピュータプログラミングの技法』第3巻、 50～ 51ページより抜粋

参考文献

フルトン、ウィリアム（1997）、『ヤング・タブロー』、ロンドン数学会学生テキスト、第 35巻、ケンブリッジ大学出版局、ISBN 978-0-521-56144-0MR 1464693 。
Knuth, Donald E. (1970)、「順列、行列、および一般化ヤング表」、Pacific Journal of Mathematics、34 (3): 709–727、doi : 10.2140/pjm.1970.34.709、MR 0272654
Robinson, G. de B. (1938)、「対称群の表現について」、American Journal of Mathematics、60 (3): 745–760、doi : 10.2307/2371609、JSTOR 2371609、Zbl 0019.25102 。
Sagan, BE (2001), 『対称群』、大学院数学テキスト、第 203巻、ニューヨーク：Springer-Verlag、ISBN 0-387-95067-2。
Schensted, C. (1961)、「最長増加部分列と最長減少部分列」、Canadian Journal of Mathematics、13：179–191、doi：10.4153/CJM-1961-015-3、MR 0121305 。
スタンレー、リチャード P. (1999)、『列挙的組合せ論』第 2 巻、ケンブリッジ高等数学研究シリーズ、第 62 巻、ケンブリッジ大学出版局、ISBN 978-0-521-56069-6MR 1676282 。
Zelevinsky, AV (1981)、「リトルウッド-リチャードソン規則とロビンソン-シェンステッド-クヌース対応の一般化」、Journal of Algebra、69 (1): 82–94、doi : 10.1016/0021-8693(81)90128-9、MR 0613858 。

さらに読む

Green, James A. (2007). GL _nの多項式表現. Lecture Notes in Mathematics. Vol. 830. K. Erdmann、JA Green、M. Schocker による Schensted 対応と Littelmann 経路に関する付録付き (第 2 版、改訂増補版). Berlin: Springer-Verlag . ISBN 978-3-540-46944-5. Zbl 1108.20044 .

外部リンク

van Leeuwen, MAA (2001) [1994]、「ロビンソン-シェンステッド対応」、数学百科事典、EMS Press
Williams, L.、「Robinson-Schenstedアルゴリズムのインタラクティブアニメーション」

[1] D.E. クヌース(1973) 『コンピュータプログラミングの技法』第3巻、 50～ 51ページより抜粋

[ 1 ]