たまり格子

数学において、Dov Tamari  (1962)によって導入された タマリ格子は、要素が括弧を使用してオブジェクトのシーケンスをペアにグループ化するさまざまな方法で構成される半順序集合です。たとえば、4 つのオブジェクトのシーケンスabcdの場合、可能な 5 つのグループ化は、(( ab ) c ) d、( ab ) ( cd )、( a ( bc )) d、a (( bc ) d )、およびa ( b ( cd ) ) です。各グループ化は、バイナリ演算によってオブジェクトを組み合わせることができる異なる順序を表します。タマリ格子では、1 つのグループが他のグループよりも順序付けられるのは、結合法則( xy ) z  =  x ( yz )を右向きに適用することによってのみ最初のグループから 2 番目のグループを取得できる場合です。たとえば、この法則をx  =  a、y  =  bc、z  =  dに適用すると、展開 ( a ( bc )) d  =  a (( bc ) d ) が得られるので、タマリ格子の順序では ( a ( bc )) d  ≤  a (( bc ) d ) となる。

この部分順序では、任意の 2 つのグループg ₁とg ₂には、最大共通先行グループであるmeet g ₁  ∧  g ₂と、最小共通後続グループであるjoin g ₁  ∨  g _{2があります。したがって、Tamari 格子は}格子の構造を持ちます。この格子のハッセ図は、連想面体の頂点と辺のグラフに同型です。n + 1 個のオブジェクトのシーケンスの Tamari 格子の要素数は、n番目のカタラン数C _n です。

タマリ格子は、他のいくつかの同等の方法で記述することもできます。

• これは、i  ≤  a _i  ≤  n かつi  ≤  j  ≤  a _iならばa _j  ≤  a _iとなるような座標順に順序付けられたn個の整数a ₁ , ...,  a _nのシーケンスの半集合です(Huang & Tamari 1972)。
• これは、木の回転操作によって順序付けられた、 n 個の葉を持つ二分木の半順序集合です。
• これは順序付きフォレストの半順序集合であり、任意のjに対して、最初のフォレストの事前順序探索における j 番目のノードの子孫の数が、2 番目のフォレストの事前順序探索における j 番目のノードの子孫の数と少なくとも同じである場合、1 つのフォレストが部分順序で他のフォレストよりも前になります (Knuth 2005)。
• これは、多角形の 1 つの対角線を別の対角線に置き換える反転操作によって順序付けられた、凸n 多角形の三角形分割の半集合です。

n +1 個のオブジェクトのグループ化のタマリ格子はT _nと呼ばれ、対応する連想面体は K _{n +1}と呼ばれます。

『 The Art of Computer Programming』では、T _{4 は}次数 4 の Tamari 格子と呼ばれ、そのハッセ図 K _{5 は}次数 4 の連想面体と呼ばれます。

• Chapoton, F. (2005)、「Sur le nombre d'intervalles dans les treillis de Tamari」、Séminaire Lotharingien de Combinatoire (フランス語)、55 (55): 2368、arXiv : math/0602368、Bibcode :2006math... ...2368C、MR  2264942。
• Csar, Sebastian A.; Sengupta, Rik; Suksompong, Warut (2014)、「タマリ格子のサブポセットについて」、Order、31 (3): 337–363、arXiv : 1108.5690、doi :10.1007/s11083-013-9305-5、MR  3265974。
• アーリー、エドワード (2004)、「タマリ格子の鎖長」、Annals of Combinatorics、8 (1): 37–43、doi :10.1007/s00026-004-0203-9、MR  2061375。
• ハヤ・フリードマン; Tamari, Dov (1967)、「Problèmes d'associativité: Une Structure de treillis finis induite par une loi demi-associative」、Journal of Combinatorial Theory (フランス語)、2 (3): 215–242、doi : 10.1016/S0021 -9800(67)80024-3、MR  0238984。
• ガイヤー、ウィンフリード（1994）、「タマリ格子について」、離散数学、133（1–3）：99–122、doi：10.1016/0012-365X（94）90019-1、MR  1298967。
• 黄, サミュエル;タマリ, ドブ(1972)、「結合性の問題: 半結合法則によって順序付けられたシステムの格子特性の簡単な証明」、組合せ理論ジャーナル、シリーズ A、13 : 7–13、doi :10.1016/0097-3165(72)90003-9、MR  0306064。
• Knuth, Donald E. (2005)、「セクション 7.2.1.6: すべてのツリーの生成の草稿」、The Art of Computer Programming、第 4 巻、34 ページ。
• Tamari, Dov (1962)、「ブラケットの代数とその列挙」、Nieuw Archief voor Wiskunde、シリーズ 3、10 : 131–146、MR  0146227。