Associahedron

In mathematics, an associahedron Kn is an (n − 2)-dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a word of n letters and the edges correspond to single application of the associativity rule. Equivalently, the vertices of an associahedron correspond to the triangulations of a regular polygon with n + 1 sides and the edges correspond to edge flips in which a single diagonal is removed from a triangulation and replaced by a different diagonal. Associahedra are also called Stasheff polytopes after the work of Jim Stasheff, who rediscovered them in the early 1960s[1] after earlier work on them by Dov Tamari.[2]

Associahedron K5 (front)
Associahedron K5 (back)
K5 is the Hasse diagram of the Tamari lattice T4.
The 9 faces of K5
Each vertex in the above Hasse diagram has the ovals from the 3 adjacent faces. Faces whose ovals intersect do not touch.

Examples

The one-dimensional associahedron K3 represents the two parenthesizations ((xy)z) and (x(yz)) of three symbols, or the two triangulations of a square. It is itself a line segment.

The two-dimensional associahedron K4 represents the five parenthesizations of four symbols, or the five triangulations of a regular pentagon. It is itself a pentagon.

The three-dimensional associahedron K5 is an enneahedron topologically equivalent to the order-4 truncated triangular bipyramid with nine faces (three squares and six pentagons) and fourteen vertices, and its dual is the triaugmented triangular prism.

Realization

Initially Jim Stasheff considered these objects as curvilinear polytopes. Subsequently, they were given coordinates as convex polytopes in several different ways; see the introduction of Ceballos, Santos & Ziegler (2015) for a survey.[3]

One method of realizing the associahedron is as the secondary polytope of a regular polygon.[3] In this construction, each triangulation of a regular polygon with n + 1 sides corresponds to a point in (n + 1)-dimensional Euclidean space, whose ith coordinate is the total area of the triangles incident to the ith vertex of the polygon. For instance, the two triangulations of the unit square give rise in this way to two four-dimensional points with coordinates (1, 1/2, 1, 1/2) and (1/2, 1, 1/2, 1). The convex hull of these two points is the realization of the associahedron K3. Although it lives in a 4-dimensional space, it forms a line segment (a 1-dimensional polytope) within that space. Similarly, the associahedron K4 can be realized in this way as a regular pentagon in five-dimensional Euclidean space, whose vertex coordinates are the cyclic permutations of the vector (1, 2 + φ, 1, 1 + φ, 1 + φ) where φ denotes the golden ratio. Because the possible triangles within a regular hexagon have areas that are integer multiples of each other, this construction can be used to give integer coordinates (in six dimensions) to the three-dimensional associahedron K5; however (as the example of K4 already shows) this construction in general leads to irrational numbers as coordinates.

Another realization, due to Jean-Louis Loday, is based on the correspondence of the vertices of the associahedron with n-leaf rooted binary trees, and directly produces integer coordinates in (n − 2)-dimensional space. The ith coordinate of Loday's realization is aibi, where ai is the number of leaf descendants of the left child of the ith internal node of the tree (in left-to-right order) and bi is the number of leaf descendants of the right child.[4]

It is possible to realize the associahedron directly in (n − 2)-dimensional space as a polytope for which all of the face normal vectors have coordinates that are 0, +1, or −1. There are exponentially many combinatorially distinct ways of doing this.[3][5]

K5 as an order-4 truncated triangular bipyramid

Because K5 is a polyhedron only with vertices in which 3 edges come together it is possible for a hydrocarbon to exist (similar to the Platonic hydrocarbons) whose chemical structure is represented by the skeleton of K5.[6] This “associahedrane” C14H14 would have the SMILES notation: C12-C3-C4-C1-C5-C6-C2-C7-C3-C8-C4-C5-C6-C78. Its edges would be of approximately equal length, but the vertices of each face would not necessarily be coplanar.

Indeed, K5 is a near-miss Johnson solid: it looks like it might be possible to make from squares and regular pentagons, but it is not. Either the vertices will not quite be coplanar, or the faces will have to be distorted slightly away from regularity.

Number of k-faces

 
   k = 1    2    3    4    5
n
1      1                               1
2      1    2                          3
3      1    5    5                    11
4      1    9   21   14               45
5      1   14   56   84   42         197

The number of (n − k)-dimensional faces of the associahedron of order n (Kn+1) is given by the number triangle[7] (n,k), shown on the right.

The number of vertices in Kn+1 is the n-th Catalan number (right diagonal in the triangle).

The number of facets in Kn+1 (for n≥2) is the n-th triangular number minus one (second column in the triangle), because each facet corresponds to a 2-subset of the n objects whose groupings form the Tamari lattice Tn, except the 2-subset that contains the first and the last element.

