A short proof of Gowers’ lower bound for the regularity lemma
A short proof of Gowers’ lower bound for the regularity lemma
复制标题
高尔斯正则引理下界的简短证明
DOI：
10.1007/s00493-014-3166-4
复制
发表时间：
2013
期刊：
影响因子：
1.1
通讯作者：
A. Shapira
中科院分区：
文献类型：
--
作者：
Guy Moshkovitz;A. Shapira
Gowers的一个著名结果指出，对于每个є>；0，都有一个图G，使得G的每个є-正则划分(在Szemerédi正则性引理的意义下)都有由1/є中高度多项式的指数塔所给出的阶。在这篇笔记中，我们给出了这一结果的一个新证明，它使用了一种明显更简单和更短的构造和正确性证明。
A celebrated result of Gowers states that for every є>0 there is a graph G such that every є-regular partition of G (in the sense of Szemerédi’s regularity lemma) has order given by a tower of exponents of height polynomial in 1/є. In this note we give a new proof of this result that uses a construction and proof of correctness that are significantly simpler and shorter.