Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On hypergraphs with every four points spanning at most two triples | On hypergraphs with every four points spanning at most two triples Dhruv Mubayi Department of Mathematics Statistics and Computer Science University of Illinois Chicago IL 60607 Submitted Jan 10 2003 Accepted Aug 25 2003 Published Sep 8 2003 MR Subject Classifications 05C35 05C65 05D05 Keywords Hypergraph Turan numbers Abstract Let F be a triple system on an n element set. Suppose that F contains more than 1 3 e n triples where e 10-6 is explicitly defined and n is sufficiently large. Then there is a set of four points containing at least three triples of F. This improves previous bounds of de Caen 1 and Matthias 7 . Given an r-graph F the Turan number ex n F is the maximum number of edges in an n. 0 1 1 ov Kill i llil -I i KI i KI Cĩ KI í m if Í 1 I ll o I 1 1 vó TI I OKI c ill TT Í 1 - 1 i TK1 6x n F vertex Ỉ graph containing no member or F The ruran density n lirrin _ 0 Jn When n F 0 and r 2 determining n F is a notoriously hard problem even for very simple r-graphs F see 5 for a survey of results Determining the Turan density of complete r-graphs is a fundamental question about set-systems In fact this is not known in any nontrivial case when r 3 Perhaps the most well-known problem in this area is to determine n K where K is the complete 3-graph on four vertices the smallest nontrivial complete r-graph It is known that 5 9 n K 3 VT7 12 . where the lower bound is due to Turan and the recent upper bound is due to Chung and Lu 2 However even the Turan density of H 4 3 the 3-graph on four vertices with three edges is not known One could argue that this problem is even more basic since H 4 3 is the smallest in the sense of both vertices and edges 3-graph with positive Turan density for applications of n H 4 3 to computer science see 9 6 Research supported in part by the National Science Foundation under grant DMS-9970325 THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 N10 1 The upper bound n H 4 3 1 3 was proved by de Caen 1 and this was improved to 1 3
