An algorithmic hypergraph regularity lemma
An algorithmic hypergraph regularity lemma
复制标题
算法超图正则引理
DOI：
10.1002/rsa.20739
复制
发表时间：
2017
影响因子：
1
通讯作者：
Schacht, Mathias
中科院分区：
文献类型：
--
作者：
Nagle, Brendan;Rödl, Vojtěch;Schacht, Mathias
szemersamodi的正则引理是图论中一个强有力的工具。它断言所有大图都承认其边集的有界划分，其中大多数类由均匀分布的边组成。这个结果最初的证明是非建设性的，后来由Alon、Duke、Lefmann、Rödl和Yuster给出了一个建设性的证明。szemersamedi的正则引理被许多作者推广到超图。Frankl和Rödl给出了一个关于三均匀超图的扩展，后来又被Rödl和Skokan扩展为三均匀超图。W.T. Gowers给出了另一个这样的扩展，使用了与Frankl， Rödl和Skokan不同的正则性概念。本文给出了超图的正则引理的构造性证明。
Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended tok‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.
登录
查看更多内容
超图的一致性引理
影响因子：
0.7
作者：
P. Frankl;V. Rödl
通讯作者：
V. Rödl
超图规律性和准随机性
DOI：
10.1137/1.9781611973068.26
发表时间：
2009
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
B. Nagle;A. Poerschke;V. Rödl;M. Schacht
通讯作者：
M. Schacht
影响因子：
1
作者：
B. Nagle;V. Rödl;M. Schacht
通讯作者：
M. Schacht
查找并计算 r-均匀超图中的派系和独立集
DOI：
10.1016/j.ipl.2006.04.005
发表时间：
2006
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
R. Yuster
通讯作者：
R. Yuster
计算给定图中子图频率的快速逼近算法
DOI：
10.1137/s0097539793247634
发表时间：
1995
期刊：
SIAM J. Comput.
影响因子：
--
作者：
R. Duke;H. Lefmann;V. Rödl
通讯作者：
V. Rödl