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