{
  "id": "2209.08507",
  "version": "v1",
  "published": "2022-09-18T08:35:59.000Z",
  "updated": "2022-09-18T08:35:59.000Z",
  "title": "Extensions and reductions of square-free words",
  "authors": [
    "Michał Dębski",
    "Jarosław Grytczuk",
    "Bartłomiej Pawlik"
  ],
  "comment": "11 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "A word is square-free if it does not contain a nonempty word of the form $XX$ as a factor. A famous 1906 result of Thue asserts that there exist arbitrarily long square-free words over a $3$-letter alphabet. We study square-free words with additional properties involving single-letter deletions and extensions of words. A square-free word is steady if it remains square-free after deletion of any single letter. We prove that there exist infinitely many steady words over a $4$-letter alphabet. We also demonstrate that one may construct steady words of any length by picking letters from arbitrary alphabets of size $7$ assigned to the positions of the constructed word. We conjecture that both bounds can be lowered to $4$, which is best possible. In the opposite direction, we consider square-free words that remain square-free after insertion of a single (suitably chosen) letter at every possible position in the word. We call them bifurcate. We prove a somewhat surprising fact, that over a fixed alphabet with at least three letters, every steady word is bifurcate. We also consider families of bifurcate words possessing a natural tree structure. In particular, we prove that there exists an infinite tree of doubly infinite bifurcate words over alphabet of size $12$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-09-18T08:35:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R15"
    ],
    "keywords": [
      "extensions",
      "letter alphabet",
      "reductions",
      "natural tree structure",
      "study square-free words"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}