{
  "id": "1704.05884",
  "version": "v1",
  "published": "2017-04-19T18:24:29.000Z",
  "updated": "2017-04-19T18:24:29.000Z",
  "title": "Self-avoiding walks and connective constants",
  "authors": [
    "Geoffrey R. Grimmett",
    "Zhongyang Li"
  ],
  "categories": [
    "math.CO",
    "math-ph",
    "math.MP",
    "math.PR"
  ],
  "abstract": "The connective constant $\\mu(G)$ of a quasi-transitive graph $G$ is the asymptotic growth rate of the number of self-avoiding walks (SAWs) on $G$ from a given starting vertex. We survey several aspects of the relationship between the connective constant and the underlying graph $G$. $\\bullet$ We present upper and lower bounds for $\\mu$ in terms of the vertex-degree and girth of a transitive graph. $\\bullet$ We discuss the question of whether $\\mu\\ge\\phi$ for transitive cubic graphs (where $\\phi$ denotes the golden mean), and we introduce the Fisher transformation for SAWs (that is, the replacement of vertices by triangles). $\\bullet$ We present strict inequalities for the connective constants $\\mu(G)$ of transitive graphs $G$, as $G$ varies. $\\bullet$ 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 further generator. $\\bullet$ We describe so-called graph height functions within an account of \"bridges\" for quasi-transitive graphs, and indicate that the bridge constant equals the connective constant when the graph has a unimodular graph height function. $\\bullet$ A partial answer is given to the question of the locality of connective constants, based around the existence of unimodular graph height functions. $\\bullet$ Examples are presented of Cayley graphs of finitely presented groups that possess graph height functions (that are, in addition, harmonic and unimodular), and that do not. $\\bullet$ The review closes with a brief account of the \"speed\" of SAW.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-04-19T18:24:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "82B20",
      "60K35"
    ],
    "keywords": [
      "connective constant",
      "self-avoiding walks",
      "unimodular graph height function",
      "generated group decreases",
      "possess graph height functions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}