Associahedron K5 Faces, Ovals
   HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, an associahedron is an -dimensional
convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
in which each vertex corresponds to a way of correctly inserting opening and closing
parentheses A bracket is either of two tall fore- or back-facing punctuation marks commonly used to isolate a segment of text or data from its surroundings. They come in four main pairs of shapes, as given in the box to the right, which also gives their n ...
in a string of letters, and the
edges Enhanced Data rates for GSM Evolution (EDGE), also known as 2.75G and under various other names, is a 2G digital mobile phone technology for packet switched data transmission. It is a subset of General Packet Radio Service (GPRS) on the GS ...
correspond to single application of the
associativity In mathematics, the associative property is a property of some binary operations that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a Validity (logic), valid rule of replaceme ...
rule. Equivalently, the vertices of an associahedron correspond to the triangulations of a
regular polygon In Euclidean geometry, a regular polygon is a polygon that is Equiangular polygon, direct equiangular (all angles are equal in measure) and Equilateral polygon, equilateral (all sides have the same length). Regular polygons may be either ''convex ...
with 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 James Dillon Stasheff (born January 15, 1936, New York City) is an American mathematician, a professor emeritus of mathematics at the University of North Carolina at Chapel Hill. He works in algebraic topology and algebra as well as their applicat ...
, who rediscovered them in the early 1960s after earlier work on them by
Dov Tamari Dov Tamari (; born Bernhard Teitler; 29 April 1911 – 11 August 2006) was a German-born mathematician. He lived in Mandatory Palestine (now Israel), and in New York City. Biography Dov Tamari was born under the name Bernhard Teitler on 29 A ...
.


Examples

The one-dimensional associahedron ''K''3 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 ''K''4 represents the five parenthesizations of four symbols, or the five triangulations of a regular pentagon. It is itself a pentagon and is related to the ''pentagon diagram'' of a
monoidal category In mathematics, a monoidal category (or tensor category) is a category (mathematics), category \mathbf C equipped with a bifunctor :\otimes : \mathbf \times \mathbf \to \mathbf that is associative up to a natural isomorphism, and an Object (cate ...
. The three-dimensional associahedron ''K''5 is an enneahedron with nine faces (three disjoint quadrilaterals and six pentagons) and fourteen vertices, and its dual is the
triaugmented triangular prism The triaugmented triangular prism, in geometry, is a convex polyhedron with 14 equilateral triangles as its faces. It can be constructed from a triangular prism by attaching equilateral square pyramids to each of its three square faces. The same ...
.


Realization

Initially
Jim Stasheff James Dillon Stasheff (born January 15, 1936, New York City) is an American mathematician, a professor emeritus of mathematics at the University of North Carolina at Chapel Hill. He works in algebraic topology and algebra as well as their applicat ...
considered these objects as
curvilinear In geometry, curvilinear coordinates are a coordinate system for Euclidean space in which the coordinate lines may be curved. These coordinates may be derived from a set of Cartesian coordinates by using a transformation that is locally inv ...
polytopes. Subsequently, they were given coordinates as
convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
s in several different ways; see the introduction of for a survey.. One method of realizing the associahedron is as the secondary polytope of a regular polygon. In this construction, each triangulation of a regular polygon with ''n'' + 1 sides corresponds to a point in (''n'' + 1)-dimensional
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
, whose ''i''th coordinate is the total area of the triangles incident to the ''i''th vertex of the polygon. For instance, the two triangulations of the
unit square In mathematics, a unit square is a square whose sides have length . Often, ''the'' unit square refers specifically to the square in the Cartesian plane with corners at the four points ), , , and . Cartesian coordinates In a Cartesian coordinat ...
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 In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...
of these two points is the realization of the associahedron ''K''3. Although it lives in a 4-dimensional space, it forms a line segment (a 1-dimensional polytope) within that space. Similarly, the associahedron ''K''4 can be realized in this way as a
regular pentagon In geometry, a pentagon () is any five-sided polygon or 5-gon. The sum of the internal angles in a simple polygon, simple pentagon is 540°. A pentagon may be simple or list of self-intersecting polygons, self-intersecting. A self-intersecting ...
in five-dimensional Euclidean space, whose vertex coordinates are the
cyclic permutation In mathematics, and in particular in group theory, a cyclic permutation is a permutation consisting of a single cycle. In some cases, cyclic permutations are referred to as cycles; if a cyclic permutation has ''k'' elements, it may be called a ''k ...
s of the vector (1, 2 + φ, 1, 1 + φ, 1 + φ) where φ denotes the
golden ratio In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their summation, sum to the larger of the two quantities. Expressed algebraically, for quantities and with , is in a golden ratio to if \fr ...
. Because the possible triangles within a
regular hexagon In geometry, a hexagon (from Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°. Regular hexagon A regular hexagon is de ...
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 ''K''5; however (as the example of ''K''4 already shows) this construction in general leads to irrational numbers as coordinates. Another realization, due to
Jean-Louis Loday Jean-Louis Loday (12 January 1946 – 6 June 2012) was a French mathematician who worked on cyclic homology and who introduced Leibniz algebras (sometimes called Loday algebras) and Zinbiel algebras. He occasionally used the pseudonym Guillaume W ...
, 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 ''i''th coordinate of Loday's realization is ''aibi'', where ''ai'' is the number of leaf descendants of the left child of the ''i''th internal node of the tree (in left-to-right order) and ''bi'' is the number of leaf descendants of the right child. 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. Because ''K''5 is a polyhedron only with vertices in which 3 edges come together it is possible for a
hydrocarbon In organic chemistry, a hydrocarbon is an organic compound consisting entirely of hydrogen and carbon. Hydrocarbons are examples of group 14 hydrides. Hydrocarbons are generally colourless and Hydrophobe, hydrophobic; their odor is usually fain ...
to exist (similar to the
Platonic hydrocarbon In organic chemistry, a Platonic hydrocarbon is a hydrocarbon whose structure matches one of the five Platonic solids, with carbon atoms replacing its vertices, carbon–carbon bonds replacing its edges, and hydrogen atoms as needed. Not all Pla ...
s) whose chemical structure is represented by the skeleton of ''K''5. This " associahedrane" C14H14 would have the
SMILES A smile is a facial expression formed primarily by flexing the muscles at the sides of the mouth. Some smiles include a contraction of the muscles at the corner of the eyes, an action known as a Duchenne smile. Among humans, a smile expresses d ...
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, ''K''5 is a
near-miss Johnson solid In geometry, a near-miss Johnson solid is a strictly convex set, convex polyhedron whose face (geometry), faces are close to being regular polygons but some or all of which are not precisely regular. Thus, it fails to meet the definition of a John ...
: 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

The number of (''n'' − ''k'')-dimensional faces of the associahedron of order ''n'' (K''n''+1) is given by the number triangle (''n'',''k''), shown on the right. The number of vertices in ''K''''n''+1 is the ''n''-th
Catalan number The Catalan numbers are a sequence of natural numbers that occur in various Enumeration, counting problems, often involving recursion, recursively defined objects. They are named after Eugène Charles Catalan, Eugène Catalan, though they were p ...
(right diagonal in the triangle). The number of facets in ''K''''n''+1 (for ''n''≥2) is the ''n''-th
triangular number A triangular number or triangle number counts objects arranged in an equilateral triangle. Triangular numbers are a type of figurate number, other examples being square numbers and cube numbers. The th triangular number is the number of dots in ...
minus one (second column in the triangle), because each facet corresponds to a 2-
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
of the ''n'' objects whose groupings form the Tamari lattice T''n'', 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).


