Improved bounds on the multicolor Ramsey numbers of paths and even cycles

Abstract: We study the multicolor Ramsey numbers for paths and even cycles,

R_{k} (P_{n})

and

R_{k} (C_{n})

, which are the smallest integers

N

such that every coloring of the complete graph

K_{N}

has a monochromatic copy of

P_{n}

or

C_{n}

respectively. For a long time,

R_{k} (P_{n})

has only been known to lie between

(k - 1 + o (1)) n

and

(k + o (1)) n

. A recent breakthrough by S'ark"ozy and later improvement by Davies, Jenssen and Roberts give an upper bound of

(k - f r a c 14 + o (1)) n

. We improve the upper bound to

(k - f r a c 12 + o (1)) n

. Our approach uses structural insights in connected graphs without a large matching. These insights may be of independent interest.

Full work available at URL: https://arxiv.org/abs/1801.04128

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (17)

This page was built for publication: Improved bounds on the multicolor Ramsey numbers of paths and even cycles