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 .

Không thể tạo bản xem trước, hãy bấm tải xuống
106    119    3    13-07-2024
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.