Diameter

In the late 1980s, in connection with the problem of
rotation distance In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial e ...
,
Daniel Sleator Daniel Dominic Kaplan Sleator (born 10 December 1953) is a professor of computer science at Carnegie Mellon University, Pittsburgh, United States. In 1999, he won the ACM Paris Kanellakis Award (jointly with Robert Tarjan) for the splay tree d ...
,
Robert Tarjan Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph theory algorithms, including his strongly connected components algorithm, and co-inventor of both splay trees a ...
, and
William Thurston William Paul Thurston (October 30, 1946August 21, 2012) was an American mathematician. He was a pioneer in the field of low-dimensional topology and was awarded the Fields Medal in 1982 for his contributions to the study of 3-manifolds. Thurst ...
provided a proof that the diameter of the ''n''-dimensional associahedron ''K''''n'' + 2 is at most 2''n'' − 4 for infinitely many ''n'' and for all "large enough" values of ''n''. 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..


Scattering amplitudes

In 2017, Mizera and Arkani-Hamed et al.. 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. The associahedron also helps explaining the relations between scattering amplitudes of open and closed strings in
string theory In physics, string theory is a theoretical framework in which the point-like particles of particle physics are replaced by one-dimensional objects called strings. String theory describes how these strings propagate through space and intera ...
.


See also

*
Cyclohedron In geometry, the cyclohedron is a -dimensional polytope where can be any non-negative integer. It was first introduced as a combinatorial object by Raoul Bott and Clifford Taubes and, for this reason, it is also sometimes called the Bott–Taube ...
, a polytope whose definition allows parentheses to wrap around in
cyclic order In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "". One does not say that east is "more clockwise" than west. Ins ...
. *
Flip graph In mathematics, a flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are speci ...
, a generalisation of the
1-skeleton In mathematics, particularly in algebraic topology, the of a topological space presented as a simplicial complex (resp. CW complex) refers to the subspace that is the union of the simplices of (resp. cells of ) of dimensions In other wor ...
of the associahedron. *
Permutohedron In mathematics, the permutohedron (also spelled permutahedron) of order is an -dimensional polytope embedded in an -dimensional space. Its vertex (geometry), vertex coordinates (labels) are the permutations of the first natural numbers. The edg ...
, a polytope that is defined from
commutativity In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Perhaps most familiar as a p ...
in a similar way to the definition of the associahedron from associativity. *
Permutoassociahedron In mathematics, the permutoassociahedron is an n-dimensional polytope whose vertices correspond to the bracketings of the permutations of n+1 terms and whose edges connect two bracketings that can be obtained from one another either by moving a p ...
, a polytope whose vertices are bracketed permutations. * Tamari lattice, a
lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an or ...
whose graph is the skeleton of the associahedron.


References


External links

*{{mathworld, title=Associahedron, urlname=Associahedron, author=Bryan Jacobs
Strange Associations
- 2007 AMS column about Associahedra by Bill Casselman
Ziegler's Lecture on the Associahedron
Notes from a lecture by Günter Ziegler at the
Autonomous University of Barcelona The Autonomous University of Barcelona (; Spanish: ; ; UAB) is a public university mostly located in Cerdanyola del Vallès, near the city of Barcelona in Catalonia, Spain. , the university consists of 57 departments in the experimental, lif ...
, 2009.
Lecture on Associahedra and Cyclohedra
MSRI lecture notes. Polytopes