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), Wiley-Intersci. Publ.,
397-406, Wiley, New York, 1991.
|