论文标题
顶点删除时的拉姆齐号
Ramsey numbers upon vertex deletion
论文作者
论文摘要
给定图形$ g $，其Ramsey Number $ r（g）$是最低$ n $，因此每两种颜色的$ e（k_n）$都包含$ g $的单色副本。它是由Conlon，Fox和Sudakov猜想的，如果一个人从$ g $中删除一个顶点，那么Ramsey号码最多可以改变。我们反驳了这种猜想，表现出无限的图表，使从每个顶点删除单个顶点将拉姆西数量减少了超稳定因子。 结果的结果之一是以下内容。存在一个图的家族$ \ {g_n \} $，以便在任何$ g_n $的ramsey颜色中（即，在$ r（g_n）-1 $ pertices上的颜色，没有$ g_n $的单色副本），其中一个颜色类别具有密度$ o（1）$。
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)$.
