Diameter estimates for graph associahedra

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 $\hat{I}˜(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 $\hat{I}˜(n\log n)$. Finally, we give the exact diameter of the associahedra of complete split and of unbalanced complete bipartite graphs.

20 pages, 6 figures. Exact diameter proofs added for new classes of graph associahedra