A localized packing lemma for sets of bounded VC 2-dimension
math.CO, math.LO
Submitted: 2026-10-31
Updated: 2026-10-31
Comments: 24 pages
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: In the setting of abelian groups, Haussler's packing lemma implies that any subset of bounded VC-dimension can be approximated by one of a small number of representative translates.
Terminology
Abstract
In the setting of abelian groups, Haussler's packing lemma implies that any subset of bounded VC-dimension can be approximated by one of a small number of representative translates. While this exact statement is provably false under the weaker hypothesis that A has bounded VC 2-dimension, we show that in F p n a similar statement does hold after localization to cosets of subspaces depending on the individual translates. More precisely, given ε>0 and A F p n with VC 2(A)<k, we show that there exist r at most ε-O k,p(1) and g 1,, g r in F p n with the property that for every x in F p n, there is a partition C x of F p n into cosets of (possibly distinct) subgroups, each of index at most (ε-O k,p(1)), and a subcollection Ω x C x whose union has size at least (1-ε) F p n, such that on each C in Ω x, the translate A-x looks like one of A-g 1,, A-g r, in the sense that ((A-x)Δ(A-g i x,C)) C<εC for some 1 at most i x,C at most r. We also prove a second version of this result in which each partition C x is the set of cosets of a single subgroup H x of quasipolynomial index but where the bound on r is a quadruple exponential.
Sources
- Hypergraph regularity and higher arity VC-dimension
- Sample completion, structured correlation, and Netflix problems
- On the linear complexity of subsets of $\mathbb{F}_p^n$ bounded $\textrm{VC}_2$-dimension
- Higher-order generalizations of stability and arithmetic regularity
- The structure of subsets of $\mathbb{F}_p^n$ of bounded $\mathrm{VC}_2$-dimension
- On the quadratic complexity of subsets of $\mathbb{F}_p^n$ of bounded $\mathrm{VC_{2}}$-dimension
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality