The emergence of a giant rainbow component

Thời gian: 9h15-10h30 thứ năm, ngày 11/12/2025

Địa điểm: Phòng 507 nhà A6

Tóm tắt: The random coloured graph $G_c(n,p)$ is obtained from the Erd\H{o}s-R\'{e}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 = \Theta(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 talk, we determine the asymptotic order of the largest rainbow tree in the \emph{weakly sub-  and supercritical regimes}, when $p = \frac{1+\eps}{n}$ for some $\eps=\eps(n)$ which satisfies $\eps = o(1)$ and $|\eps|^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