{
  "id": "1304.7216",
  "version": "v2",
  "published": "2013-04-26T16:15:22.000Z",
  "updated": "2015-03-22T09:45:10.000Z",
  "title": "Counting self-avoiding walks",
  "authors": [
    "Geoffrey R. Grimmett",
    "Zhongyang Li"
  ],
  "comment": "Very minor changes for v2",
  "categories": [
    "math.CO",
    "math-ph",
    "math.MP",
    "math.PR"
  ],
  "abstract": "The connective constant $\\mu(G)$ of a graph $G$ is the asymptotic growth rate of the number of self-avoiding walks on $G$ from a given starting vertex. We survey three aspects of the dependence of the connective constant on the underlying graph $G$. Firstly, when $G$ is cubic, we study the effect on $\\mu(G)$ of the Fisher transformation (that is, the replacement of vertices by triangles). Secondly, we discuss upper and lower bounds for $\\mu(G)$ when $G$ is regular. Thirdly, we present strict inequalities for the connective constants $\\mu(G)$ of vertex-transitive graphs $G$, as $G$ varies. As a consequence of the last, the connective constant of a Cayley graph of a finitely generated group decreases strictly when a new relator is added, and increases strictly when a non-trivial group element is declared to be a generator. Special prominence is given to open problems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-04-26T16:15:22.000Z",
      "abstract": "The connective constant \\mu(G) of a graph G is the asymptotic growth rate of the number of self-avoiding walks on G from a given starting vertex. We survey three aspects of the dependence of the connective constant on the underlying graph G. Firstly, when G is cubic, we study the effect on \\mu(G) of the Fisher transformation (that is, the replacement of vertices by triangles). Secondly, we discuss upper and lower bounds for \\mu(G) when G is regular. Thirdly, we present strict inequalities for the connective constants \\mu(G) of vertex-transitive graphs G, as G varies. As a consequence of the last, the connective constant of a Cayley graph of a finitely generated group decreases strictly when a new relator is added, and increases strictly when a non-trivial group element is declared to be a generator. Special prominence is given to open problems.",
      "comment": null,
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-03-22T09:45:10.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "82B20",
      "60K35"
    ],
    "keywords": [
      "counting self-avoiding walks",
      "connective constant",
      "generated group decreases",
      "asymptotic growth rate",
      "non-trivial group element"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1304.7216G"
    }
  }
}