Cesar Ceballos ; Thibault Manneville ; Vincent Pilaud ; Lionel Pournin - Diameters and geodesic properties of generalizations of the associahedron

dmtcs:2540 - Discrete Mathematics & Theoretical Computer Science, January 1, 2015, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015) - https://doi.org/10.46298/dmtcs.2540
Diameters and geodesic properties of generalizations of the associahedronConference paper

Authors: C. Ceballos ; T. Manneville ; V. Pilaud ; L. Pournin

    [en]
    The $n$-dimensional associahedron is a polytope whose vertices correspond to triangulations of a convex $(n + 3)$-gon and whose edges are flips between them. It was recently shown that the diameter of this polytope is $2n - 4$ as soon as $n > 9$. We study the diameters of the graphs of relevant generalizations of the associahedron: on the one hand the generalized associahedra arising from cluster algebras, and on the other hand the graph associahedra and nestohedra. Related to the diameter, we investigate the non-leaving-face property for these polytopes, which asserts that every geodesic connecting two vertices in the graph of the polytope stays in the minimal face containing both.

    [fr]
    L’associaèdre de dimension $n$ est un polytope dont les sommets correspondent aux triangulations d’un $(n + 3)$-gone convexe et dont les arêtes sont les échanges entre ces triangulations. Il a été récemment démontré que le diamètre de ce polytope est $2n - 4$ dès que $n > 9$. Nous étudions les diamètres des graphes de certaines généralisations de l’associaèdre : d’une part les associaèdres généralisés provenant des algèbres amassées, et d’autre part les associaèdres de graphes et les nestoèdres. En lien avec le diamètre, nous étudions si toutes les géodésiques entre deux sommets de ces polytopes restent dans la plus petite face les contenant.


    Volume: DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
    Section: Proceedings
    Published on: January 1, 2015
    Imported on: November 21, 2016
    Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] graph associahedra, generalized associahedra, non-leaving-face property, flip graph diameter

    Consultation statistics

    This page has been seen 537 times.
    This article's PDF has been downloaded 975 times.