Diameter estimates for graph associahedra

DOI10.1007/S00026-022-00598-ZMaRDI QIDQ2093260zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Lionel Pournin, Mario Valencia-Pabon

Publication date 7 November 2022

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.16130

zbMATH Keywords

hypergraphic polytopesnestohedrapermutohedra

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) (n)-dimensional polytopes (52B11) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Polytopes and polyhedra (52B99)

Abstract: Graph associahedra are generalized permutohedra arising as special cases of nestohedra and hypergraphic polytopes. The graph associahedron of a graph $G$ encodes the combinatorics of search trees on $G$, defined recursively by a root $r$ together with search trees on each of the connected components of $G-r$. In particular, the skeleton of the graph associahedron is the rotation graph of those search trees. We investigate the diameter of graph associahedra as a function of some graph parameters. We give a tight bound of $Theta(m)$ on the diameter of trivially perfect graph associahedra on $m$ edges. We consider the maximum diameter of associahedra of graphs on $n$ vertices and of given tree-depth, treewidth, or pathwidth, and give lower and upper bounds as a function of these parameters. We also prove that the maximum diameter of associahedra of graphs of pathwidth two is $Theta(nlogn)$. Finally, we give the exact diameter of the associahedra of complete split and of unbalanced complete bipartite graphs.

Recommendations

• On the diameter of tree associahedra
• Diameters and geodesic properties of generalizations of the associahedron
• Graph properties of graph associahedra
• The diameter of associahedra
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra

Cites work

• A counterexample to the Hirsch conjecture
• Bit Reversal on Uniprocessors
• Competitive Online Search Trees on Trees
• Convexity in Graphs and Hypergraphs
• Coxeter complexes and graph-associahedra
• Dynamic Optimality—Almost
• Exploring the subexponential complexity of completion problems
• Faces of generalized permutohedra
• Fundamental groups of blow-ups.
• Gal's conjecture for nestohedra corresponding to complete bipartite graphs
• Graph properties of graph associahedra
• Homotopy Associativity of H-Spaces. I
• scientific article; zbMATH DE number 512918 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Lower Bounds for Accessing Binary Search Trees with Rotations
• Monoïdes préordonnés et chaînes de Malcev
• On low tree-depth decompositions
• On the diameter of tree associahedra
• Optimal node ranking of tree in linear time
• Ordered colourings
• Permutohedra, Associahedra, and Beyond
• Quasi-threshold graphs
• Rankings of Graphs
• Real root conjecture fails for five- and higher-dimensional spheres
• Realization of the Stasheff polytope
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Self-adjusting binary search trees
• Sparsity. Graphs, structures, and algorithms
• The asymptotic diameter of cyclohedra
• The Comparability Graph of a Tree
• The diameter of associahedra
• The geometry of binary search trees
• The Partial Order of a Polymatroid Extreme Point
• Trivially perfect graphs

Cited in

(11)

• On the diameter of tree associahedra
• The diameter of associahedra
• Diameters and geodesic properties of generalizations of the associahedron
• scientific article; zbMATH DE number 1262798 (Why is no real title available?)
• Diameter determination on restricted graph families
• Celebrating Loday's associahedron
• The rotation distance of brooms
• Shortest paths on polymatroids and hypergraphic polytopes
• Combinatorial generation via permutation languages. IV: Elimination trees
• Hardness of finding combinatorial shortest paths on graph associahedra
• Computing distances on graph associahedra is fixed-parameter tractable

This page was built for publication: Diameter estimates for graph associahedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2093260)