Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "The Tur´n problem for hypergraphs of fixed size "

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: The Tur´n problem for hypergraphs of fixed size a. | The Turan problem for hypergraphs of hxed size Peter Keevash Department of Mathematics Caltech Pasadena CA 91125 USA. keevash@caltech.edu Submitted Oct 22 2004 Accepted Jun 3 2005 Published Jun 14 2005 Mathematics Subject Classifications 05D05 Abstract We obtain a general bound on the Turan density of a hypergraph in terms of the number of edges that it contains. If F is an r-uniform hypergraph with f edges we show that F f 2 1 ơ 1 2r 2 r f 3 2 r -1 for fixed r 3 and f 1. Given an r-uniform hypergraph F the Turan number of F is the maximum number of edges in an r-uniform hypergraph on n vertices that does not contain a copy of F. We denote this number by ex n F . It is not hard to show that the limit F limn x ex n F p exists. It is usually called the Turan density of F. There are very few hypergraphs with r 2 for which the Turán density is known and even fewer for the exact Turán number. We refer the reader to 10 11 12 13 14 15 16 for recent results on these problems. A general upper bound on Turán densities was obtained by de Caen 3 who showed w KÍp 1 s-1 where kP denotes the complete r-uniform hypergraph on s vertices. A construction showing Kd 1 r 1Ỵ 1 was given by Sidorenko 17 see also 18 better bounds are known for large r. We refer the reader to Sidorenko 18 for a full discussion of this problem. For a general hypergraph F Sidorenko 19 see also 20 obtained a bound for the Turáan density in terms of the number of edges showing that if F has f edges then w F f . In this note we improve this as follows. Theorem 1 Suppose F is an r-uniform hypergraph with f edges. i If r 3 and f 4 then k F 1 pf2 2f 3 f 3 . ii For a fixed r 3 and f 1 we have pF Jp 1 o 1 2r 2 rf 3 2 r -1. We start by describing our main tool which is Sidorenko s analytic approach. See 20 for a survey of this method. Consider an r-uniform hypergraph H on n vertices. It is convenient to regard the vertex set V as a finite measure space in which each vertex v has v 1 n so that p V 1. We write h Vr 0 1