Balanced blow-up conjecture for triangle densities

Let GG be a graph with triangle density γ\gamma, and let fB(γ)f_B(\gamma) denote the minimum possible density of copies of BB among such graphs. For an integer t2t\geq 2, set

B=Kt,t,t.B=K_{t,t,t}.

Balanced blow-up conjecture. For every t2t\geq 2,

fB(γ)=γt2.f_B(\gamma)=\gamma^{t^2}.

This asserts that the random-graph upper bound has the correct order for balanced blowups of K3K_3. The supplied text does not state a resolution; it notes that improvements to the corresponding lower bound would have applications in theoretical computer science.

Sources & referencesView supporting material

Primary source

Asaf Shapira and Raphael Yuster, “On the Density of a Graph and its Blowup”, arXiv:0903.0198 (2009).

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.