受限Ramsey问题与反Ramsey问题的阈值

Thresholds for constrained Ramsey and anti-Ramsey problems

摘要 Abstract

设 $H_1$ 和 $H_2$ 是图。若图 $G$ 的任意边染色都包含一个单色的 $H_1$ 或彩虹的 $H_2$,则称 $G$ 具有 $(H_1, H_2)$ 的受限Ramsey性质。我们的主要结果给出了当 $H_1 = K_{1,k}$(其中 $k \geq 3$)且 $H_2$ 不是森林时,$G(n,p)$ 中受限Ramsey性质的零陈述。结合Kohayakawa、Konstadinidis和Mota的先前工作,除了 $H_1 = K_{1,2}$ 的特殊情况外,所有非平凡情况下的受限Ramsey性质均得以解决,而 $H_1 = K_{1,2}$ 等价于 $H_2$ 的反Ramsey性质。对于固定图 $H$,如果 $G$ 的任意正常边染色都包含一个彩虹的 $H$,则称 $G$ 具有 $H$ 的反Ramsey性质。我们证明了 $G(n,p)$ 中反Ramsey问题的零陈述可以归约为一个必要条件的染色陈述,并利用此结果得到了某些特定图族的反Ramsey性质的阈值。

Let $H_1$ and $H_2$ be graphs. A graph $G$ has the constrained Ramsey property for $(H_1,H_2)$ if every edge-colouring of $G$ contains either a monochromatic copy of $H_1$ or a rainbow copy of $H_2$. Our main result gives a 0-statement for the constrained Ramsey property in $G(n,p)$ whenever $H_1 = K_{1,k}$ for some $k \ge 3$ and $H_2$ is not a forest. Along with previous work of Kohayakawa, Konstadinidis and Mota, this resolves the constrained Ramsey property for all non-trivial cases with the exception of $H_1 = K_{1,2}$, which is equivalent to the anti-Ramsey property for $H_2$. For a fixed graph $H$, we say that $G$ has the anti-Ramsey property for $H$ if any proper edge-colouring of $G$ contains a rainbow copy of $H$. We show that the 0-statement for the anti-Ramsey problem in $G(n,p)$ can be reduced to a (necessary) colouring statement, and use this to find the threshold for the anti-Ramsey property for some particular families of graphs.

受限Ramsey问题与反Ramsey问题的阈值 - arXiv