{
  "id": "2505.06215",
  "version": "v1",
  "published": "2025-05-09T17:48:59.000Z",
  "updated": "2025-05-09T17:48:59.000Z",
  "title": "A note on the ineffectiveness of the regularity lemma for bounded degree graphs",
  "authors": [
    "Clark Lyons",
    "Grigory Terlov",
    "Zoltán Vidnyánszky"
  ],
  "comment": "10 pages, 2 figures",
  "categories": [
    "math.CO",
    "math.LO"
  ],
  "abstract": "We show that for any $\\Delta \\geq 3$, there is no bound computable from $(\\varepsilon, r)$ on the size of a graph required to approximate a graph of maximum degree at most $\\Delta$ up to $\\varepsilon$ error in $r$-neighborhood statistics. This provides a negative answer to a question posed by Lov\\'asz. Our result is a direct consequence of the recent celebrated work of Bowen, Chapman, Lubotzky, and Vidick, which refutes the Aldous--Lyons conjecture.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-05-09T17:48:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bounded degree graphs",
      "regularity lemma",
      "ineffectiveness",
      "neighborhood statistics",
      "maximum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}