Forcing triangles with local edge densities
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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), 111120.

2  P. Erdös and C. C. Rousseau. The size Ramsey number of a complete bipartite graph. Discrete Math. 113 (1993) no. 13, 259262.

3  M. Krivelevich. On the edge distribution in trianglefree graphs. J. Comb. Theory (B) 63 (1995), 245260.

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), 153161.
