Packing Nearly Optimal Ramsey R(3,t) Graphs
Packing Nearly Optimal Ramsey R(3,t) Graphs
复制标题
包装接近最优的 Ramsey R(3,t) 图
DOI：
10.1007/s00493-019-3921-7
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
Warnke, Lutz
中科院分区：
文献类型：
--
作者：
Guo, He;Warnke, Lutz
1995年，Kim通过构造n-顶点图证明了Ramsey界R（3，t）≤ ct 2/logt。我们把这个著名的结果推广到常数的值，把完全图K n近似分解成这样的近最优RamseyR（3，t）图的一个packing.更精确地说，对任意ε> 0，我们找到一个n-顶点图的边不交集合（Gi）i ∈ K n，使得（a）每个Gi是无三角形的，且至多有独立数，以及（B）所有G的并集至少包含$$（1-\n）\left（\开始{array}{l} n\\2\end {array}\right）$$边。我们的算法证明通过顺序地选择图Givia半随机（即，作为应用，我们证明了Fox，Grinshpun，Liebenau，Person和Szabó在Ramsey理论中的一个猜想（关于Burr，Erdés和Lovász在1976年引入的Ramsey型参数）。也就是说，我们用bysr（H）表示H的r-Ramsey极小图的最小度，从而封闭了H = K3的对数间隙，并建立了sr（K3）=Θ（r2 logr）。
In 1995 Kim famously proved the Ramsey boundR(3,t) ≤ct2/logtby constructing ann-vertex graph that is triangle-free and has independence number at most. We extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graphKninto a packing of such nearly optimal RamseyR(3,t) graphs.More precisely, for anyε> 0 we find an edge-disjoint collection (Gi)iofn-vertex graphsGi⊆Knsuch that (a) eachGiis triangle-free and has independence number at most, and (b) the union of all theGicontains at least $$(1-\epsilon)\left(\begin{array}{l}n \\2\end{array}\right)$$ edges. Our algorithmic proof proceeds by sequentially choosing the graphsGivia a semi-random (i.e., Rödl nibble type) variation of the triangle-free process.As an application, we prove a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szabó (concerning a Ramsey-type parameter introduced by Burr, Erdős, and Lovász in 1976). Namely, denoting bysr(H) the smallest minimum degree ofr-Ramsey minimal graphs forH, we close the existing logarithmic gap forH=K3and establish thatsr(K3) =Θ(r2logr).
登录
查看更多内容
无 K4 进程何时停止？
影响因子：
1
作者：
L. Warnke
通讯作者：
L. Warnke
A·哈贝：（1989）
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--
定向游戏和最小拉姆齐图
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
Anita Liebenau
通讯作者：
Anita Liebenau
无金刚石工艺
DOI：
--
发表时间：
2010
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
Michael E. Picollelli
通讯作者：
Michael E. Picollelli
密集无限西顿序列
DOI：
--
发表时间：
1981
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
M. Ajtai;J. Komlos;E. Szemerédi
通讯作者：
E. Szemerédi