Tight bounds on the maximum size of a set of permutations with bounded VC-dimension

The VC-dimension of a family P of n-permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple of positions is the set of all k! permutation patterns. Let rk(n) be the maximum size of a set of n-permutations with VC-dimension k. Raz showed that r2(n) grows exponentially in n. We show that r3(n)=2Θ(nlogα(n)) and for every t⩾1, we have r2t+2(n)=2Θ(nα(n)t) and r2t+3(n)=2O(nα(n)tlogα(n)).We also study the maximum number pk(n) of 1-entries in an n×n(0,1)-matrix with no (k+1)-tuple of columns containing all (k+1)-permutation matrices. We determine that, for example, p3(n)=Θ(nα(n)) and p2t+2(n)=n2(1/t!)α(n)t±O(α(n)t−1) for every t⩾1.We also show that for every positive s there is a slowly growing function ζs(n) (for example ζ2t+3(n)=2O(αt(n)) for every t⩾1) satisfying the following. For all positive integers n and B and every n×n(0,1)-matrix M with ζs(n)Bn 1-entries, the rows of M can be partitioned into s intervals so that at least B columns contain at least B 1-entries in each of the intervals.