Submission 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 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.

Mathematics Subject Classification: 05C65, 05C35, 05C75, 05C55, 03C45

Keywords and phrases:

Full text arXiv 2010.00726: pdf, ps.