{
  "id": "1108.4995",
  "version": "v3",
  "published": "2011-08-25T02:25:40.000Z",
  "updated": "2012-02-08T00:14:03.000Z",
  "title": "An undecidability result on limits of sparse graphs",
  "authors": [
    "Endre Csóka"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO",
    "math.LO",
    "math.PR"
  ],
  "abstract": "Given a set B of finite rooted graphs and a radius r as an input, we prove that it is undecidable to determine whether there exists a sequence (G_i) of finite bounded degree graphs such that the rooted r-radius neighbourhood of a random node of G_i is isomorphic to a rooted graph in B with probability tending to 1. Our proof implies a similar result for the case where the sequence (G_i) is replaced by a unimodular random graph.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2012-02-08T00:14:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "sparse graphs",
      "undecidability result",
      "unimodular random graph",
      "finite bounded degree graphs",
      "similar result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1108.4995C"
    }
  }
}