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

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 satt(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 k3k\ge 3 and t(k2)t\ge {k\choose 2},

satt(n,R(Kk))=Θ(nlogn).\operatorname{sat}_t(n,\mathcal{R}(K_k))=\Theta(n\log n).

This refines known bounds of order between nlog(n)/loglog(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.

Sources & referencesView supporting material

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.