Ramsey numbers upon vertex deletion

arXiv2208.11181MaRDI QIDQ6507980FDOQ6507980

Abstract: Given a graph

G

, its Ramsey number

r (G)

is the minimum

N

so that every two-coloring of

E (K_{N})

contains a monochromatic copy of

G

. It was conjectured by Conlon, Fox, and Sudakov that if one deletes a single vertex from

G

, the Ramsey number can change by at most a constant factor. We disprove this conjecture, exhibiting an infinite family of graphs such that deleting a single vertex from each decreases the Ramsey number by a super-constant factor. One consequence of this result is the following. There exists a family of graphs

G_{n}

so that in any Ramsey coloring for

G_{n}

(that is, a coloring of a clique on

r (G_{n}) - 1

vertices with no monochromatic copy of

G_{n}

), one of the color classes has density

o (1)

.

This page was built for publication: Ramsey numbers upon vertex deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507980)