Associahedron (original) (raw)
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 string 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 after earlier work on them by Dov Tamari.
| Property | Value |
|---|---|
| dbo:abstract | 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 string 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 after earlier work on them by Dov Tamari. (en) En mathématiques, et notamment en combinatoire algébrique, un associaèdre est une réalisation géométrique d'un treillis de Tamari. L'associaèdre Kn est un polytope (polyèdre convexe et borné) de dimension n-2 dans lequel chaque sommet correspond à une façon d'insérer des parenthèses ouvrantes et fermantes dans un mot de n lettres, et les arêtes correspondent à une application de la règle d'associativité. De manière équivalente, les sommets d'un associaèdre correspondent aux triangulations d'un polygone régulier à n+1 côtés et les arêtes correspondent à l’opération d'échange d'arêtes de la triangulation (flip en anglais), opération qui consiste à enlever une diagonale de la triangulation et à la remplacer par la diagonale opposée dans le quadrilatère qui apparaît. Enfin, la dualité entre arbres binaires et triangulations fait correspondre, aux sommets de l’associaèdre, les arbres binaires à n-1 nœuds, et les arêtes aux rotations dans les arbres. Les associaèdres sont également appelés polytopes de Stasheff, d'après Jim Stasheff qui les a redécouverts au début des années 1960, dix ans après Tamari. En 1988, Daniel Sleator, Robert Tarjan et William Thurston montrent que le diamètre des associaèdres n'est jamais plus grand que 2n-4 quand n est supérieur à 9. Ils montrent également que cette borne supérieure est atteinte quand n est suffisamment grand. Ils conjecturent alors que, dans cette phrase, « suffisamment grand » signifie « supérieur à 9 ». Cette conjecture a été résolue en 2012 par Lionel Pournin. (fr) In matematica, un associaedro è un politopo convesso in cui ogni vertice rappresenta un modo di inserire correttamente parentesi aperte e chiuse in una stringa di lettere e gli spigoli corrispondono ad una singola applicazione della proprietà associativa. I vertici dell'associaedro possono anche essere visti come le triangolazioni di un poligono regolare con lati. Gli associaedri sono anche chiamati politopi di Stasheff. (it) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Associahedron_K5_front.svg?width=300 |
| dbo:wikiPageExternalLink | http://gilkalai.wordpress.com/2009/02/28/ziegler%c2%b4s-lecture-on-the-associahedron/ https://web.archive.org/web/20121229115453/http:/www.msri.org/web/msri/scientific/workshops/show https://www.ams.org/featurecolumn/archive/associahedra.html |
| dbo:wikiPageID | 19698446 (xsd:integer) |
| dbo:wikiPageLength | 13205 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1113334090 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Amplituhedron dbr:Robert_Tarjan dbr:Enneahedron dbr:Monoidal_category dbr:Hydrocarbon dbr:Permutohedron dbr:Regular_hexagon dbr:Regular_pentagon dbr:Regular_polygon dbr:Cyclohedron dbr:Commutativity dbr:Mathematics dbr:SMILES dbr:Geometric_graph_theory dbr:Normal_(geometry) dbr:Golden_ratio dbr:N-skeleton dbr:Convex_hull dbr:Convex_polytope dbr:String_theory dbr:Dov_Tamari_(mathematician) dbr:Tamari_lattice dbr:Autonomous_University_of_Barcelona dbr:Triangular_number dbr:Triaugmented_triangular_prism dbr:William_Thurston dbr:Lattice_(order) dbr:Curvilinear dbr:Cyclic_order dbr:Cyclic_permutation dbr:Daniel_Sleator dbr:Euclidean_space dbr:Parentheses dbr:Flip_graph dbr:Jim_Stasheff dbr:Schröder–Hipparchus_number dbr:Associativity dbc:Polytopes dbr:Edge_(geometry) dbr:Jean-Louis_Loday dbr:Polygon_triangulation dbr:Catalan_number dbr:Unit_square dbr:Vertex_(geometry) dbr:Near-miss_Johnson_solid dbr:Triangular_array dbr:Facet_(geometry) dbr:Platonic_hydrocarbon dbr:Rotation_distance dbr:Permutoassociahedron dbr:Subset dbr:Günter_Ziegler dbr:Rooted_binary_tree dbr:Associahedrane dbr:File:Associahedron.gif dbr:File:Associahedron_K5_back.svg dbr:File:Associahedron_K5_faces,_ovals.svg dbr:File:Associahedron_K5_front.svg dbr:File:Tamari_lattice,_ovals.svg |
| dbp:author | Bryan Jacobs (en) |
| dbp:title | Associahedron (en) |
| dbp:urlname | Associahedron (en) |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Math dbt:Mathworld dbt:Mvar dbt:Reflist dbt:Short_description dbt:Sub |
| dcterms:subject | dbc:Polytopes |
| gold:hypernym | dbr:Polytope |
| rdfs:comment | 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 string 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 after earlier work on them by Dov Tamari. (en) In matematica, un associaedro è un politopo convesso in cui ogni vertice rappresenta un modo di inserire correttamente parentesi aperte e chiuse in una stringa di lettere e gli spigoli corrispondono ad una singola applicazione della proprietà associativa. I vertici dell'associaedro possono anche essere visti come le triangolazioni di un poligono regolare con lati. Gli associaedri sono anche chiamati politopi di Stasheff. (it) En mathématiques, et notamment en combinatoire algébrique, un associaèdre est une réalisation géométrique d'un treillis de Tamari. L'associaèdre Kn est un polytope (polyèdre convexe et borné) de dimension n-2 dans lequel chaque sommet correspond à une façon d'insérer des parenthèses ouvrantes et fermantes dans un mot de n lettres, et les arêtes correspondent à une application de la règle d'associativité. De manière équivalente, les sommets d'un associaèdre correspondent aux triangulations d'un polygone régulier à n+1 côtés et les arêtes correspondent à l’opération d'échange d'arêtes de la triangulation (flip en anglais), opération qui consiste à enlever une diagonale de la triangulation et à la remplacer par la diagonale opposée dans le quadrilatère qui apparaît. Enfin, la dualité entre ar (fr) |
| rdfs:label | Associahedron (en) Associaèdre (fr) Associaedro (it) |
| owl:sameAs | freebase:Associahedron wikidata:Associahedron dbpedia-fr:Associahedron dbpedia-it:Associahedron https://global.dbpedia.org/id/4TbL5 |
| prov:wasDerivedFrom | wikipedia-en:Associahedron?oldid=1113334090&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Associahedron.gif wiki-commons:Special:FilePath/Associahedron_K5_back.svg wiki-commons:Special:FilePath/Associahedron_K5_faces,_ovals.svg wiki-commons:Special:FilePath/Associahedron_K5_front.svg wiki-commons:Special:FilePath/Tamari_lattice,_ovals.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Associahedron |
| is dbo:wikiPageRedirects of | dbr:Stasheff_polytope |
| is dbo:wikiPageWikiLink of | dbr:Amplituhedron dbr:Enneahedron dbr:Permutohedron dbr:Cyclohedron dbr:Integral_polytope dbr:Timeline_of_category_theory_and_related_mathematics dbr:Geometric_combinatorics dbr:Geometric_graph_theory dbr:Cluster_algebra dbr:Combinatorics dbr:Pentagon dbr:Tamari_lattice dbr:Matrix_chain_multiplication dbr:Triaugmented_triangular_prism dbr:Flip_graph dbr:Covering_relation dbr:Jim_Stasheff dbr:Schröder–Hipparchus_number dbr:Lagrange_inversion_theorem dbr:Homotopy_associative_algebra dbr:Jean-Louis_Loday dbr:Polygon_triangulation dbr:A∞-operad dbr:Catalan_number dbr:Polyhedral_skeletal_electron_pair_theory dbr:Rotation_distance dbr:Permutoassociahedron dbr:Simple_polytope dbr:Stasheff_polytope |
| is dbp:dual of | dbr:Triaugmented_triangular_prism |
| is foaf:primaryTopic of | wikipedia-en:Associahedron |
