tailieunhanh - Đề tài " The two possible values of the chromatic number of a random graph "

Given d ∈ (0,∞) let kd be the smallest integer k such that d | Annals of Mathematics The two possible values of the chromatic number of a random graph By Dimitris Achlioptas and Assaf Naor Annals of Mathematics 162 2005 1335 1351 The two possible values of the chromatic number of a random graph By Dimitris Achlioptas and Assaf Naor Abstract Given d E 0 to let kd be the smallest integer k such that d 2k log k. We prove that the chromatic number of a random graph G n d n is either kd or kd 1 almost surely. 1. Introduction The classical model of random graphs in which each possible edge on n vertices is chosen independently with probability p is denoted by G n p . This model introduced by Erdos and Renyi in 1960 has been studied intensively in the past four decades. We refer to the books 3 5 11 and the references therein for accounts of many remarkable results on random graphs as well as for their connections to various areas of mathematics. In the present paper we consider random graphs of bounded average degree . p d n for some fixed d E 0 to . One of the most important invariants of a graph G is its chromatic number X G namely the minimum number of colors required to color its vertices so that no pair of adjacent vertices has the same color. Since the mid-1970s work on X G n p has been in the forefront of random graph theory motivating some of the field s most significant developments. Indeed one of the most fascinating facts known 13 about random graphs is that for every d E 0 to there exists an integer kd such that almost surely x G n d n is either kd or kd 1. The value of kd itself nevertheless remained a mystery. To date the best known 12 estimate for x G n d n confines it to an interval i ll OnơTti it I will I . 29 log logd Tn nil main mQiilt rpdnrp TtiiQ ImioT II mtiva of ivn m aưoưc Ci 2 logd 2 . Ln out man Ltồ H we Lins lengcn to 2. Specifically we prove Theorem 1. Given d E 0 to let kd be the smallest integer k such that d 2k log k. With probability that tends to 1 as n to X G n d n E kd kd 1 . Work .