A small step forwards on the Erdos-Sos problem concerning the Ramsey numbers R(3, k)
A small step forwards on the Erdos-Sos problem concerning the Ramsey numbers R(3, k)
复制标题
关于 Ramsey 数 R(3, k) 的 Erdos-Sos 问题向前迈出了一小步
DOI：
10.1016/j.dam.2016.06.003
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
Radziszowski Stanislaw
中科院分区：
文献类型：
--
作者：
Zhu Rujie;Xu Xiaodong;Radziszowski Stanislaw
设Δ s= R（K3，KS）-R（K3，KS-1），其中R（G，H）是图G和H的Ramsey数，定义为最小n使得Kn的任意两种颜色的边染色包含第一种颜色的G或第二种颜色的H. 1980年，Erdés和Sós对Δ s的增长提出了一些问题。已知的Δ s的具体界是3≤ Δ s≤ s，自问题提出以来，它们没有得到改进。本文给出了一些构造，它们特别地意味着R（K3，KS）≥ R（K3，KS − 1− e）+ 4，并且对于s，t≥ 3，R（3，KS + t− 1）≥ R（3，KS + 1− e）+ R（3，KT + 1− e）− 5。这并没有改善Δ s的下界3，但我们仍然认为这是朝着理解它的增长迈出的一步。本文讨论了一些相关的问题，并给出了两个涉及Δ s的定理，包括：对某个常数d和所有s，Δ s− Δ s+ 1≤ d成立。我们还证明了，如果后者为真，则lim s→∞ Δ s/s= 0。
Abstract Let Δ s= R (K 3, K s)− R (K 3, K s− 1), where R (G, H) is the Ramsey number of graphs G and H defined as the smallest n such that any edge coloring of K n with two colors contains G in the first color or H in the second color. In 1980, Erdős and Sós posed some questions about the growth of Δ s. The best known concrete bounds on Δ s are 3≤ Δ s≤ s, and they have not been improved since the stating of the problem. In this paper we present some constructions, which imply in particular that R (K 3, K s)≥ R (K 3, K s− 1− e)+ 4, and R (3, K s+ t− 1)≥ R (3, K s+ 1− e)+ R (3, K t+ 1− e)− 5 for s, t≥ 3. This does not improve the lower bound of 3 on Δ s, but we still consider it a step towards to understanding its growth. We discuss some related questions and state two conjectures involving Δ s, including the following: for some constant d and all s it holds that Δ s− Δ s+ 1≤ d. We also prove that if the latter is true, then lim s→∞ Δ s/s= 0.