Efficient Testing of Hypergraphs
Efficient Testing of Hypergraphs
复制标题
超图的高效测试
DOI：
10.1007/3-540-45465-9_87
复制
发表时间：
2002
影响因子：
1
通讯作者：
V. Rödl
中科院分区：
文献类型：
--
作者：
Y. Kohayakawa;B. Nagle;V. Rödl
本文在Goldreich，Goldwasser，和罗恩[9，10]的意义下，在3-一致超图（简称3-图）的背景下研究了组合性质测试中的一个基本问题.通常，3-图F只是3-元素集合的集合。设Forbind（n，F）是所有n阶3-图的族，它们不包含F的拷贝作为导出子超图。我们表明，财产“H？对任意3-图F，“Forbind（n，F）”是可测的.事实上，这是一个新的，基本的组合引理，它扩展到3-图的结果图由于阿隆，菲舍尔，Krivelevich，和Szegedy [2，3]。n3（？> 0）若在3-图H的n个顶点上添加或删除三元组，则H必须包含？CN| V（F）|F的诱导拷贝，只要n？n0（？，F）。我们的方法受到[2，3]的启发，但主要成分是最近的超图正则性引理和3-图的计数引理。
We investigate a basic problem in combinatorial property testing, in the sense of Goldreich, Goldwasser, and Ron [9,10], in the context of 3-uniform hypergraphs, or 3-graphs for short. As customary, a 3-graph F is simply a collection of 3-element sets. Let Forbind(n, F) be the family of all 3-graphs on n vertices that contain no copy of F as an induced subhypergraph. We show that the property "H ? Forbind(n, F)" is testable, for any 3-graph F. In fact, this is a consequence of a new, basic combinatorial lemma, which extends to 3-graphs a result for graphs due to Alon, Fischer, Krivelevich, and Szegedy [2,3].Indeed, we prove that if more than ?n3 (? > 0) triples must be added or deleted from a 3-graph H on n vertices to destroy all induced copies of F, then H must contain ? cn |V(F)| induced copies of F, as long as n ? n0(?,F). Our approach is inspired in [2,3], but the main ingredients are recent hypergraph regularity lemmas and counting lemmas for 3-graphs.