Barrus–Ferrara–Vandenbussche–Wenger conjecture on rainbow clique saturation

About 9 years old · traced to

Let KkK_k be the complete graph on kk vertices, let R(Kk)\mathcal{R}(K_k) be the family of rainbow edge-colorings of KkK_k, and let sat⁡t(n,R(Kk))\operatorname{sat}_t(n,\mathcal{R}(K_k)) denote the minimum number of edges in an nn-vertex graph that is (R(Kk),t)(\mathcal{R}(K_k),t)-saturated. Barrus–Ferrara–Vandenbussche–Wenger conjecture. For k≥3k\ge 3 and t≥(k2)t\ge {k\choose 2},

sat⁡t(n,R(Kk))=Θ(nlog⁡n).\operatorname{sat}_t(n,\mathcal{R}(K_k))=\Theta(n\log n).

This refines known bounds of order between nlog⁡(n)/log⁡log⁡(n)n\log(n)/\log\log(n) and nlog⁡(n)n\log(n) for rainbow clique saturation, and the stated asymptotic equality remains unresolved in the supplied source.

References

Primary source

Michael Ferrara, Daniel Johnston, Sarah Loeb, Florian Pfender, Alex Schulte, Heather C. Smith, Eric Sullivan, Michael Tait and Casey Tompkins, “On Edge-Colored Saturation Problems”, arXiv:1712.00163 (2017).

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.