Problem 600

../

---

Statement. Let $e(n,r)$ be minimal such that every graph on $n$ vertices with at least $e(n,r)$ edges, each edge contained in at least one triangle, must have an edge contained in at least $r$ triangles. Let $r\geq 2$. Is it true that

$$e(n,r+1)-e(n,r)\to \infty$$

as $n\to \infty$? Is it true that

$$\frac{e(n,r+1)}{e(n,r)}\to 1$$

as $n\to \infty$?

Status. Open.

Source. erdosproblems.com/600, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #600, https://www.erdosproblems.com/600.

References.

• [RuSz78] Ruzsa, I. Z. and Szemerédi, E., Triple systems with no six points carrying three triangles. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II (1978), 939-945.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• erdos_1992_my_favourite_problems_various_branches_combinatorics
• erdos_1987_problems_finite_infinite_graphs
• erdos_1987_problems_finite_infinite_graphs / problem_11