A small step forwards on the Erdős-Sós problem concerning the Ramsey numbers R(3, k)

Publication date 30 September 2016

Abstract: Let

D e l t a_{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, ErdH{o}s and S'{o}s posed some questions about the growth of

D e l t a_{s}

. The best known concrete bounds on

D e l t a_{s}

are

3 l e D e l t a_{s} l e s

, and they have not improved since the stating of the problem. In this paper we present some constructions, which imply in particular that

R (K_{3}, K_{s}) g e R (K_{3}, K_{s - 1} - e) + 4

. This does not improve the lower bound of 3 on

D e l t a_{s}

, but we still consider it a step towards to understanding its growth. We discuss some related questions and state two conjectures involving

D e l t a_{s}

, including the following: for some constant

d

and all

s

it holds that

D e l t a_{s} - D e l t a_{s + 1} l e q d

. We also prove that if the latter is true, then

l i m_{s i g h t a r r o w i n f t y} D e l t a_{s} / s = 0

.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: A small step forwards on the Erdős-Sós problem concerning the Ramsey numbers \(R(3, k)\)