Giant rainbow tree size conjecture near the phase transition

Let Gc(n,p)G_c(n,p) be the random graph on nn vertices whose edges are independently present with probability pp and uniformly coloured with cc colours. Let b1>0b1>0, set c=b1nc=b1 n, let b5>0b5>0 be sufficiently small, and set p=1+b5np=\frac{1+b5}{n}. Giant rainbow tree conjecture. With high probability, the largest rainbow tree in Gc(n,p)G_c(n,p) has order

(2b5+O(b52))n.\left(2b5+O\left(b5^2\right)\right)n.

This would sharpen the proved estimate that the largest rainbow tree has order Θ(b5n)\Theta(b5 n), matching the asymptotic order of the giant component in the corresponding ordinary random graph.

Sources & referencesView supporting material

Primary source

Oliver Cooley, Tuan Anh Do, Joshua Erde and Michael Missethan, “The emergence of a giant rainbow component”, arXiv:2210.11972 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.