The VC-dimension of a family Ρ of n-permutations is the largest integer k such that the set of restrictions of the permutations in Ρ on some k-tuple of positions is the set of all k! permutation patterns. Let r_k(n) be the maximum size of a set of n-permutations with VC-dimension k. Raz showed that r_2(n) grows exponentially in n. We show that r_3(n) = 2~(θ(n log α(n))) and for every t ≥ 1, we have r_(2t+2)(n) = 2_(n_(n)t) and r_(2t+3(n)) = 2~(O(nα(n)~t log α(n)).
展开▼
