타마리 격자

Tamari lattice
주문4의 타마리 격자

In mathematics, a Tamari lattice, introduced by Dov Tamari (1962), is a partially ordered set in which the elements consist of different ways of grouping a sequence of objects into pairs using parentheses; for instance, for a sequence of four objects abcd, the five possible groupings are ((ab)c)d, (ab)(cd), (a(bc))d, a((bc)d), and a(b(cd)).각 그룹화는 2진법 연산에 의해 개체가 결합될 수 있는 다른 순서를 기술한다. Tamari 격자에서는 연관법(xy)z = x(yz)의 우측 적용에 의해서만 첫 번째 그룹으로부터 두 번째 그룹화를 얻을 수 있는 경우, 하나의 그룹이 다른 그룹보다 먼저 정렬된다.예를 들어 x = a, y = bc, z = d로 이 법칙을 적용하면 확장(a(bc)d = a(bc)d = a(bc)d가 되므로 타마리 격자(a(BC)d ≤ a(BC)d의 순서에 따라 확장(a(bc)d)가 된다.

이 부분적 순서에서, 어떤 두 그룹1 g와 g는2 가장 큰 공통의 전임자, 만남 g1 ∧ g와2 최소 공통의 후임자, 결합 g1 ∨ g를2 가진다.따라서 타마리 격자는 격자 구조를 가지고 있다.이 격자의 하세 다이어그램은 정점과 연관면의 가장자리 그래프에 이형이다.tamari 격자 안에 있는 원소의 수는 n번째 카탈로니아 수 C이다n.

Tamari 격자는 또한 몇 가지 다른 동등한 방법으로 설명할 수 있다.

  • i coordinate ai n, i if j ≤ ai, then a, ordered then a, then thenji a (Huang & Tamari 1972년)와 같이 n 정수1 a, ..., an, 좌표로 정렬된 순서의 poset이다.
  • 잎이 n개인 이진수(binary tree)의 포셋으로, 나무 회전 작업으로 순서를 정한다.
  • 그것은 순서가 정해진 숲의 포셋으로, 만약, 첫 번째 숲의 사전 순서에 있는 j번째 노드가 두 번째 숲의 사전 순서에 있는 j번째 노드(Knuth 2005)만큼의 후손을 가지고 있다면, 한 숲이 부분 순서에 있어서 다른 숲보다 먼저 있는 것이다.
  • 그것은 볼록한 n곤의 삼각형 포셋으로, 다각형의 대각선 하나를 다른 것으로 대체하는 플립 연산에 의해 명령된다.

표기법

n+1 객체의 C 그룹화의n 타마리 격자(Tamari lattice)를 T라고n 부르지만, 이에 대응하는 연관면(associarhedron)을n+1 K라고 한다.

The Art of Computer Programming T에서는4 순서 4의 타마리 격자(Tamari lattice)와 그 하세 다이어그램 K를5 순서 4의 연관체로 부른다.

참조

  • Chapoton, F. (2005), "Sur le nombre d'intervalles dans les treillis de Tamari", Séminaire Lotharingien de Combinatoire (in French), 55 (55): 2368, arXiv:math/0602368, Bibcode:2006math......2368C, MR 2264942.
  • Csar, Sebastian A.; Sengupta, Rik; Suksompong, Warut (2014), "On a Subposet of the Tamari Lattice", Order, 31 (3): 337–363, arXiv:1108.5690, doi:10.1007/s11083-013-9305-5, MR 3265974.
  • Early, Edward (2004), "Chain lengths in the Tamari lattice", Annals of Combinatorics, 8 (1): 37–43, doi:10.1007/s00026-004-0203-9, MR 2061375.
  • Friedman, Haya; Tamari, Dov (1967), "Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative", Journal of Combinatorial Theory (in French), 2 (3): 215–242, doi:10.1016/S0021-9800(67)80024-3, MR 0238984.
  • Geyer, Winfried (1994), "On Tamari lattices", Discrete Mathematics, 133 (1–3): 99–122, doi:10.1016/0012-365X(94)90019-1, MR 1298967.
  • Huang, Samuel; Tamari, Dov (1972), "Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law", Journal of Combinatorial Theory, Series A, 13: 7–13, doi:10.1016/0097-3165(72)90003-9, MR 0306064.
  • Knuth, Donald E. (2005), "Draft of Section 7.2.1.6: Generating All Trees", The Art of Computer Programming, vol. IV, p. 34.
  • Tamari, Dov (1962), "The algebra of bracketings and their enumeration", Nieuw Archief voor Wiskunde, Series 3, 10: 131–146, MR 0146227.