2022/08/23 by Wigderson, Yuval
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2208.11181
Given a graph G, its Ramsey number r(G) is the minimum N so that every two-coloring of E(KN) 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 \Gn\ so that in any Ramsey coloring for Gn (that is, a coloring of a clique on r(Gn)-1 vertices with no monochromatic copy of Gn), one of the color classes has density o(1).