Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Extremal problems for t-partite and t-colorable hypergraphs. | Extremal problems for t-partite and t-colorable hypergraphs Dhruv Mubayi John Talboty Submitted Aug 23 2007 Accepted Jan 20 2008 Published Feb 4 2008 Mathematics Subject Classification 05D05 Abstract Fix integers t r 2 and an r-uniform hypergraph F. We prove that the maximum number of edges in a t-partite r-uniform hypergraph on n vertices that contains no copy of F is ct Fp o nr where ct F can be determined by a finite computation. We explicitly define a sequence F1 F2 . of r-uniform hypergraphs and prove that the maximum number of edges in a t-chromatic r-uniform hypergraph on n vertices containing no copy of Fi is at r i r o nr where at r i can be determined by a hnite computation for each i 1. In several cases at r i is irrational. The main tool used in the proofs is the Lagrangian of a hypergraph. 1 Introduction An r-uniform hypergraph or r-graph is a pair G V E of vertices V and edges E c Ỵ in particular a 2-graph is a graph. We denote an edge v15 v2 vrg by v1v2 vr. Given r-graphs F and G we say that G is F-free if G does not contain a copy of F. The maximum number of edges in an F-free r-graph of order n is ex n F . For r 2 and F Ks s 3 this number was determined by Turán T41 earlier Mantel M07 found ex n K3 . However in general even for r 2 the problem of determining the exact value of ex n F is beyond current methods. The corresponding asymptotic problem is to determine the Turan density of F defined by f F limn 1 eX F this always exists by a simple averaging argument due to Katona et al. KNS64 . For 2-graphs the Turán Department of Mathematics Statistics and Computer Science University of Illinois Chicago IL 60607 and Department of Mathematical Sciences Carnegie-Mellon University Pittsburgh PA 15213. Email mubayi@. Research supported in part by NSF grants DMS-0400812 and 0653946 and an Alfred P. Sloan Research Fellowship. yDepartment of Mathematics UCL London WC1E 6BT UK. Email talbot@. This author is a Royal Society University .
