We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Ramsey numbers upon vertex deletion.
- Authors
Wigderson, Yuval
- Abstract
Given a graph G $G$, its Ramsey number r(G) $r(G)$ is the minimum N $N$ so that every two‐coloring of E(KN) $E({K}_{N})$ contains a monochromatic copy of G $G$. It was conjectured by Conlon, Fox, and Sudakov that if one deletes a single vertex from G $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} $\{{G}_{n}\}$ so that in any Ramsey coloring for Gn ${G}_{n}$ (i.e., a coloring of a clique on r(Gn)−1 $r({G}_{n})-1$ vertices with no monochromatic copy of Gn ${G}_{n}$), one of the color classes has density o(1) $o(1)$.
- Subjects
RAMSEY numbers; LOGICAL prediction
- Publication
Journal of Graph Theory, 2024, Vol 106, Issue 3, p663
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.23093