Two Ramsey problems in blowups of graphs

Abstract: Given graphs

G

and

H

, we say

G s t a c k r e l r o H

if every

r

-colouring of the edges of

G

contains a monochromatic copy of

H

. Let

H [t]

denote the

t

-blowup of

H

. The blowup Ramsey number

B (G s t a c k r e l r o H; t)

is the minimum

n

such that

G [n] s t a c k r e l r o H [t]

. Fox, Luo and Wigderson refined an upper bound of Souza, showing that, given

G

,

H

and

r

such that

G s t a c k r e l r o H

, there exist constants

a = a (G, H, r)

and

b = b (H, r)

such that for all

t i n m a t h b b N

,

B (G s t a c k r e l r o H; t) l e q a b^{t}

. They conjectured that there exist some graphs

H

for which the constant

a

depending on

G

is necessary. We prove this conjecture by showing that the statement is true in the case of

H

being

3

-chromatically connected, which in particular includes triangles. On the other hand, perhaps surprisingly, we show that for forests

F

, the function

B (G s t a c k r e l r o F; t)

is independent of

G

. Second, we show that for any

r, t i n m a t h b b N

, any sufficiently large

r

-edge coloured complete graph on

n

vertices with

O m e g a (n^{2 - 1 / t})

edges in each colour contains a member from a certain finite family

m a t h c a l F_{t}^{r}

of

r

-edge coloured complete graphs. This answers a conjecture of Bowen, Hansberg, Montejano and M"uyesser.

This page was built for publication: Two Ramsey problems in blowups of graphs