{
  "id": "1606.08833",
  "version": "v1",
  "published": "2016-06-28T19:35:33.000Z",
  "updated": "2016-06-28T19:35:33.000Z",
  "title": "Computing area in group presentations",
  "authors": [
    "Timothy Riley"
  ],
  "comment": "8 pages, 1 figure",
  "categories": [
    "math.GR"
  ],
  "abstract": "The width of a word $w$ representing an element in a free group $F(a,b)$ was defined by Jiang to be the minimal $N$ such that $w$ freely equals a product of $N$ conjugates of powers of $a$ and $b$. In 1991 Grigorchuk and Kurchanov gave an algorithm computing $N$ and asked whether it could be done in polynomial time. We use dynamic programming answer this affirmatively. The width of $w$ can be reinterpreted as its area with respect to the presentation $\\langle a, b \\mid a^k, b^k; \\ k \\in \\mathbb{N} \\rangle$ of the trivial group. We also give a polynomial time algorithm finding the areas of words in the group presentation $\\langle a, b \\mid a, b \\rangle$. These problems have connections to computing the minimal number of fixed points in the homotopy class of a continuous self-map of a compact surface, RNA folding, and the design of liquid crystals.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-06-28T19:35:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F05",
      "20F10",
      "68W32",
      "68Q17"
    ],
    "keywords": [
      "group presentation",
      "computing area",
      "liquid crystals",
      "free group",
      "trivial group"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}