报告题目: A giant rainbow component in random coloured graphs

报告人: Tuan Anh Do 北京理工大学

报告时间: 4.15日周三下午3:00-4:00

报告地点: 2106

摘要: 

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 paper we determine the asymptotic order of the largest rainbow tree in the \emph{weakly supercritical regime}, when $p = \frac{1+\eps}{n}$ for some $\eps=\eps(n)>0$ which satisfies $\eps = o(1)$ and $\eps^3 n\to\infty$. We show that with high probability the giant 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$. In particular we show that for any $\delta >0$ there is some $d$ such that if $c\ge n$, with high probability $G_c(n,d/n)$ contains an almost spanning (of length at least $(1-\delta)n$) rainbow cycle. This is a joint work with Cooley, Erde and Missethan.