Problem 80

Erdős Problem #80: declared status 'open'. Formalized: no. 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$? Current best: The best known lower bounds for $f_c(n)$ are those from Szemer\'{e}di's regularity lemma, and as such remain very poor. Prize: no. Tags: graph theory, ramsey theory.