{
  "id": "0911.2908",
  "version": "v1",
  "published": "2009-11-15T19:21:26.000Z",
  "updated": "2009-11-15T19:21:26.000Z",
  "title": "How long does it take to generate a group?",
  "authors": [
    "Benjamin Klopsch",
    "Vsevolod F. Lev"
  ],
  "journal": "J. Algebra 261 (2003), no. 1, 145--171",
  "doi": "10.1016/S0021-8693(02)00671-3",
  "categories": [
    "math.GR",
    "math.NT"
  ],
  "abstract": "The diameter of a finite group $G$ with respect to a generating set $A$ is the smallest non-negative integer $n$ such that every element of $G$ can be written as a product of at most $n$ elements of $A \\cup A^{-1}$. We denote this invariant by $\\diam_A(G)$. It can be interpreted as the diameter of the Cayley graph induced by $A$ on $G$ and arises, for instance, in the context of efficient communication networks. In this paper we study the diameters of a finite abelian group $G$ with respect to its various generating sets $A$. We determine the maximum possible value of $\\diam_A(G)$ and classify all generating sets for which this maximum value is attained. Also, we determine the maximum possible cardinality of $A$ subject to the condition that $\\diam_A(G)$ is \"not too small\". Connections with caps, sum-free sets, and quasi-perfect codes are discussed.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-11-15T19:21:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20K01",
      "20F05"
    ],
    "keywords": [
      "generating set",
      "efficient communication networks",
      "finite abelian group",
      "cayley graph",
      "finite group"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0911.2908K"
    }
  }
}