We consider a natural notion of search trees on graphs, which we show is ubiquitous in various areas of discrete mathematics and computer science. Search trees on graphs can be modified by local operations called rotations, which generalize rotations in binary search trees. The rotation graph of search trees on a graph $G$ is the skeleton of a polytope called the graph associahedron of $G$.We consider the case where the graph $G$ is a tree. We construct a family of trees $G$ on $n$ vertices and pairs of search trees on $G$ such that the minimum number of rotations required to transform one search tree into the other is $\Omega (n\log n)$. This implies that the worst-case diameter of tree associahedra is $\Theta (n\log n)$, which answers a question from Thibault Manneville and Vincent Pilaud. The proof relies on a notion of projection of a search tree which may be of independent interest.
Jean Cardinal
1
;
Stefan Langerman
1
;
Pablo Pérez-Lantero
2
1
Université libre de Bruxelles (ULB)
2
Universidad de Santiago
Jean Cardinal; Stefan Langerman; Pablo Pérez-Lantero. On the diameter of tree associahedra. The electronic journal of combinatorics, Tome 25 (2018) no. 4. doi: 10.37236/7762
@article{10_37236_7762,
author = {Jean Cardinal and Stefan Langerman and Pablo P\'erez-Lantero},
title = {On the diameter of tree associahedra},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {4},
doi = {10.37236/7762},
zbl = {1398.05060},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7762/}
}
TY - JOUR
AU - Jean Cardinal
AU - Stefan Langerman
AU - Pablo Pérez-Lantero
TI - On the diameter of tree associahedra
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/7762/
DO - 10.37236/7762
ID - 10_37236_7762
ER -
%0 Journal Article
%A Jean Cardinal
%A Stefan Langerman
%A Pablo Pérez-Lantero
%T On the diameter of tree associahedra
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/7762/
%R 10.37236/7762
%F 10_37236_7762
