Logarithmic balanced-clique conjecture for graphs with fixed triangle density

Let GG be a graph on nn vertices with triangle density γ\gamma. For an integer tt, let Kt,t,tK_{t,t,t} denote the balanced complete tripartite graph with three parts of size tt.

Logarithmic balanced-clique conjecture. There is an absolute constant c>0c>0 such that GG contains a copy of Kt,t,tK_{t,t,t} with

t=clog1/γn.t=c\log_{1/\gamma}n.

This would match the logarithmic scale suggested by a random graph with edge density γ1/3\gamma^{1/3}. The text presents it as an improvement of Nikiforov's result, and no resolution is given.

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.