The ineffectiveness of the regularity lemma for bounded degree graphs

Abstract

We show that for any $\Delta \ge 3$, there is no bound computable from $(\epsilon ,r)$ on the size of a graph required to approximate a graph of maximum degree at most $\Delta$ up to $\epsilon$ error in $r$-neighborhood statistics. This provides a negative answer to a question posed by Lovász. Our result is a direct consequence of the recent celebrated work of Bowen, Chapman, Lubotzky, and Vidick, which refutes the Aldous-Lyons conjecture.

10 pages, 2 figures, to appear in BLMS