Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\varepsilon$-regular parts in the Szemeredi lemma is grows like $O(\varepsilon^{-r})$ for some $r>0$. Or are the only available bounds always power towers in $\varepsilon$?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ I imagine for random graphs you only need very few parts with high probability — after all, the condition of regularity is an approximation of being random. The main strength of the regularity lemma is that it works for all graphs $\endgroup$– Daniel WeberCommented Apr 5 at 10:46
-
$\begingroup$ @Command Master Exactly what I expected, but still I cannot find a formal statement where one gets nice bounds. $\endgroup$– ABIMCommented Apr 5 at 12:57
-
1$\begingroup$ Malliaris and Shelah have shown that the number of parts needed grows only like $\epsilon^{-r}$ it $G$ doesn't contain half-graphs of size $O(\log r)$. See, for example, shelah.logic.at/files/217705/… $\endgroup$– Thomas BloomCommented Apr 7 at 14:16
Add a comment
|