题目：The emergence of a giant rainbow component in random coloured graphs.

报告人：Do Tuan Anh

时间：4月28日10:00

地点：网络与安全创新研究大楼A1236室

报告摘要：

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 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.

嘉宾简介：

Dr. Do Tuan Anh graduated with a PhD from Graz University of Technology in 2023. Since 2024, he has been at Beijing Institute of Technology (BIT) as a Postdoc in a combinatorics group led by Prof. Jie Han. His research mainly concerns probabilistic and extremal combinatorics. He has publications in the SIAM Journal on Discrete Mathematics, the European Journal of Combinatorics, the Journal of Graph Theory, and the Electronic Journal of Combinatorics