Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds

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 $\mathrm{Lit}(G)\le \ell$ has a regular equipartition into excellent sets with $(1+o_{\epsilon \to 0,\ell }(1))\cdot {\epsilon }^{-\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_{\epsilon \to 0,\ell }(1))\cdot {\epsilon }^{-\ell -1}$. Dropping the equitability condition, we determine the asymptotics of non-equitable partitions up to a multiplicative $\log (1/\epsilon )$: every graph $G$ with $\mathrm{Lit}(G)\le \ell$ has a regular partition into excellent sets with $(1+o_{\epsilon \to 0,\ell }(1))\cdot {\epsilon }^{-\ell }\cdot \ln (1/\epsilon )$ 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_{\epsilon \to 0,\ell }(1))\cdot {\epsilon }^{-\ell }$. We also show that such partition can be obtained algorithmically efficiently in an approximation scheme fashion: replacing the $o_{\epsilon \to 0,\ell }(1)$ term above by a constant $c>0$, we obtain randomized $O_{c,\epsilon ,\ell }(n\cdot \log (n))$-time algorithms for partitions/equipartitions into good sets, a deterministic $O_{c,\epsilon ,\ell }(n^2)$-time algorithm for partitions into good sets, a deterministic $O_{c,\epsilon ,\ell }(n^6)$-time algorithm for equipartitions into good sets, a deterministic $O_{c,\ell ,\epsilon }(1)\cdot n^{O(\ell \cdot 2^{2\cdot \ell +4})}$-time algorithm for partitions/equipartitions into excellent sets, and $O_{c,\epsilon ,\ell }(\log (n+1))$-space algorithms for partitions/equipartitions into good/excellent sets.

170 pages, 2 figures, 1 table