The size‐Ramsey number of powers of paths

Abstract: Given graphs

G

and

H

and a positive integer

q

say that

G

is

q

-Ramsey for

H

, denoted

G i g h t a r r o w (H)_{q}

, if every

q

-colouring of the edges of

G

contains a monochromatic copy of

H

. The size-Ramsey number

h a t r (H)

of a graph

H

is defined to be

h a t r (H) = m i n | E (G) | c o l o n G i g h t a r r o w (H)_{2}

. Answering a question of Conlon, we prove that, for every fixed

k

, we have

h a t r (P_{n}^{k}) = O (n)

, where

P_{n}^{k}

is the

k

-th power of the

n

-vertex path

P_{n}

(i.e. , the graph with vertex set

V (P_{n})

and all edges

u, v

such that the distance between

u

and

v

in

P_{n}

is at most

k

). Our proof is probabilistic, but can also be made constructive.

Recommendations

Cited in

(20)

This page was built for publication: The size‐Ramsey number of powers of paths