On the size-Ramsey number of tight paths

Abstract: For any

r g e q 2

and

k g e q 3

, the

r

-color size-Ramsey number

h a t R (m a t h c a l G, r)

of a

k

-uniform hypergraph

m a t h c a l G

is the smallest integer

m

such that there exists a

k

-uniform hypergraph

m a t h c a l H

on

m

edges such that any coloring of the edges of

m a t h c a l H

with

r

colors yields a monochromatic copy of

m a t h c a l G

. Let

m a t h c a l P_{n, k - 1}^{(k)}

denote the

k

-uniform tight path on

n

vertices. Dudek, Fleur, Mubayi and RH{o}dl showed that the size-Ramsey number of tight paths

h a t R (m a t h c a l P_{n, k - 1}^{(k)}, 2) = O (n^{k - 1 - a l p h a} (l o g n)^{1 + a l p h a})

where

. In this paper, we improve their bound by showing that

h a t R (m a t h c a l P_{n, k - 1}^{(k)}, r) = O (r^{k} (n l o g n)^{k / 2})

for all

k g e q 3

and

r g e q 2

.

Recommendations

Cites Work

Cited In (10)

This page was built for publication: On the size-Ramsey number of tight paths