Logo
All Random Solved Random Open
OPEN
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$?
Ruzsa and Szemerédi [RuSz78] proved that $e(n,r)=o(n^2)$ for any fixed $r$.

See also [80].