Higher Vapnik–Chervonenkis theory

Finite VC-dimension, a combinatorial property of families of sets, was discovered simultaneously by Vapnik and Chervonenkis in probabilistic learning theory, and by Shelah in model theory (where it is called NIP). It plays an important role in several areas including machine learning, combinatorics, mathematical logic, functional analysis and topological dynamics. We develop aspects of higher-order VC-theory, in particular establishing a generalization of the epsilon-net theorem for families of sets (and functions) on n-fold product spaces with bounded VC_n-dimension (i.e. there is a bound on the sizes of n-dimensional boxes that can be shattered). We obtain some applications in combinatorics and in model theory, including a strong version of Szemerdi’s regularity lemma for hypergraphs omitting a fixed finite n-partite n-hypergraph. Joint work with Henry Towsner.