Diameters and geodesic properties of generalizations of the associahedron

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

Diameters and geodesic properties of generalizations of the associahedron

C. Ceballos
, T. Manneville
, V. Pilaud
, L. Pournin

York University
Laboratoire d'Informatique (LIX)
University Paris 13

Research output: Contribution to journal › Conference article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	345-356
Number of pages	12
Journal	Discrete Mathematics and Theoretical Computer Science
Publication status	Published - 1 Jan 2015
Event	27th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2015 - Daejeon, Korea, Republic of Duration: 6 Jul 2015 → 10 Jul 2015

Keywords

Flip graph diameter
Generalized associahedra
Graph associahedra
Non-leaving-face property

Cite this

@article{c9de0edd1c964fab85a61bd5eba43b9d,

title = "Diameters and geodesic properties of generalizations of the associahedron",

abstract = "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.",

keywords = "Flip graph diameter, Generalized associahedra, Graph associahedra, Non-leaving-face property",

author = "C. Ceballos and T. Manneville and V. Pilaud and L. Pournin",

note = "Publisher Copyright: {\textcopyright} 2015 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France; 27th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2015 ; Conference date: 06-07-2015 Through 10-07-2015",

year = "2015",

month = jan,

day = "1",

language = "English",

pages = "345--356",

journal = "Discrete Mathematics and Theoretical Computer Science",

issn = "1462-7264",

}

TY - JOUR

T1 - Diameters and geodesic properties of generalizations of the associahedron

AU - Ceballos, C.

AU - Manneville, T.

AU - Pilaud, V.

AU - Pournin, L.

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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.

AB - 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.

KW - Flip graph diameter

KW - Generalized associahedra

KW - Graph associahedra

KW - Non-leaving-face property

UR - https://www.scopus.com/pages/publications/85055949498

M3 - Conference article

AN - SCOPUS:85055949498

SN - 1462-7264

SP - 345

EP - 356

JO - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

T2 - 27th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2015

Y2 - 6 July 2015 through 10 July 2015

ER -

Diameters and geodesic properties of generalizations of the associahedron

Abstract

Keywords

Other files and links

Fingerprint

Cite this