{
  "id": "1409.7587",
  "version": "v1",
  "published": "2014-09-26T14:22:20.000Z",
  "updated": "2014-09-26T14:22:20.000Z",
  "title": "On the structure of graphs which are locally indistinguishable from a lattice",
  "authors": [
    "Itai Benjamini",
    "David Ellis"
  ],
  "comment": "48 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study the properties of finite graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to some fixed graph $F$. This is a natural extension of the study of regular graphs, and of the study of graphs of constant link. We focus on the case where $F$ is $\\mathbb{L}^d$, the $d$-dimensional square lattice. We obtain a characterisation of all the finite graphs in which the ball of radius $2$ around each vertex is isomorphic to the ball of radius $2$ in $\\mathbb{L}^2$, and of all the finite graphs in which the ball of radius $3$ around each vertex is isomorphic to the ball of radius $3$ in $\\mathbb{L}^d$, for each integer $d \\geq 3$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. Our proofs use a mixture of techniques and results from combinatorics, algebraic topology and group theory.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-09-26T14:22:20.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75"
    ],
    "keywords": [
      "finite graphs",
      "locally indistinguishable",
      "regular graphs",
      "dimensional square lattice",
      "graph isomorphic"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 48,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1409.7587B"
    }
  }
}