On Some Multicolor Ramsey Numbers Involving K₃+e and K₄-e

Abstract: The Ramsey number

R (G_{1}, G_{2}, G_{3})

is the smallest positive integer

n

such that for all 3-colorings of the edges of

K_{n}

there is a monochromatic

G_{1}

in the first color,

G_{2}

in the second color, or

G_{3}

in the third color. We study the bounds on various 3-color Ramsey numbers

R (G_{1}, G_{2}, G_{3})

, where

G_{i} i n K_{3}, K_{3} + e, K_{4} - e, K_{4}

. The minimal and maximal combinations of

G_{i}

's correspond to the classical Ramsey numbers

R_{3} (K_{3})

and

R_{3} (K_{4})

, respectively, where

R_{3} (G) = R (G, G, G)

. Here, we focus on the much less studied combinations between these two cases. Through computational and theoretical means we establish that

R (K_{3}, K_{3}, K_{4} - e) = 17

, and by construction we raise the lower bounds on

R (K_{3}, K_{4} - e, K_{4} - e)

and

R (K_{4}, K_{4} - e, K_{4} - e)

. For some

G

and

H

it was known that

R (K_{3}, G, H) = R (K_{3} + e, G, H)

; we prove this is true for several more cases including

R (K_{3}, K_{3}, K_{4} - e) = R (K_{3} + e, K_{3} + e, K_{4} - e)

. Ramsey numbers generalize to more colors, such as in the famous 4-color case of

R_{4} (K_{3})

, where monochromatic triangles are avoided. It is known that

51 l e q R_{4} (K_{3}) l e q 62

. We prove a surprising theorem stating that if

R_{4} (K_{3}) = 51

then

R_{4} (K_{3} + e) = 52

, otherwise

R_{4} (K_{3} + e) = R_{4} (K_{3})

.

Recommendations

Cited In (4)

Uses Software

This page was built for publication: On Some Multicolor Ramsey Numbers Involving $K_3+e$ and $K_4-e$