On the diameter of tree associahedra (Q1991427): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 18:11, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the diameter of tree associahedra |
scientific article |
Statements
On the diameter of tree associahedra (English)
0 references
30 October 2018
0 references
Summary: 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 \textit{T. Manneville} and \textit{V. Pilaud} [Sémin. Lothar. Comb. 73, B73d, 31 p. (2015; Zbl 1326.05041)]. The proof relies on a notion of projection of a search tree which may be of independent interest.
0 references
associahedra
0 references
diameter
0 references