论文标题
巨型彩虹部分的出现
The emergence of a giant rainbow component
论文作者
论文摘要
随机彩色图$ g_c（n，p）$是从erdős-rényi二项式随机图$ g（n，p）$获得的，通过分配给每个边缘的颜色，从一组$ c $颜色的颜色分配为随机独立且均匀的颜色。不难看到，当$ c =θ（n）$时，该模型中最大的彩虹树的顺序会在关键点$ p = \ frac {1} {n} $处进行相变。在本文中，我们确定\ emph {弱的亚和超临界方案中最大的彩虹树的渐近顺序，当$ p = \ frac {1+\ varepsilon} {n} {n} $ for $ \ \ \ \ \ varepsilon = \ varepsilon = \ varepsilon（n）的$ \ varepsilon（n）$ $ \ vareps $ \ vareps | n \ to \ infty $。特别是，我们表明，在这两种情况下，概率很高的是$ g_c（n，p）$的最大组成部分，均包含几乎跨越的彩虹树。我们还考虑\ emph {稀疏制度}中最大的彩虹树的顺序，当$ p = \ frac {d} {n} $ for Somand constance $ d> 1 $时。在这里，我们表明，最大的彩虹树具有线性顺序，此外，对于$ d $和$ c $，大大，高概率$ g_c（n，p）$甚至包含几乎跨越的彩虹循环。
The random coloured graph $G_c(n,p)$ is obtained from the Erdős-Rényi binomial random graph $G(n,p)$ by assigning to each edge a colour from a set of $c$ colours independently and uniformly at random. It is not hard to see that, when $c = Θ(n)$, the order of the largest rainbow tree in this model undergoes a phase transition at the critical point $p=\frac{1}{n}$. In this paper we determine the asymptotic order of the largest rainbow tree in the \emph{weakly sub- and supercritical regimes}, when $p = \frac{1+\varepsilon}{n}$ for some $\varepsilon=\varepsilon(n)$ which satisfies $\varepsilon = o(1)$ and $|\varepsilon|^3 n\to\infty$. In particular, we show that in both of these regimes with high probability the largest component of $G_c(n,p)$ contains an almost spanning rainbow tree. We also consider the order of the largest rainbow tree in the \emph{sparse regime}, when $p = \frac{d}{n}$ for some constant $d >1$. Here we show that the largest rainbow tree has linear order, and, moreover, for $d$ and $c$ sufficiently large, with high probability $G_c(n,p)$ even contains an almost spanning rainbow cycle.
