科研之友
微信
新浪微博
Facebook
分享链接
摘要
For given integers k and r, the Folkman number f (k; r) is the smallest number of vertices in a graph G which contains no clique on k + 1 vertices, yet for every partition of its edges into r parts, some part contains a clique of order k. The existence (finiteness) of Folkman numbers was established by Folkman (1970) for r = 2 and by Nesetril and Rodl (1976) for arbitrary r, but these proofs led to very weak upper bounds on f (k; r). Recently, Conlon and Gowers and independently the authors obtained a doubly exponential bound on f (k; 2). Here, we establish a further improvement by showing an upper bound on f (k; r) which is exponential in a polynomial of k and r. This is comparable to the known lower bound 2(Omega(rk)). Our proof relies on a recent result of Saxton and Thomason (or, alternatively, on a recent result of Balogh, Morris, and Samotij) from which we deduce a quantitative version of Ramsey's theorem in random graphs.
- 出版日期2017-8
