Davoodi–Javadi–Omoomi lower-bound conjecture for sigma clique coverings

Let Kt(d)K_t(d) be the complete tt-partite graph with each part of size dd. Davoodi–Javadi–Omoomi's conjecture. There exists a function ff and a constant c>0c>0 such that, for every positive integers tt and dd, if tf(d)t\geq f(d), then

scc(Kt(d))cd2tlogt.\operatorname{scc}(K_t(d))\geq cd^2t\log t.

This conjecture predicts that complete multipartite graphs attain, up to a constant factor, the logarithmic upper bound for the sigma clique cover number when the number of parts is sufficiently large relative to their size. The paper presents an equivalent set-system formulation and proves related lower bounds, but the stated asymptotic bound remains open.

Sources & referencesView supporting material

Primary source

Akbar Davoodi, Dániel Gerbner, Abhishek Methuku and Máté Vizer, “On Clique Coverings of Complete Multipartite Graphs”, arXiv:1809.01443 (2018).

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.