An exponential-type upper bound for Folkman numbers
An exponential-type upper bound for Folkman numbers
复制标题
DOI：
10.1007/s00493-015-3298-1
复制
发表时间：
2016-03
期刊：
影响因子：
1.1
通讯作者：
V. Rödl;A. Rucinski;M. Schacht
中科院分区：
文献类型：
--
作者：
V. Rödl;A. Rucinski;M. Schacht
对于给定的整数（k;r）， Folkman数f（k;r）是图（k +1个顶点）中不包含团的最小顶点数，但对于图（k +1个顶点）的每一个边划分，都有一部分包含一个有序的团。Folkman数的存在性（有限性）是由Folkman（1970）对r=2和Nešetřil和Rödl（1976）对任意r建立的，但这些证明导致f（k;r）的上界很弱。最近，Conlon和Gowers以及独立作者获得了f（k;2）的双指数界。在这里，我们通过展示f（k;r）的上界来建立一个进一步的改进，它是kandr的多项式的指数。这与已知的下界2Ω（rk）相当。我们的证明依赖于Saxton和Thomason最近的一个结果（或者，也可以依赖于Balogh、Morris和Samotij最近的一个结果），从这个结果我们推导出随机图中Ramsey定理的一个定量版本。
For given integerskandr, the Folkman numberf(k;r) is the smallest number of vertices in a graphGwhich contains no clique onk+1 vertices, yet for every partition of its edges intorparts, some part contains a clique of orderk. The existence (finiteness) of Folkman numbers was established by Folkman (1970) forr=2 and by Nešetřil and Rödl (1976) for arbitraryr, but these proofs led to very weak upper bounds onf(k;r).Recently, Conlon and Gowers and independently the authors obtained a doubly exponential bound onf(k;2). Here, we establish a further improvement by showing an upper bound onf(k;r) which is exponential in a polynomial ofkandr. This is comparable to the known lower bound 2Ω(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.