GPT 6 Astra Ultra attempt on Math-664

Erdős Problem 80: books in graphs whose edges all lie in triangles

1. Statement and scope

For fixed $0<c<1/2$, let $f_c(n)$ be the least possible maximum number of triangles through an edge in an $n$-vertex graph with at least $cn^2$ edges and every edge in a triangle. The restriction on $c$ ensures that admissible graphs exist for large $n$. We prove elementary density bounds and deduce $f_c(n)\to\infty$ from the triangle removal lemma, stating that input precisely. The finer rate for $c<1/4$, including the proposed logarithmic lower bound, remains unresolved here.

2. Two counts and an elementary linear bound

Let $m=e(G)$, $T$ be its number of triangles, and $B$ its maximum book size. For an edge $uv$, its triangle count is $|N(u)\cap N(v)|$. Counting each triangle at its three edges gives \[ m\le3T\le mB. \tag{1} \] The first inequality uses the hypothesis that every edge is covered. Also \[ \sum_{uv\in E(G)}(d(u)+d(v))=\sum_v d(v)^2\ge4m^2/n. \] Some edge has endpoint-degree sum at least $4m/n$. Since $N(u)\cup N(v)$ has at most $n$ vertices, that edge has at least $4m/n-n$ common neighbours. Thus \[ B\ge (4c-1)n\quad\text{if }m\ge cn^2. \tag{2} \] This is informative for $c>1/4$; it does not give a positive lower bound in the main sparse-density regime.

3. Qualitative divergence via triangle removal

Use the standard triangle removal lemma as an external input: for every $\eta>0$ there is $\delta>0$ such that an $n$-vertex graph with fewer than $\delta n^3$ triangles can be made triangle-free by deleting at most $\eta n^2$ edges. If $T\ge\delta n^3$, then $1$ and $m\le n^2/2$ give $B\ge6\delta n$. Otherwise, let $D$ be a set of at most $\eta n^2$ edges whose deletion kills every triangle. Each original triangle contains an edge of $D$, and each edge of $D$ lies in at most $B$ original triangles. Therefore $T\le B|D|$, and $1$ gives \[ cn^2\le m\le3T\le3B\eta n^2. \] In all cases, \[ B\ge\min\{6\delta(\eta)n,\ c/(3\eta)\}. \tag{3} \] Given any $M>0$, choose $\eta=c/(6(M+1))$. Once $n> (M+1)/(6\delta(\eta))$, both entries on the right of $3$ exceed $M$. This proves $f_c(n)\to\infty$ with the correct order of quantifiers: $\eta$ and its removal constant are fixed before $n$ grows. The proof supplies no good explicit rate without an appropriate quantitative estimate for $\delta(\eta)$.

4. A check on the density bound

For $n$ divisible by three, the complete tripartite graph with three equal parts has $m=n^2/3$, and every edge has exactly $n/3$ common neighbours, all in the third part. Hence $f_c(n)\le n/3$ for $c\le1/3$ on this subsequence. At $c=1/3$, $2$ matches this upper bound exactly: $f_{1/3}(n)=n/3$ when $3\mid n$. This special exact value does not estimate the sublinear regime $c<1/4$. The problem page records the Fox--Loh subpolynomial upper construction there, so a fixed positive power lower bound in that regime is already false; that construction is background, not proved in this text.

5. Assessment and attribution

The counting argument, exact tripartite case, and reduction of divergence to the stated removal lemma are complete. The logarithmic-rate question is unresolved in this attempt. This replaces earlier GPT-5.2 write-ups with an explicit removal argument and carefully scoped conclusions, without claiming a new bound or unperformed exhaustive search. Sources: https://www.erdosproblems.com/80; J. Fox, A new proof of the graph removal lemma, https://arxiv.org/abs/1006.1300.

Completion rate estimate: 25%.