Giant rainbow trees in sparse random graphs

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05)

Review text

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

Cites work

This page was built for publication: Giant rainbow trees in sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6957477)