Hypergraph regularity and higher arity VC-dimension
From MaRDI portal
Publication:6350356
arXiv2010.00726MaRDI QIDQ6350356FDOQ6350356
Authors: Artem Chernikov, Henry Piers Towsner 
Publication date: 1 October 2020
Abstract: 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.
Extremal problems in graph theory (05C35) Classification theory, stability, and related concepts in model theory (03C45) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Structural characterization of families of graphs (05C75)
This page was built for publication: Hypergraph regularity and higher arity VC-dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6350356)
