Critical density formula for complete bipartite graphs

Let Kn,mK_{n,m} be the complete bipartite graph. Denote its critical edge density by dcrit(Kn,m)=d(n,m)d_{crit}(K_{n,m})=d(n,m) and the best edge density obtained from star decomposition by ds(n,m)d_s(n,m). Complete bipartite star-decomposition conjecture.

dcrit(Kn,m)=ds(n,m)=11n+m1.d_{crit}(K_{n,m})=d_s(n,m)=1-\frac{1}{n+m-1}.

The formula is stated in the complete bipartite graph case, but the source does not provide a resolution status for this conjectural claim.

Sources & referencesView supporting material

Primary source

Péter Csikvári and Zoltán Lóránt Nagy, “The Density Turán problem”, arXiv:1407.7873 (2014).

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.