论文标题
超图规律性和较高的Arity VC维度
Hypergraph regularity and higher arity VC-dimension
论文作者
论文摘要
我们概括了一个事实，即可以通过矩形近似具有小的VC维度的图，表明具有小VC_K-dimension（等效地，省略固定有限（k+1）-partite（k+1） - 套分（k+1） - 均匀的超毛图）的高图可以由k-ary cylinder集近似。 用超图的规律性语言，这表明，当h是某些k <k'的k'-均匀超图具有小的vc_k-尺寸时，h hypergraph juroparity只需要第一个k级的h分解时，一个人就可以使用h可以使用一组thertices，对k-tairs和k-tuples的cy来近似h - 接近0或接近1。 我们还表现出合适的相反：具有较大VC_K-dimension的K'-均匀的超图不能在顶点的所有措施下均匀地具有统一的近似值。
We generalize the fact that graphs with small VC-dimension can be approximated by rectangles, showing that hypergraphs with small VC_k-dimension (equivalently, omitting a fixed finite (k+1)-partite (k+1)-uniform hypergraph) can be approximated by k-ary cylinder sets. In the language of hypergraph regularity, this shows that when H is a k'-uniform hypergraph with small VC_k-dimension for some k<k', the decomposition of H given by hypergraph regularity only needs the first k levels---one can approximate H using sets of vertices, sets of pairs, and so on up to sets of k-tuples---and that on most of the resulting k-ary cylinder sets, the density of H is either close to 0 or close to 1. We also show a suitable converse: k'-uniform hypergraphs with large VC_k-dimension cannot have such approximations uniformly under all measures on the vertices.
