Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9515473 | Journal of Combinatorial Theory, Series A | 2005 | 5 Pages |
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ââ.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Dhruv Mubayi, Yi Zhao,