Monotonicity conjecture for the number of rainbow trees

Let k,c,cNk,c,c'\in\mathbb{N} with ccc'\leq c, and let GG be a graph. For r{c,c}r\in\{c,c'\}, let T(r,k)T(r,k) be the random variable counting the number of rainbow trees of order kk when the edges of GG are coloured uniformly with rr colours. Rainbow-tree monotonicity conjecture. The random variable T(c,k)T(c,k) stochastically dominates T(c,k)T(c',k).

A coupling establishing this monotonicity is immediate when c=2cc=2c', but a general coupling was not found. The conjecture formalises the intuition that using more colours should make rainbow substructures more abundant.

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.