{
  "abstract": "In this paper, we determine the precise asymptotics of the number of parts of stable regularity equipartitions in terms of the Littlestone dimension: every graph $G$ of Littlestone dimension $\\operatorname{Lit}(G)\\leq\\ell$ has a regular equipartition into excellent sets with $(1 + o_{ε\\to 0,\\ell}(1))\\cdotε^{-\\ell-1}$ parts and in the other direction, for every $\\ell\\in\\mathbb{N}_+$, there is an infinite family of graphs, all of Littlestone dimension $\\ell$, whose equipartitions into good sets must have size at least $(1 + o_{ε\\to 0,\\ell}(1))\\cdotε^{-\\ell-1}$. Dropping the equitability condition, we determine the asymptotics of non-equitable partitions up to a multiplicative $\\log(1/ε)$: every graph $G$ with $\\operatorname{Lit}(G)\\leq\\ell$ has a regular partition into excellent sets with $(1 + o_{ε\\to 0,\\ell}(1))\\cdotε^{-\\ell}\\cdot\\ln(1/ε)$ parts and in the other direction, for every $\\ell\\in\\mathbb{N}_+$, there is an infinite family of graphs, all of Littlestone dimension $\\ell$, whose partitions into good sets must have size at least $(1 + o_{ε\\to 0,\\ell}(1))\\cdotε^{-\\ell}$. We also show that such partition can be obtained algorithmically efficiently in an approximation scheme fashion: replacing the $o_{ε\\to 0,\\ell}(1)$ term above by a constant $c > 0$, we obtain randomized $O_{c,ε,\\ell}(n\\cdot\\log(n))$-time algorithms for partitions/equipartitions into good sets, a deterministic $O_{c,ε,\\ell}(n^2)$-time algorithm for partitions into good sets, a deterministic $O_{c,ε,\\ell}(n^6)$-time algorithm for equipartitions into good sets, a deterministic $O_{c,\\ell,ε}(1)\\cdot n^{O(\\ell\\cdot 2^{2\\cdot\\ell+4})}$-time algorithm for partitions/equipartitions into excellent sets, and $O_{c,ε,\\ell}(\\log(n+1))$-space algorithms for partitions/equipartitions into good/excellent sets.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.25127",
  "author_total": 2,
  "authors": [
    {
      "name": "Leonardo N. Coregliano"
    },
    {
      "name": "Fernando G. Jeronimo"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/3mkmsm515n73x.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.25127",
  "fulltext_url": null,
  "id": "3mkmsm515n73x",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.25127",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "arxiv",
      "math.LO"
    ],
    [
      "openalex",
      "2607|Limits and Structures in Graph Theory"
    ]
  ],
  "openalex": "W7214126884",
  "pdf_url": "https://arxiv.org/pdf/2609.25127",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-20",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/3mkmsm515n73x.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:23:43Z",
      "native_id": "2609.25127",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.25127"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:math.LO",
      "subfield": "logic-foundations"
    }
  ],
  "title": "Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds",
  "title_text": "Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds",
  "type": "preprint",
  "updated_at": "2026-10-30T12:23:43Z",
  "url": "https://research.draconitic.com/paper/3mkmsm515n73x",
  "venue": "arXiv",
  "versions": []
}