Latice Tamari

În matematică o latice Tamari, introdusă de Dov Tamari,^[1] este o mulțime parțial ordonată^⁠(d) în care elementele constau în diferitele moduri de grupare ale elementelor unui șir de obiecte în perechi folosind paranteze; de exemplu, pentru o secvență de patru obiecte abcd, cele cinci grupări posibile sunt ((ab)c)d, (ab)(cd), (a(bc))d, a((bc)d) și a(b(cd)). Fiecare grupare descrie o ordine diferită în care obiectele pot fi combinate printr-o operație binară. În laticea Tamari, o grupare este ordonată înaintea alteia dacă a doua grupare poate fi obținută din prima numai prin aplicații spre dreapta ale asociativității (xy)z = x(yz). De exemplu, aplicarea acestei legi cu x = a, y = bc și z = d dă extinderea (a(bc))d = a((bc)d), deci în ordinea laticei Tamari (a(bc))d ≤ a((bc)d).

În această ordonare parțială, oricare două grupări g₁ și g₂ au cel mai mare predecesor comun (minorant) expresia g₁ ∧ g₂ și cel mai mic succesor comun (majorant) expresia g₁ ∨ g₂. Astfel, laticea Tamari are structura unei latice^⁠(d). Diagrama Hasse^⁠(d) a acestei latice este izomorfă față de graful vârfurilor și laturilor^⁠(d) unui asociaedru. Numărul de elemente dintr-o latice Tamari pentru o secvență de n + 1 obiecte este al n-lea număr Catalan C_n.

Laticea Tamari poate fi descrisă și în alte moduri, echivalente:

Este mulțimea parțial ordonată de secvențe de n întregi a₁, ..., a_n, ordonate în funcție de coordonate, astfel încât i ≤ a_i ≤ n, iar dacă i ≤ j ≤ a_i atunci a_j ≤ a_i.^[2]
Este mulțimea parțial ordonată a arborilor binari cu n noduri terminale, ordonată prin operații de rotație a unui arbore.
Este mulțimea parțial ordonată a pădurilor ordonate, în care o pădure este anterioară alteia în ordinea parțială dacă, pentru fiecare j, al j-lea nod din ordinea traversării primei păduri are cel puțin la fel de mulți descendenți ca și nodul j dintr-o traversare în ordinea celei de-a doua păduri.^[3]
Este mulțimea parțial ordonată a tringulărilor unui n-gon convex, ordonat prin operații de inversare care înlocuiesc o diagonală a poligonului cu alta.

Notații

Laticea Tamari a grupărilor C_n de n+1 obiecte este notată T_n, dar asociaedrul corespunzător este notat K_n+1.

În Arta programării calculatoarelor T₄ este numită laticea Tamari de ordinul 4, iar diagrama sa Hasse, K₅, asociaedrul de ordinul 4.^[3]

Note

^ en Tamari, Dov (1962), „The algebra of bracketings and their enumeration”, Nieuw Archief voor Wiskunde, Series 3, 10: 131–146, MR 0146227
^ en 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
^ ^a ^b en Knuth, Donald E. (2005), „Draft of Section 7.2.1.6: Generating All Trees”, The Art of Computer Programming (în română Arta programării calculatoarelor), IV, p. 34, arhivat din original la 2 ianuarie 2023, accesat în 2 ianuarie 2023 (Knuth 2005)

Bibliografie

fr 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
en 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
en 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
en Friedman, Haya; Tamari, Dov (1967), „Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative”, Journal of Combinatorial Theory (în French), 2 (3): 215–242, doi:10.1016/S0021-9800(67)80024-3 , MR 0238984 Mentenanță CS1: Limbă nerecunoscută (link)
en Geyer, Winfried (1994), „On Tamari lattices”, Discrete Mathematics, 133 (1–3): 99–122, doi:10.1016/0012-365X(94)90019-1 , MR 1298967