Erdős Problem #80

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\)? The answer is no. Fox and Loh [FoLo12] proved that \(f_c(n) \leq n^{O(1/\log\log n)}\) for every fixed \(c < 1/4\), so no \(\epsilon > 0\) works for, say, \(c = 1/8\). For \(c > 1/4\) the situation is different: \(f_c(n) \geq n/6\), see [erdosproblems.com/80](https://www.erdosproblems.com/80). The bound \(c < 1/2\) is what makes the hypothesis satisfiable: a simple graph on \(n\) vertices has at most \(n(n-1)/2\) edges, so no graph has \(cn^2\) of them once \(c \geq 1/2\).