论文标题
约束Ramsey属性的阈值
The threshold for the constrained Ramsey property
论文作者
论文摘要
给定图形$ g $，$ h_1 $和$ h_2 $，令$ g \ xrightArrow {\ text {mr}}（h_1，h_2）$表示属性，在$ g $的每一个边缘着色中都有$ h_1 $的单色副本或$ h_1 $或$ h_2 $ $ h_2 $的彩虹副本。被限制的Ramsey号码定义为最小$ n $，因此存在$ k_n \ xrightArrow {\ text {mr}}（h_1，h_2）$，并且仅当$ h_1 $是星或$ h_2 $时，才存在。我们确定属性$ g（n，p）\ xrightArrow {\ text {mr}}}（h_1，h_2）$的阈值时，当$ h_2 $是森林时，当阈值为$ω（n^{ - 1}）时，明确是森林。
Given graphs $G$, $H_1$, and $H_2$, let $G\xrightarrow{\text{mr}}(H_1,H_2)$ denote the property that in every edge colouring of $G$ there is a monochromatic copy of $H_1$ or a rainbow copy of $H_2$. The constrained Ramsey number, defined as the minimum $n$ such that $K_n\xrightarrow{\text{mr}}(H_1,H_2)$, exists if and only if $H_1$ is a star or $H_2$ is a forest. We determine the threshold for the property $G(n,p)\xrightarrow{\text{mr}}(H_1,H_2)$ when $H_2$ is a forest, explicitly when the threshold is $Ω(n^{-1})$ and implicitly otherwise.
