TAILIEUCHUNG - Báo cáo toán học: "Dense H-free graphs are almost (χ(H) − 1)-partite"

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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Dense H-free graphs are almost (χ(H) − 1)-partite. | Dense H-free graphs are almost x H 1 -partite Peter Allen Submitted Jul 24 2009 Accepted Jan 19 2010 Published Jan 29 2010 Mathematics Subject Classification 05C35 Abstract By using the Szemeredi Regularity Lemma 10 Alon and Sudakov 1 recently extended the classical Andrasfai-Erdos-SOs theorem 2 to cover general graphs. We prove without using the Regularity Lemma that the following stronger statement is true. Given any r 1 -partite graph H whose smallest part has t vertices there exists a constant C such that for any given e 0 and sufficiently large n the following is true. Whenever G is an n-vertex graph with minimum degree J G 1 3 e n 3r 1 either G contains H or we can delete f n H Cn2-1 edges from G to obtain an r-partite graph. Further we are able to determine the correct order of magnitude of f n H in terms of the Zarankiewicz extremal function. 1 Introduction We define the graph Kr s to be the complete r-partite graph whose parts each have s vertices. Given a graph H whose chromatic number is x H we examine all the proper x H -colourings of H. We choose one whose smallest colour class is of smallest possible size then ơ H is the size of this smallest colour class. Otherwise our notation is standard. We recall the classical theorem of Zarankiewicz 12 Theorem 1. If the n-vertex graph G has minimum degree exceeding 1 1 n then G contains Kr 1. DIMAP and Mathematics Institute University of Warwick Coventry CV4 7AL . Email . allen@warwick . . Research supported by the Centre for Discrete Mathematics and its Applications EPSRC award EP D063191 1. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R21 1 This theorem is an immediate corollary of Turan s theorem 11 . As is well known it is best possible the extremal example being a complete balanced r-partite graph sometimes called a Turan graph . An old result of Andrasfai Erdos and Sos 2 which amounts to a very strong stability result for Zarankiewicz theorem is the following. Theorem 2. Suppose r 2. If the .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học