{
  "id": "0711.2800",
  "version": "v3",
  "published": "2007-11-18T17:05:30.000Z",
  "updated": "2009-07-02T15:30:22.000Z",
  "title": "Parameter testing with bounded degree graphs of subexponential growth",
  "authors": [
    "Gabor Elek"
  ],
  "comment": "To appear in Random Structures and Algorithms. (note that the title has changed)",
  "categories": [
    "math.CO",
    "math-ph",
    "math.MP"
  ],
  "abstract": "Parameter testing algorithms are using constant number of queries to estimate the value of a certain parameter of a very large finite graph. It is well-known that graph parameters such as the independence ratio or the edit-distance from 3-colorability are not testable in bounded degree graphs. We prove, however, that these and several other interesting graph parameters are testable in bounded degree graphs of subexponential growth.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2009-07-02T15:30:22.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C99"
    ],
    "keywords": [
      "bounded degree graphs",
      "subexponential growth",
      "large finite graph",
      "parameter testing algorithms",
      "constant number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0711.2800E"
    }
  }
}