TAILIEUCHUNG - Báo cáo toán học: "Proof of the (n/2 − n/2 − n/2) Conjecture for large n"

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: Proof of the (n/2 − n/2 − n/2) Conjecture for large n. | Proof of the n 2 n 2 n 2 Conjecture for large n Yi Zhao Department of Mathematics and Statistics Georgia State University Atlanta GA 30303 yzhao6@ Submitted Jun 6 2008 Accepted Jan 22 2011 Published Feb 4 2011 Mathematics Subject Classifications 05C35 05C55 05C05 05D10 Abstract A conjecture of Loebl also known as the n 2 n 2 n 2 Conjecture states that if G is an n-vertex graph in which at least n 2 of the vertices have degree at least n 2 then G contains all trees with at most n 2 edges as subgraphs. Applying the Regularity Lemma Ajtai Komlos and Szemeredi proved an approximate version of this conjecture. We prove it exactly for sufficiently large n. This immediately gives a tight upper bound for the Ramsey number of trees and partially confirms a conjecture of Burr and Erdos. 1 Introduction For a graph G let V G or simply V and E G denote its vertex set and edge set respectively. The order of G is v G V G or G and the size of G is e G E G or G . For v G V and a set X c V N v X 1 represents the set of the neighbors of v in X and deg v X N v X is the degree of v in X. In particular N v N v V and deg v deg v V . Let G be a graph and T be a tree with v T v G . Under what condition must G contain T as a subgraph Applying the greedy algorithm one can easily derive the following fact. Fact . Every graph G with J G mindeg v k contains all trees T on k edges as subgraphs. A preliminary version of this paper appears in the . dissertation 2001 of the author under the supervision of Endre Szemeredi. Research supported in part by NSF grant DMS-9983703 NSA grants H98230-05-1-0140 H98230-07-1-0019 and H98230-10-1-0165 a DlMACS graduate student Fellowship at Rutgers University and a VIGRE Postdoctoral Fellowship at University of Illinois at Chicago. 1We prefer N v X to the widely used notation NX v because we want to save the subscript for the underlying graph. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P27 1 Extending Fact Erdos and Sos 7 conjectured that

• 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