---

Claim. For all sufficiently large $n$ there are graphs on $n$ vertices with $\frac{n^2}4\bigl(1-e^{-(\log n)^{1/6}}\bigr)$ edges in which every edge lies in a triangle and no edge lies in more than $n^{14/\log\log n}$ triangles. This is Theorem 1.1 (arXiv v2, p. 2) of the library's source card. For every fixed $c<1/4$ these graphs have at least $cn^2$ edges once $n$ is large, so the function $f_c(n)$ of Problem 80 (the paper's $h(n,c)$) satisfies $f_c(n)\le n^{14/\log\log n}=n^{o(1)}$, and $f_c(n)>n^\epsilon$ fails for every fixed $\epsilon>0$ and all large $n$. The paper presents the theorem as a negative answer to Erdős's 1987 question whether $f_c(n)>n^\epsilon$ for every fixed $c>0$, and notes that the range $c<1/4$ is best possible, since above $1/4$ a linear book is forced; the previous upper bound in that range was Alon and Trotter's $O(\sqrt n)$.

Covers. The first closing question of Problem 80, whether for every $c>0$ some $\epsilon>0$ has $f_c(n)>n^\epsilon$ for all large $n$: the answer is no, since it fails for every fixed $c<1/4$. Outside this page: the page-level question, to estimate $f_c(n)$; the second closing question, whether $f_c(n)\gg\log n$ for every $c$, which the paper leaves open (its lower bound $2^{\Omega(\log^*n)}$ for fixed $c$ comes from Fox's bound in the triangle removal lemma); and the range $c\ge1/4$, where the property holds: for $c>1/4$ by the bound $f_c(n)\ge n/6$ of Edwards and of Khadzhiivanov and Nikiforov, which the paper cites, which is the theorem of Problem 905, and which is recorded on its own claim page, Khadzhiivanov and Nikiforov 1979, with a proof in Corollary 3 (p. 45) of Khadzhiivanov's 1988 account; and at $c=1/4$ by that account's Corollary 4.

Depends on. Nothing in this wiki; the result is the paper's own theorem.

Acceptance. The site's curator, T. F. Bloom, records the theorem in the problem's commentary as the disproof of Erdős's first conjecture (page last edited 7 April 2026, accessed 2026-09-18), while labeling the problem OPEN because the estimate and the logarithmic question remain; the community database also records the problem open. That commentary is not curator acceptance, so the acceptance rests on the refereed publication. Refereed: Combinatorica 32 (2012), no. 6, 619--628 (the Crossref record, dates the issue December 2012). The version cited is arXiv:1106.0290v2 (5 June 2011); the first posting, v1 of 1 June 2011, names this page. The journal text is not held and was not compared with the preprint, so locators are the preprint's.

Read depth. Claims checked: the definition of $h(n,c)$, Theorem 1.1 and the surrounding paragraphs of p. 2; the construction (Section 3) was not read, and nothing is independently reviewed in this corpus.