Hypergraph regularity and quasi-randomness
Hypergraph regularity and quasi-randomness
复制标题
超图规律性和准随机性
DOI：
10.1137/1.9781611973068.26
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Schacht
中科院分区：
文献类型：
--
作者：
B. Nagle;A. Poerschke;V. Rödl;M. Schacht
Thomason和Chung、Graham和Wilson是第一个系统地研究拟随机图和超图的人，并证明了随机图的几个性质在确定性意义上相互暗示。他们的准随机性概念与早期Szemeredi正则性引理中的e-正则性概念相匹配。与此相反，不存在“自然”超图正则性引理匹配的概念，拟随机超图考虑这些作者。
本文研究了3-一致超图的拟随机性的几个概念，它们对应于Frankl和Rodl，Gowers和Haxell，Nagle和Rodl的正则性引理。我们建立了这些引理的正则性的三个概念之间的等价。由于Haxell等人的正则性引理是算法的，我们得到了Frankl-Rodl引理（其特例）和Gowers引理的算法版本作为推论。作为进一步的推论，我们得到了Frankl-Rodl引理的特殊情况（我们可以使其算法化）允许相应的计数引理。(This一个推论遵循等价性，并且Gowers的正则性引理或Haxell等人的正则性引理允许计数引理。）
Thomason and Chung, Graham, and Wilson were the first to systematically study quasi-random graphs and hypergraphs, and proved that several properties of random graphs imply each other in a deterministic sense. Their concepts of quasi-randomness match the notion of e-regularity from the earlier Szemeredi regularity lemma. In contrast, there exists no "natural" hypergraph regularity lemma matching the notions of quasi-random hypergraphs considered by those authors.
We study several notions of quasi-randomness for 3-uniform hypergraphs which correspond to the regularity lemmas of Frankl and Rodl, Gowers and Haxell, Nagle and Rodl. We establish an equivalence among the three notions of regularity of these lemmas. Since the regularity lemma of Haxell et al. is algorithmic, we obtain algorithmic versions of the lemmas of Frankl-Rodl (a special case thereof) and Gowers as corollaries. As a further corollary, we obtain that the special case of the Frankl-Rodl lemma (which we can make algorithmic) admits a corresponding counting lemma. (This corollary follows by the equivalences and that the regularity lemma of Gowers or that of Haxell et al. admits a counting lemma.)