Three-colour random bipartite tree-cover threshold conjecture

Let GG(n,n,p)G\sim G(n,n,p) be a random bipartite graph with two parts of size nn, and let tc3(G)\operatorname{tc}_3(G) be the minimum number of monochromatic trees whose vertices cover GG in every 3-edge-colouring. Three-colour random bipartite conjecture. There exists a constant CC such that if

pC(logn/n)1/4,p\ge C(\log n/n)^{1/4},

then with high probability

tc3(G)5.\operatorname{tc}_3(G)\le 5.

This is proposed as the three-colour analogue of the two-colour threshold question and remains open.

Sources & referencesView supporting material

Primary source

Camila Fernández, Matías Pavez-Signé and Maya Stein, “Monochromatic partitions in 2-edge-coloured bipartite graphs”, arXiv:2403.12587 (2024).

Additional references

3 papers in this index state this conjecture (2016–2024). The statement above is taken from the most recent of them; the others are arXiv:2204.00496, arXiv:1607.03348.

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.