Forcing triangles with local edge densities

The following problem[2] relates the edge density of a graph to the containment of triangles:

A conjecture on local edge density and triangles (proposed by Erdös and Rousseau[2])

If each set of \(\lfloor n/2 \rfloor \) vertices in a graph \(G \) with \(n\) vertices spans more than \(n^2/50\) edges, then \(G\) contains a triangle.

A more general but slightly weaker version was proved [4] which asserts that for all sufficiently large \( n\), a graph on \( n\) vertices in which each set of \( \lfloor \alpha n \rfloor\) vertices spans at least \( \beta n^2\) edges must contain a triangle if \( \alpha \geq .648\) and \( \beta > (2 \alpha -1)/4\). Krivelevich [3] showed that a graph on \( n\) vertices in which each set of \( \lfloor \alpha n \rfloor\) vertices spans at least \( \beta n^2\) edges must contain a triangle if \( \alpha \geq .6\) and \( \beta > (5 \alpha -2)/25\).

Chung and Graham [1] made the following related conjecture:

Conjecture

Let \( b_t(n)\) denote the maximum number of edges induced by any set of \( \lfloor n/2 \rfloor\) vertices in the Turán graph on \( n\) vertices for \( K_t\). If each set of \( \lfloor n/2 \rfloor\) vertices in a graph with \( n\) vertices spans more than \( b_t(n)\) edges, then \( G\) contains a \( K_t\).

Bibliography
1 F. R. K. Chung and R. L. Graham. On graphs not containing prescribed induced subgraphs. A Tribute to Paul Erdös, (eds. A. Baker, B. Bollobás, and A. Hajnal), Cambridge University Press, Cambridge, (1990), 111-120.

2 P. Erdös and C. C. Rousseau. The size Ramsey number of a complete bipartite graph. Discrete Math. 113 (1993) no. 1-3, 259-262.

3 M. Krivelevich. On the edge distribution in triangle-free graphs. J. Comb. Theory (B) 63 (1995), 245-260.

4 P. Erdös, R. Faudree, C. C. Rousseau and R. H. Schelp, A local density condition for triangles, Discrete Math., Graph theory and applications (Hakone, 1990), Discrete Math. 127 (1994), 153-161.