Problem Statement
Let $c>0$ and let $f_c(n)$ be the maximal $m$ such that every graph $G$ with $n$ vertices and at least $cn^2$ edges, where each edge is contained in at least one triangle, must contain a book of size $m$, that is, an edge shared by at least $m$ different triangles.
Estimate $f_c(n)$. In particular, is it true that $f_c(n)>n^{\epsilon}$ for some $\epsilon>0$? Or $f_c(n)\gg \log n$?
Estimate $f_c(n)$. In particular, is it true that $f_c(n)>n^{\epsilon}$ for some $\epsilon>0$? Or $f_c(n)\gg \log n$?
Categories:
Graph Theory Ramsey Theory
Progress
A problem of Erdős and Rothschild. Alon and Trotter showed that, provided $c<1/4$, $f_c(n)\ll_c n^{1/2}$. Szemerédi observed that his regularity lemma implies that $f_c(n)\to \infty$.Edwards (unpublished) and Khadziivanov and Nikiforov [KhNi79] proved independently that $f_c(n) \geq n/6$ when $c>1/4$ (see [905]).
Fox and Loh [FoLo12] proved that\[f_c(n) \leq n^{O(1/\log\log n)}\]for all $c<1/4$, disproving the first conjecture of Erdős.
The best known lower bounds for $f_c(n)$ are those from Szemerédi's regularity lemma, and as such remain very poor.
See also [600] and the entry in the graphs problem collection.
Source: erdosproblems.com/80 | Last verified: January 13, 2026