Giant rainbow trees in sparse random graphs (Q6957477)

This paper considers the size of the largest rainbow tree in a supercritical sparse random graph whose edges are coloured randomly. The authors start with the binomial random graph \(G(n,(1+\epsilon)/n)\) on \(n\) vertices, where each pair is included as an edge with probability \((1+\epsilon)/n\), independently of any other pair. Here, the parameter \(\epsilon >0\) is fixed, that is, it does not depend on \(n\). It is a classic result in the theory of random graphs that such a random graph typically has a unique largest connected component of order about \(2\epsilon n\) (known as the giant component), whereas any other component has logarithmic order. Now, consider a collection of \(c = \alpha n\) colours or labels and the edges of the random graph are coloured independently with one of these colours selected uniformly at random. In what is their main result, the authors show that the random graph contains a rainbow tree (that is, a tree where no colour is repeated) of order \((1+O(\epsilon \log 1/\epsilon)) 2\epsilon n\), for any \(\epsilon\) sufficiently small. This proves (up to the term \(\log 1/\epsilon\)) a conjecture of \textit{O. Cooley} et al. [Eur. J. Comb. 127, Article ID 104154, 20 p. (2025; Zbl 1566.05041)].