Article ID Journal Published Year Pages File Type
9515473 Journal of Combinatorial Theory, Series A 2005 5 Pages PDF
Abstract
Given positive integers n,k,t, with 2⩽k⩽n, and t<2k, 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 Turán numbers T⩾r(n,k,t) and Tr(n,k,t), where T⩾r(n,k,t) (Tr(n,k,t)) denotes the minimum size of a family F⊂[n]⩾rF⊂[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))Tr(n,k,t) for fixed r,k,t with t⩽kr and n→∞.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,