Hypergraph regularity and higher arity VC-dimension

Artem Chernikov, Henry Towsner

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 fin…