Edges forcing an $r$-triangle edge: are the thresholds $e(n,r)$ asymptotically flat in $r$? (Erdős #600)
Statement
Consider graphs $G$ on $n$ vertices in which every edge lies in at least one triangle. Let $e(n,r)$ be the least number of edges that forces some edge to lie in at least $r$ triangles: precisely, $e(n,r)$ is minimal such that every $n$-vertex graph with at least $e(n,r)$ edges, each edge in at least one triangle, must contain an edge lying in at least $r$ triangles. Fix $r\geq 2$. Is it true that $$e(n,r+1)-e(n,r)\to\infty$$ as $n\to\infty$, and that $$\frac{e(n,r+1)}{e(n,r)}\to 1$$ as $n\to\infty$?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else full written) settling both questions for every fixed $r\geq2$ — that $e(n,r+1)-e(n,r)\to\infty$ and $e(n,r+1)/e(n,r)\to1$ — OR a disproof of either (a proof that the difference stays bounded along a subsequence, or that the ratio is bounded away from $1$). ADVANCES: prove either statement on its own (the divergence of the difference, or the ratio $\to1$) for all $r\geq2$ or for a specific value such as $r=2$, with proof; OR establish new upper or lower bounds on $e(n,r)$ that sharpen the Ruzsa–Szemerédi $o(n^2)$ into an explicit rate, with proof; OR compute $e(n,r)$ exactly for a new range of small $n$ and $r\geq2$ via a reproducible extremal-graph search with an exhaustiveness certificate, reporting the observed differences and ratios. Deliver the proof file, or the search code plus certified value table.
Background
Asked by Erdős [Er87]. The foundational input is the Ruzsa–Szemerédi theorem [RuSz78]: for every fixed $r$, $e(n,r)=o(n^2)$ — this is the celebrated (6,3)-theorem / triangle-removal phenomenon, one of the deepest results in extremal graph theory, which implies the corners theorem and Roth's theorem on 3-term arithmetic progressions. The present two questions probe the fine structure of $e(n,r)$ as $r$ grows: whether consecutive differences diverge while the ratio tends to $1$ (so $e(n,r)$ increases with $r$, but only in a lower-order way relative to its own size). Listed as open on erdosproblems.com/600 (fetched 2026-07-13, status 'open', tagged 'graph theory'); related to Erdős #80 (erdosproblems.com/80). No Erdős prize is attached. The attacker's tool: extremal-graph computation of $e(n,r)$ for small $n$ and $r$ (ILP/exhaustive search over graphs whose every edge lies in a triangle) to gather asymptotic data on the differences and ratios, combined with Behrend-type / Ruzsa–Szemerédi constructions to bound $e(n,r)$ from below.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #600 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.