Extremal Hypergraph Problems and the Regularity Method
Extremal Hypergraph Problems and the Regularity Method
复制标题
极值超图问题和正则方法
DOI：
10.1007/3-540-33700-8_16
复制
发表时间：
2006
影响因子：
1
通讯作者：
M. Schacht
中科院分区：
文献类型：
--
作者：
B. Nagle;V. Rödl;M. Schacht
Szemeredi的正则性引理断言每个图都可以分解成相对较少的类随机子图。这种类似于随机的行为使人们能够找到并枚举给定同构类型的子图，产生所谓的图的计数引理。这两个引理的组合应用被称为图的正则性方法，并已证明在图论，组合几何，组合数论和理论计算机科学中很有用。
Szemeredi’s regularity lemma asserts that every graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type, yielding the so-called counting lemma for graphs. The combined application of these two lemmas is known as the regularity method for graphs and has proved useful in graph theory, combinatorial geometry, combinatorial number theory and theoretical computer science.