Triangle count bound via book number in dense graphs

Conjecture 1.1 · arXiv:1905.05312

arXiv Conjecture high confidence— first stated 2019-10-20

Authors: David Conlon, Jacob Fox, Benny Sudakov

Status partial high confidence

Conjecture 1.1 remains open in full generality. The authors themselves proved it for the boundary case b = n/6 and for the near-upper-boundary range 0.2495n ≤ b < n/4, leaving the bulk of the interval n/6 < b < 0.2495n unresolved. No subsequent paper resolving the remaining cases was found in the indexed literature as of May 2026.

Reviewer notes. The conjecture was partially proved in the source paper itself: it holds at b = n/6 and for 0.2495n ≤ b < n/4. Web searches and a Semantic Scholar citation query returned no follow-up paper resolving the remaining range n/6 < b < 0.2495n. The conjecture is classified as partial (proved in special cases by the authors) with high confidence that no full resolution has appeared.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. If $n/6 \leq b < n/4$, then every graph on $n$ vertices with at least $\lfloor n^2/4 \rfloor$ edges and book number at most $b$ which is not the balanced complete bipartite graph has at least $b^2(n - 4b)$ triangles, with equality if and only if the graph is $S_{b,n}$.

Context

The authors introduce the 3-prism blow-up $S_{b,n}$ — formed by blowing up the 3-prism graph with four parts of size $b$ and two parts of size $\lfloor(n-4b)/2\rfloor$ and $\lceil(n-4b)/2\rceil$ — as the conjectured extremal construction. The conjecture implies an asymptotically tight bound on $t(n,b)$ for $n/6 \leq b \leq n/4 - \omega(1)$, fully addressing Mubayi's question about the $\gamma(\beta)$ dependency. A footnote notes the construction is essentially identical to one in an earlier arXiv version of Mubayi's paper.

Source paper

Books versus triangles at the extremal density
David Conlon, Jacob Fox, Benny Sudakov · 2019-10-20
https://arxiv.org/abs/1905.05312 PDF source