Hypergraph regularity and higher arity VC-dimension

We generalize the fact that all graphs omitting a fixed finite bipartite graph can be uniformly approximated by rectangles (Alon-Fischer-Newman, Lovász-Szegedy), showing that hypergraphs omitting a fixed finite $(k+1)$-partite $(k+1)$-uniform hypergraph can be approximated by $k$-ary cylinder sets. In particular, in the decomposition given by hypergraph regularity one only needs the first $k$ levels: such hypergraphs can be approximated using sets of vertices, sets of pairs, and so on up to sets of $k$-tuples, and on most of the resulting $k$-ary cylinder sets, the density is either close to 0 or close to 1. Moreover, existence of such approximations uniformly under all measures on the vertices is a characterization. Our proof uses a combination of analytic, combinatorial and model-theoretic methods, and involves a certain higher arity generalization of the epsilon-net theorem from VC-theory.  Joint work with Henry Towsner.