The ineffectiveness of the regularity lemma for bounded degree graphs

Clark Lyons, Grigory Terlov, Zoltán Vidnyánszky

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 $\va…