{
  "id": "1607.08303",
  "version": "v1",
  "published": "2016-07-28T03:27:56.000Z",
  "updated": "2016-07-28T03:27:56.000Z",
  "title": "Linear programming and the intersection of subgroups in free groups",
  "authors": [
    "Sergei V. Ivanov"
  ],
  "comment": "16 pages, 2 figures. arXiv admin note: text overlap with arXiv:1607.03052",
  "categories": [
    "math.GR",
    "cs.DM",
    "math.OC"
  ],
  "abstract": "We study the intersection of finitely generated subgroups of free groups by utilizing the method of linear programming. We prove that if $H_1$ is a finitely generated subgroup of a free group $F$, then the Walter Neumann coefficient $\\sigma(H_1)$ of $H_1$ is rational and can be computed in deterministic exponential time of size of $H_1$. This coefficient $\\sigma(H_1)$ is a minimal nonnegative real number such that, for every finitely generated subgroup $H_2$ of $F$, it is true that $\\bar{ {\\rm r}}(H_1, H_2) \\le \\sigma(H_1) \\bar{ {\\rm r}}(H_1) \\bar{ {\\rm r}}(H_2)$, where $\\bar{ {\\rm r}} (H) := \\max ( {\\rm r} (H)-1,0)$ is the reduced rank of $H$, ${\\rm r}(H)$ is the rank of $H$, and $\\bar{ {\\rm r}}(H_1, H_2)$ is the reduced rank of a generalized intersection of $H_1, H_2$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-07-28T03:27:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20E05",
      "20E07",
      "20F65",
      "68Q25",
      "90C90"
    ],
    "keywords": [
      "free group",
      "linear programming",
      "finitely generated subgroup",
      "intersection",
      "reduced rank"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}