{
  "id": "1802.02002",
  "version": "v1",
  "published": "2018-02-06T15:30:39.000Z",
  "updated": "2018-02-06T15:30:39.000Z",
  "title": "On the structure of random graphs that are locally indistinguishable from a lattice",
  "authors": [
    "Itai Benjamini",
    "David Ellis"
  ],
  "comment": "58 pages",
  "categories": [
    "math.CO",
    "math.GR",
    "math.PR"
  ],
  "abstract": "We study the properties of finite graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to the ball of radius $r$ in some fixed vertex-transitive graph $F$. This is a natural extension of the study of regular graphs. We focus on the case where $F$ is $\\mathbb{L}^d$, the graph of the $d$-dimensional square lattice. In a previous work [I. Benjamini, D. Ellis, On the structure of graphs which are locally indistinguishable from a lattice, {\\em Forum of Mathematics, Sigma} 4 (2016), e31.], the authors obtained a characterisation of all the $n$-vertex graphs in which the ball of radius $r$ around each vertex is isomorphic to the ball of radius $r$ in $\\mathbb{L}^d$, for each pair of integers $d,r$ such that $d \\geq 2$ and $r \\geq 3$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. In this paper, we estimate the number of unlabelled, $n$-vertex graphs which have the above property (in the case where $r$ is at least linear in $d$). This number grows like a stretched-exponential, again in contrast with the situation for regular graphs. We use this estimate to obtain results on the typical properties of a uniform random such graph. In particular, we show that with high probability, the largest component of this random graph has size $O(n^{1-\\epsilon})$ for some fixed $\\epsilon>0$ depending only upon $d$, but that there are only $o(n)$ vertices in bounded-size components. Our proofs use a mixture of techniques and results from group theory, topology, analytic number theory and combinatorics.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-02-06T15:30:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C30",
      "20H15"
    ],
    "keywords": [
      "random graph",
      "locally indistinguishable",
      "regular graphs",
      "vertex graphs",
      "dimensional square lattice"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 58,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}