If \(G\) has no \(5\)cliques, and any large subset of vertices contains a triangle, then \(G\) is sparse
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
Problem [1]
Suppose a graph \(G\) contains no \(K_5\) and for every \(\epsilon >0\) and \(n \geq n_0(\epsilon)\), every set of \(\epsilon n\) vertices contains a triangle. Is it true that \(G\) can only have \(o(n^2)\) edges?The best available result [1] is that such \( G\) contains at most \( \frac 1 {12} n^2 (1+o(1))\) edges.
Bibliography  

1 
P. Erdös, Problems and results in combinatorial analysis and
combinatorial number theory, Graph theory, combinatorics and
applications, Vol. 1 (Kalamazoo, MI, 1988), WileyIntersci. Publ.,
397406, Wiley, New York, 1991.
