En matemáticas, una celosía de Tamari , introducida por Dov Tamari ( 1962 ), es un conjunto parcialmente ordenado en el que los elementos consisten en diferentes formas de agrupar una secuencia de objetos en pares utilizando paréntesis; por ejemplo, para una secuencia de cuatro objetos abcd , las cinco agrupaciones posibles son (( ab ) c ) d , ( ab ) ( cd ), ( a ( bc )) d , a (( bc ) d ) y a ( b ( cd)). Cada agrupación describe un orden diferente en el que los objetos pueden combinarse mediante una operación binaria ; en la red de Tamari, una agrupación se ordena antes que otra si la segunda agrupación puede obtenerse de la primera mediante aplicaciones hacia la derecha de la ley asociativa ( xy ) z = x ( yz ). Por ejemplo, aplicar esta ley con x = a , y = bc y z = d da la expansión ( a ( bc )) d = a (( bc ) d ), por lo que en el orden de la red de Tamari ( a ( bc )) d ≤ a (( bc ) d ).
En este orden parcial, cualquiera de las dos agrupaciones g 1 y g 2 Tienes un mayor predecesor común, la reúnen g 1 ∧ g 2 , y un sucesor menos común, el unen g 1 ∨ g 2 . Por lo tanto, la celosía de Tamari tiene la estructura de una celosía . El diagrama de Hasse de esta celosía es isomorfo al gráfico de vértices y aristas de un asociaedro . El número de elementos en una celosía Tamari para una secuencia de n + 1 objetos es el n- ésimo número catalán C n .
La celosía de Tamari también se puede describir de varias otras formas equivalentes:
- Es el conjunto de sucesiones de n enteros a 1 , ..., a n , ordenadas por coordenadas, tal que i ≤ a i ≤ n y si i ≤ j ≤ a i entonces a j ≤ a i ( Huang & Tamari 1972 ) .
- Es el conjunto de árboles binarios con n hojas, ordenados por operaciones de rotación de árboles .
- Es el conjunto de bosques ordenados , en el que un bosque es anterior a otro en el orden parcial si, para cada j , el j- ésimo nodo en un recorrido de preorden del primer bosque tiene al menos tantos descendientes como el j- ésimo nodo en un recorrido de preorden del segundo bosque ( Knuth 2005 ).
- Es el conjunto de triangulaciones de un n -gon convexo , ordenado por operaciones de volteo que sustituyen una diagonal del polígono por otra.
Notación
El entramado de Tamari de las agrupaciones C n de n +1 objetos se llama T n , pero la asociación correspondiente se llama K n +1 .
En El arte de la programación informática, T 4 se llama la red de Tamari de orden 4 y su diagrama de Hasse K 5 el asociaedro de orden 4 .
Referencias
- Chapoton, F. (2005), "Sur le nombre d'intervalles dans les treillis de Tamari", Séminaire Lotharingien de Combinatoire (en francés), 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 (en francés), 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), "Problemas de asociatividad: una prueba simple de la propiedad reticular de sistemas ordenados por una ley semi-asociativa", Journal of Combinatorial Theory, Serie A , 13 : 7-13, doi : 10.1016 / 0097- 3165 (72) 90003-9 , MR 0306064.
- Knuth, Donald E. (2005), "Borrador de la sección 7.2.1.6: Generación de todos los árboles" , El arte de la programación informática , IV , p. 34.
- Tamari, Dov (1962), "El álgebra de los corchetes y su enumeración", Nieuw Archief voor Wiskunde , Serie 3, 10 : 131-146, MR 0146227.