{"id":"arxiv/2609.25127","url":"https://arxiv.org/abs/2609.25127","tags":["math.CO","cs.DS","math.LO"],"score":0,"title":"Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds","domain":"math.CO","source":"arxiv","authors":["Leonardo N. Coregliano","Fernando G. Jeronimo"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-20","reactions":{}}