Giant rainbow tree size conjecture near the phase transition

At least 3 years old · documented by

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.

References

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.