The number of faces of all dimensions (including the associahedron itself as a face, but not including the empty set) is a Schröder–Hipparchus number (row sums of the triangle).[8]

Diameter

In the late 1980s, in connection with the problem of rotation distance, Daniel Sleator, Robert Tarjan, and William Thurston provided a proof that the diameter of the n-dimensional associahedron Kn + 2 is at most 2n − 4 for infinitely many n and for all "large enough" values of n.[9] They also proved that this upper bound is tight when n is large enough, and conjectured that "large enough" means “strictly greater than 9”. This conjecture was proved in 2012 by Lionel Pournin.[10]

Scattering amplitudes

In 2017, Mizera[11] and Arkani-Hamed et al.[12] showed that the associahedron plays a central role in the theory of scattering amplitudes for the bi-adjoint cubic scalar theory. In particular, there exists an associahedron in the space of scattering kinematics, and the tree level scattering amplitude is the volume of the dual associahedron.[12] The associahedron also helps explaining the relations between scattering amplitudes of open and closed strings in string theory.[11] See also Amplituhedron.

gollark: (as this is based on a tower server and not a rack one, you might not even have ridiculously noisy fans in it!)
gollark: Anyway, I don't think this computer is worth £300, inasmuch as you could buy an old server with a Sandy Bridge era CPU for let's say £120, buy and install an equivalent GPU (if compatible, you might admittedly have some issues with power supply pinout) for £100 or so, possibly upgrade the RAM and disks for £50, and outperform that computer with £30 left over.
gollark: I did *not* just pluck £90 out of nowhere, since even if there wasn't the whole silicon shortage going on, used prices aren't conveniently documented by the manufacturer somewhere.
gollark: I checked eBay. If I wanted one, I could buy it for £90, and there are a few for those sorts of prices.
gollark: 120GB SSDs are at most £20 nowadays.

See also

References
  1. Stasheff, James Dillon (1963), "Homotopy associativity of H-spaces. I, II", Transactions of the American Mathematical Society, 108: 293–312, doi:10.2307/1993609, MR 0158400. Revised from a 1961 Ph.D. thesis, Princeton University, MR2613327.
  2. Tamari, Dov (1951), Monoïdes préordonnés et chaînes de Malcev, Thèse, Université de Paris, MR 0051833.
  3. Ceballos, Cesar; Santos, Francisco; Ziegler, Günter M. (2015), "Many non-equivalent realizations of the associahedron", Combinatorica, 35 (5): 513–551, arXiv:1109.5544, doi:10.1007/s00493-014-2959-9.
  4. Loday, Jean-Louis (2004), "Realization of the Stasheff polytope", Archiv der Mathematik, 83 (3): 267–278, arXiv:math/0212126, doi:10.1007/s00013-004-1026-y, MR 2108555.
  5. Hohlweg, Christophe; Lange, Carsten E. M. C. (2007), "Realizations of the associahedron and cyclohedron", Discrete & Computational Geometry, 37 (4): 517–543, arXiv:math.CO/0510614, doi:10.1007/s00454-007-1319-6, MR 2321739.
  6. IPME document about mini-fullerenes - page 30 (page 9 in this PDF) shows in chapter “7. Fullerene of fourteen carbon atoms C14” under “b) Base-truncated triangular bipyramid (Fig. 16)” a K5 polyhedron
  7. Sloane, N. J. A. (ed.). "Sequence A033282 (Triangle read by rows: T(n, k) is the number of diagonal dissections of a convex n-gon into k+1 regions.)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  8. Holtkamp, Ralf (2006), "On Hopf algebra structures over free operads", Advances in Mathematics, 207 (2): 544–565, arXiv:math/0407074, doi:10.1016/j.aim.2005.12.004, MR 2271016.
  9. Sleator, Daniel; Tarjan, Robert; Thurston, William (1988), "Rotation distance, triangulations, and hyperbolic geometry", Journal of the American Mathematical Society, 1 (3): 647–681, doi:10.1090/S0894-0347-1988-0928904-4, MR 0928904.
  10. Pournin, Lionel (2014), "The diameter of associahedra", Advances in Mathematics, 259: 13–42, arXiv:1207.6296, doi:10.1016/j.aim.2014.02.035, MR 3197650.
  11. Mizera, Sebastian (2017). "Combinatorics and topology of Kawai-Lewellen-Tye relations". JHEP. 2017:97. arXiv:1706.08527. Bibcode:2017JHEP...08..097M. doi:10.1007/JHEP08(2017)097.
  12. Arkani-Hamed, Nima; Bai, Yuntao; He, Song; Yan, Gongwang (2017), Scattering Forms and the Positive Geometry of Kinematics, Color and the Worldsheet, arXiv:1711.09102, Bibcode:2018JHEP...05..096A, doi:10.1007/JHEP05(2018)096.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.