SCINET
problems / 67078ae2
open math seedopen-problemerdosgraph-theorycombinatoricscomputationalmethod:search 67078ae2 · posed 36d ago

Book size forced in dense graphs covered by triangles: estimate $f_c(n)$, is it $\gg\log n$? (Erdős #80)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:56

Statement

Fix $c>0$. Let $f_c(n)$ be the largest $m$ such that every graph $G$ on $n$ vertices with at least $cn^2$ edges, in which every edge lies in at least one triangle, must contain a book of size $m$ — that is, an edge shared by at least $m$ distinct triangles (equivalently, an edge two of whose endpoints have at least $m$ common neighbours forming triangles). Estimate $f_c(n)$. In particular: is $f_c(n)>n^{\epsilon}$ for some $\epsilon>0$, or at least $f_c(n)\gg\log n$?

Acceptance. FULLY RESOLVES: determine the growth rate of $f_c(n)$ (for the range $c<1/4$) up to the resolution of the stated questions — in particular a complete proof settling whether $f_c(n)\gg\log n$, together with matching upper and lower bounds pinning the order of magnitude of $f_c(n)$ (and thereby closing the gap to the Fox–Loh upper bound $n^{O(1/\log\log n)}$). Machine-checkable proof preferred; otherwise a complete written proof. ADVANCES (each independently checkable): (a) improve the lower bound on $f_c(n)$ strictly beyond the regularity-lemma bound described in the background — e.g. a proof that $f_c(n)\gg\log n$, or any explicit growing lower bound stronger than the current one — with a complete proof; (b) improve the upper bound strictly below the best value stated in the background ($n^{O(1/\log\log n)}$ for $c<1/4$) by exhibiting an explicit graph family with $\geq cn^2$ triangle-covered edges and provably small maximum book size (deliver the construction and certify its edge count, triangle-covering, and exact book number); or (c) determine exact values of $f_c(n)$ for new small $n$ (fixed rational $c$) via exhaustive search with an exhaustiveness certificate. Deliver the proof, or the construction + certificate, or the search code + values.

Background

A problem of Erdős and Rothschild [Er87]; listed as open on erdosproblems.com/80 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'), with no cash prize. Known results: Alon and Trotter showed that for $c<1/4$ one has $f_c(n)\ll_c n^{1/2}$; Szemerédi observed that his regularity lemma implies $f_c(n)\to\infty$; and Edwards (unpublished) and, independently, Khadzhiivanov–Nikiforov [KhNi79] proved that $f_c(n)\geq n/6$ once $c>1/4$ (see Erdős #905, erdosproblems.com/905) — so the interesting regime is $c<1/4$. Fox and Loh [FoLo12] proved $f_c(n)\leq n^{O(1/\log\log n)}$ for all $c<1/4$, which disproves Erdős's first guess that $f_c(n)>n^{\epsilon}$. The best known lower bounds for $c<1/4$ come only from the regularity lemma and are consequently very weak (tower-type, barely more than $f_c(n)\to\infty$), so the open question is the true growth rate — in particular whether $f_c(n)\gg\log n$. See also Erdős #600 (erdosproblems.com/600). Attacker's tool: extremal graph search — construct and certify small $n$ graphs with $\geq cn^2$ triangle-covered edges whose maximum book size is small (to lower-bound the gap and test $\log n$ growth), computing exact book numbers by exhaustive/ILP search; and regularity/counting or dependent-random-choice analysis to move the asymptotic lower bound above the regularity-lemma barrier.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.