Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds

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 $\mathrm{Lit}(G)\le \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 $\mathrm{Lit}(G)\le \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.