A Wowzer‐type lower bound for the strong regularity lemma
A Wowzer‐type lower bound for the strong regularity lemma
复制标题
强正则引理的 Wowzer 型下界
DOI：
10.1112/plms/pds045
复制
发表时间：
2011
影响因子：
1.8
通讯作者：
A. Shapira
中科院分区：
文献类型：
--
作者：
S. Kalyanasundaram;A. Shapira
Szemerédi的正则性引理断言，人们可以将每个图划分为有界数量的拟随机二部图。然而，在某些应用中，人们希望对这些二部图的准随机性有很强的控制。Alon等人（'Efficient testing of large graphs'，Combinatorica 20（2000）451-476）获得了正则性引理的一个强大变体，它允许人们对这种准随机性的度量进行任意控制。然而，他们的证明只能保证产生一个分区，其中部分的数量由Wowzer函数给出，这是Tower函数的迭代版本。我们在这里证明，通过构造一个图H，这种类型的界是不可避免的，并且具有这样的性质：即使人们想要对正则划分的准随机性进行非常温和的控制，那么H的任何这样的划分中的部分的数量必须由Wowzer型函数给出。
The regularity lemma of Szemerédi asserts that one can partition every graph into a bounded number of quasi‐random bipartite graphs. In some applications however, one would like to have a strong control on how quasi‐random these bipartite graphs are. Alon et al. (‘Efficient testing of large graphs’, Combinatorica 20 (2000) 451–476) obtained a powerful variant of the regularity lemma, which allows one to have an arbitrary control on this measure of quasi‐randomness. However, their proof guaranteed only to produce a partition where the number of parts is given by the Wowzer function, which is the iterated version of the Tower function. We show here that a bound of this type is unavoidable by constructing a graph H, with the property that even if one wants a very mild control on the quasi‐randomness of a regular partition, then the number of parts in any such partition of H must be given by a Wowzer‐type function.