Bounds for graph regularity and removal lemmas
Bounds for graph regularity and removal lemmas
复制标题
图正则性和移除引理的界限
DOI：
10.1007/s00039-012-0171-x
复制
发表时间：
2011
影响因子：
2.2
通讯作者：
J. Fox
中科院分区：
文献类型：
--
作者：
D. Conlon;J. Fox
我们证明了，对于任意正整数k，存在一个图，其中它的顶点的任意公平划分为k个部分，至少有ck ~ 2/log*k对部分不是$${\displaystyle $$}-正则的，其中$${c，\displaystyle\mathbb {0 }$$是绝对常数.这个界限是紧的常数c和地址的问题高尔斯的数量不规则对Szemerédi的规律性引理。为了获得对不规则对的一些控制，另一个正则性引理，称为强正则性引理，由阿隆，费舍尔，Krivelevich和Szegedy开发。对于这个引理，我们证明了一个下界的wowzer-type，这是一个更高的水平，在阿克曼层次比塔功能，在强正则性引理的部分的数量，基本上匹配的上限。另一方面，对于导出图移除引理，强正则引理的标准应用，我们找到了一个不同的证明，它产生了一个塔型界。我们还讨论了几个相关的正则性引理的界，包括Frieze和Kannan的弱正则性引理以及最近建立的正则逼近定理。特别地，我们证明了近似参数为$${\displaystyle $$}的弱划分可能需要多达$${2^{\Omega}（\displaystyle\Omega ^{-2}）}$$部分。这是紧到隐含常数，并解决了一个问题的研究Lovász和Szegedy。
We show, for any positive integer k, that there exists a graph in which any equitable partition of its vertices into k parts has at least ck2/log*k pairs of parts which are not $${\epsilon}$$-regular, where $${c,\epsilon >0 }$$ are absolute constants. This bound is tight up to the constant c and addresses a question of Gowers on the number of irregular pairs in Szemerédi’s regularity lemma. In order to gain some control over irregular pairs, another regularity lemma, known as the strong regularity lemma, was developed by Alon, Fischer, Krivelevich, and Szegedy. For this lemma, we prove a lower bound of wowzer-type, which is one level higher in the Ackermann hierarchy than the tower function, on the number of parts in the strong regularity lemma, essentially matching the upper bound. On the other hand, for the induced graph removal lemma, the standard application of the strong regularity lemma, we find a different proof which yields a tower-type bound. We also discuss bounds on several related regularity lemmas, including the weak regularity lemma of Frieze and Kannan and the recently established regular approximation theorem. In particular, we show that a weak partition with approximation parameter $${\epsilon}$$ may require as many as $${2^{\Omega}(\epsilon^{-2})}$$ parts. This is tight up to the implied constant and solves a problem studied by Lovász and Szegedy.