Tham khảo luận văn - đề án 'báo cáo khoa học: on a two-sided tur´an problem', luận văn - báo cáo, báo cáo khoa học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | On a two-sided Turan problem Dhruv Mubayi Yi Zha d Department of Mathematics Statistics and Computer Science University of Illinois at Chicago 851 S. Morgan Street Chicago IL 60607 mubayi@ zhao@ Submitted Aug 21 2003 Accepted Nov 3 2003 Published Nov 10 2003 MR Subject Classifications 05D05 05C35 Abstract Given positive integers n k t with 2 k n and t 2k let m n fc t be the minimum size of a family F of nonempty subsets of n such that every k-set in n contains at least t sets from F and every k 1 -set in n contains at most t 1 sets from F. Sloan et al. determined m n 3 2 and Furedi et al. studied m n 4 t for t 2 3. We consider m n 3 t and m n 4 t for all the remaining values of t and obtain their exact values except for k 4 and t 6 7 11 12. For example we prove that m n 4 5 n 17 for n 160. The values of m n 4 t for t 7 11 12 are determined in terms of well-known and open Turan problems for graphs and hypergraphs. We also obtain bounds of m n 4 6 that differ by absolute constants. 1 Introduction We consider an extremal problem for set systems. Given integers n k t with 2 k n and t 2k a family F c 2n 0 is a k t -system of n if every k-set in n contains at least t sets from F and every k 1 -set in n contains at most t 1 sets from F. Let m n k t denote the minimum size of a k t -system of n . This threshold function first arose in problems on computer science 10 11 although the notation m n k t was not used until 6 . It was shown in 11 that m n k t 0 nk-1 for 1 t k and m n 3 2 ra-1 1. In 6 m n 4 3 was determined exactly for large n and it was shown that for fixed k m n k 2 1 o 1 Tk-1 n k 2 where Tr n k t is the generalized Turan number. For fixed k and t 2k the order of magnitude of m n k t Research supported in part by NSF grant DMS-9970325. Research supported in part by NSF grant DMS-9983703 a VIGRE Postdoctoral Fellowship at University of Illinois at Chicago. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R42 1 was determined in 9 . A .
