{
  "id": "2211.07984",
  "version": "v1",
  "published": "2022-11-15T08:38:37.000Z",
  "updated": "2022-11-15T08:38:37.000Z",
  "title": "The rotation distance of brooms",
  "authors": [
    "Jean Cardinal",
    "Lionel Pournin",
    "Mario Valencia-Pabon"
  ],
  "comment": "24 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The associahedron $\\mathcal{A}(G)$ of a graph $G$ has the property that its vertices can be thought of as the search trees on $G$ and its edges as the rotations between two search trees. If $G$ is a simple path, then $\\mathcal{A}(G)$ is the usual associahedron and the search trees on $G$ are binary search trees. Computing distances in the graph of $\\mathcal{A}(G)$ (or equivalently, the rotation distance between two binary search trees) is a major open problem. Here, we consider the different case when $G$ is a complete split graph. In that case, $\\mathcal{A}(G)$ interpolates between the stellohedron and the permutohedron, and all the search trees on $G$ are brooms. We show that the rotation distance between any two such brooms and therefore the distance between any two vertices in the graph of the associahedron of $G$ can be computed in quasi-quadratic time in the number of vertices of $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-15T08:38:37.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "rotation distance",
      "binary search trees",
      "major open problem",
      "complete split graph",
      "simple path"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}