Non-uniform Turan-type problems

摘要

Given positive integers n, k, t, with 2 <= k <= n, and t < 2(k), let m (n, k, t) be the minimum size of a family f of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F and every (k - 1)-subset of [n] contains at most t - 1 members of F. For fixed k and t, we determine the order of magnitude of m(n, k, t). We also consider related Turdn numbers T->= r (n, k, t) and T, (n, k, t), where T->= r (n, k, t) (T-r (n, k, t)) denotes the minimum size of a family F subset of (([n])(>= r)) (F subset of (([n])(r)) such that every k-subset of [n] contains at least t members of F. We prove that T->= r (n, k, t) = (1 + o(1)) T-r(n, k, t) for fixed r, k, t with t <=, and n -> infinity. (c) 2004 Elsevier Inc. All rights reserved.