Tamari lattice

{{Dark mode invert|Image:Tamari lattice.svg}}

In mathematics, a Tamari lattice, introduced by {{harvs|txt|authorlink=Dov Tamari|first=Dov |last=Tamari|year=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)). Each grouping describes a different order in which the objects may be combined by a binary operation; in the Tamari lattice, one grouping is ordered before another if the second grouping may be obtained from the first by only rightward applications of the associative law (xy)z = x(yz). For instance, applying this law with x = a, y = bc, and z = d gives the expansion (a(bc))d = a((bc)d), so in the ordering of the Tamari lattice (a(bc))d ≤ a((bc)d).

In this partial order, any two groupings g1 and g2 have a greatest common predecessor, the meet g1 ∧ g2, and a least common successor, the join g1 ∨ g2. Thus, the Tamari lattice has the structure of a lattice. The Hasse diagram of this lattice is isomorphic to the graph of vertices and edges of an associahedron. The number of elements in a Tamari lattice for a sequence of n + 1 objects is the nth Catalan number Cn.

The Tamari lattice can also be described in several other equivalent ways:

  • It is the poset of sequences of n integers a1, ..., an, ordered coordinatewise, such that i ≤ ai ≤ n and if i ≤ j ≤ ai then aj ≤ ai {{harv|Huang|Tamari|1972}}.
  • It is the poset of binary trees with n leaves, ordered by tree rotation operations.
  • It is the poset of ordered forests, in which one forest is earlier than another in the partial order if, for every j, the jth node in a preorder traversal of the first forest has at least as many descendants as the jth node in a preorder traversal of the second forest {{harv|Knuth|2005}}.
  • It is the poset of triangulations of a convex n-gon, ordered by flip operations that substitute one diagonal of the polygon for another.

Notation

The Tamari lattice of the groupings of n+1 objects is called Tn. The corresponding associahedron is called Kn+1.

In The Art of Computer Programming T4 is called the Tamari lattice of order 4 and its Hasse diagram K5 the associahedron of order 4.

References

  • {{citation

| last = Chapoton | first = F.

| year = 2005

| mr = 2264942

| journal = Séminaire Lotharingien de Combinatoire

| title = Sur le nombre d'intervalles dans les treillis de Tamari

| language = French

| volume = 55

| bibcode = 2006math......2368C

| pages = 2368

| arxiv = math/0602368

| issue = 55}}.

  • {{citation

| last1 = Csar | first1 = Sebastian A.

| last2 = Sengupta | first2 = Rik

| last3 = Suksompong | first3 = Warut

| mr = 3265974

| issue = 3

| journal = Order

| pages = 337–363

| title = On a Subposet of the Tamari Lattice

| volume = 31

| year = 2014

| doi = 10.1007/s11083-013-9305-5| arxiv = 1108.5690}}.

  • {{citation

| last = Early | first = Edward

| mr = 2061375

| issue = 1

| journal = Annals of Combinatorics

| pages = 37–43

| title = Chain lengths in the Tamari lattice

| volume = 8

| year = 2004

| doi = 10.1007/s00026-004-0203-9}}.

  • {{citation

| doi = 10.1016/S0021-9800(67)80024-3

| last1 = Friedman | first1 = Haya | authorlink = Haya Freedman

| last2 = Tamari | first2 = Dov | author2-link = Dov Tamari (mathematician)

| language = French

| mr = 0238984

| journal = Journal of Combinatorial Theory

| pages = 215–242

| issue = 3

| title = Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative

| volume = 2

| year = 1967| doi-access = free

}}.

  • {{citation

| last = Geyer | first = Winfried

| mr = 1298967

| issue = 1–3

| journal = Discrete Mathematics

| pages = 99–122

| title = On Tamari lattices

| volume = 133

| year = 1994

| doi = 10.1016/0012-365X(94)90019-1| doi-access = free

}}.

  • {{citation

| last1 = Huang | first1 = Samuel

| last2 = Tamari | first2 = Dov | author2-link = Dov Tamari (mathematician)

| mr = 0306064

| journal = Journal of Combinatorial Theory, Series A

| pages = 7–13

| title = Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law

| volume = 13

| year = 1972

| doi = 10.1016/0097-3165(72)90003-9| doi-access =

}}.

  • {{citation

| last = Knuth | first = Donald E. | author-link = Donald Knuth

| contribution = Draft of Section 7.2.1.6: Generating All Trees

| title = The Art of Computer Programming

| volume = IV

| contribution-url = http://www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz

| page = 34

| year = 2005}}.

  • {{citation

| last = Tamari | first = Dov | author-link = Dov Tamari (mathematician)

| mr = 0146227

| journal = Nieuw Archief voor Wiskunde |series=Series 3

| pages = 131–146

| title = The algebra of bracketings and their enumeration

| volume = 10

| year = 1962}}.

Category:Lattice theory