Monotonicity conjecture for the number of rainbow trees

About 4 years old · traced to

Let k,c,c′∈Nk,c,c'\in\mathbb{N} with c′≤cc'\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=2c′c=2c', but a general coupling was not found. The conjecture formalises the intuition that using more colours should make rainbow substructures more abundant.

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.