On a problem of Erdös and Rothschild on edges in triangles

Erdös and Rothschild asked to estimate the maximum number, denoted by $h(n,c)$, such that every $n$-vertex graph with at least $cn^2$ edges, each of which is contained in at least one triangle, must contain an edge that is in at least $h(n,c)$ triangles. In particular, Erdös asked in 1987 to determine whether for every $c>0$ there is $\epsilon>0$ such that $h(n,c)>n^{\epsilon}$ for all sufficiently large $n$. We prove that $$h(n,c)=n^{O(1/\log \log n)}$$ for every fixed $c<1/4$. This gives a negative answer to the question of Erdös, and is best possible in terms of the range for $c$, as it is known that every $n$-vertex graph with more than $n^2/4$ edges contains an edge that is in at least $n/6$ triangles.

Joint work with Jacob Fox.