pith. sign in

arxiv: 2605.02652 · v1 · submitted 2026-05-04 · 🧮 math.CO

Books versus Triangles near the n/6 Threshold

Kaizhe Chen , Jie Ma , Tianhen Wang This is my paper

Pith reviewed 2026-05-08 17:34 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C35
keywords extremal graph theorybook numbertrianglesMantel's theoremstability theorem3-prism blow-upConlon-Fox-Sudakov conjecture
0
0 comments X

The pith

For book numbers from n/6 up to (1/6 + ε)n, every graph with at least floor(n²/4) edges and book number at most b has at least b²(n - 4b) triangles unless it is the 3-prism blow-up.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that a conjecture on the minimum number of triangles in n-vertex graphs with more than the Mantel number of edges holds in an interval starting at the book-number threshold n/6 and extending a positive fraction beyond it. The conjecture predicts that such graphs contain at least b²(n - 4b) triangles when the maximum number of triangles per edge is bounded by b, with equality only for a specific six-partite graph obtained by blowing up the 3-prism. The authors first prove a stability result showing that any extremal graph must be close in structure to this blow-up, then perform a parameter-by-parameter analysis to pin down the exact part sizes and force the triangle count. A sympathetic reader cares because the result closes the gap between the known endpoint at b = n/6 and the previously resolved interval near b = n/4, confirming that the tradeoff between global triangle count and local book density behaves as predicted near the lower threshold.

Core claim

There exists a constant ε > 0 such that for every n/6 ≤ b ≤ (1/6 + ε)n, every n-vertex graph G with at least floor(n²/4) edges and book number b(G) ≤ b, other than the balanced complete bipartite graph, satisfies the inequality that the number of triangles in G is at least b²(n - 4b), with equality if and only if G is the balanced blow-up of the 3-prism.

What carries the argument

A stability theorem asserting that every graph achieving the conjectured minimum triangle count with the given book bound is close to a blow-up of the 3-prism, followed by a detailed parameter analysis that forces the exact balanced six-partite structure.

If this is right

  • The minimum number of triangles is realized exactly by the balanced 3-prism blow-up throughout the interval n/6 to (1/6 + ε)n.
  • The conjectured lower bound on triangles is continuous from the known case b = n/6 onward for a positive-length interval.
  • Any extremal graph in this range must have a six-partite vertex partition with part sizes differing by at most a small fraction of n.
  • The book number bound forces the graph to avoid dense substructures that would create extra triangles beyond the predicted count.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The stability-plus-parameter-analysis method may extend further into the interval toward n/4, potentially resolving the full conjecture with the same core ideas.
  • The 3-prism blow-up appears to be the unique minimizer near the threshold, which could indicate it governs the entire range of the conjecture.
  • Similar stability techniques might apply to other strengthenings of Mantel's theorem that bound the maximum number of triangles per edge or per vertex.

Load-bearing premise

Any graph that nearly achieves the minimum triangle count with book number at most b must be structurally close to a blow-up of the 3-prism.

What would settle it

An explicit n-vertex graph with b = n/6 + δn for small δ that has fewer than b²(n - 4b) triangles or whose neighborhood structure deviates significantly from any blow-up of the 3-prism.

Figures

Figures reproduced from arXiv: 2605.02652 by Jie Ma, Kaizhe Chen, Tianhen Wang.

Figure 1
Figure 1. Figure 1: The extremal graph Sb,n. Each solid or dashed line represents a complete bipar￾tite graph. Conlon, Fox, and Sudakov [2] proved Conjecture 1.2 when (1/4 − 1/2000)n ≤ b < n/4 and when b = n/6. They also proved a quantitative lower bound near the endpoint n/6: let G be an n-vertex graph with at least n 2/4 edges which is not the balanced complete bipartite graph. If η > 0 is sufficiently small and b(G) ≤ (1/6… view at source ↗
Figure 2
Figure 2. Figure 2: Construction of W2, W3, and W4 which implies dU (v) ≥ view at source ↗
Figure 3
Figure 3. Figure 3: Construction of W1, W5, and W6 2 view at source ↗
read the original abstract

The book number $b(G)$ of a graph $G$ is the maximum number of triangles sharing a common edge. A strengthening of Mantel's theorem due to Rademacher states that every $n$-vertex graph with more than $\lfloor n^2/4\rfloor$ edges contains at least $\lfloor n/2\rfloor$ triangles. Another strengthening, initiated by Erd\H{o}s, asserts that every such graph $G$ satisfies $b(G)\ge n/6$. Motivated by these results, Mubayi studied the tradeoff between the total number of triangles and the book number in such graphs, and asymptotically resolved the problem when $n/4\le b(G)\le n/2$. Conlon, Fox, and Sudakov conjectured that, for $n/6\le b< n/4$, every $n$-vertex graph with at least $\lfloor n^2/4\rfloor$ edges and book number at most $b$, other than the balanced complete bipartite graph, has at least $b^2(n-4b)$ triangles, with equality only for the blow-up $S_{b,n}$ of the $3$-prism. They proved the conjecture when $b$ lies in an interval with endpoint $n/4$, and also at the endpoint $b=n/6$, where they asked whether it remains valid in an interval containing this endpoint. In this paper, we answer this question affirmatively. We show that there exists a constant $\varepsilon>0$ such that the conjecture holds for all $n/6\le b\le (1/6+\varepsilon)n$. Our proof first establishes a stability theorem showing that every extremal graph is close to a blow-up of the $3$-prism, and then uses a detailed parameter analysis to force the exact six-partite structure.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves that there exists ε > 0 such that the Conlon-Fox-Sudakov conjecture holds for all n/6 ≤ b ≤ (1/6 + ε)n: every n-vertex graph with at least ⌊n²/4⌋ edges and book number at most b (other than the balanced complete bipartite graph) contains at least b²(n - 4b) triangles, with equality only for the blow-up S_{b,n} of the 3-prism. The argument first establishes a stability theorem that every extremal graph is close in edit distance to a blow-up of the 3-prism, then performs a detailed parameter analysis on part sizes and edge densities to force the exact six-partite balanced structure and the triangle lower bound.

Significance. If the result holds, it extends the verified range of the conjecture from an interval near n/4 down to an interval containing the n/6 endpoint, supplying further evidence toward the full statement. The stability theorem supplies the quantitative closeness needed for the subsequent finite-dimensional case analysis, which is a standard and verifiable technique in this area of extremal graph theory.

minor comments (2)
  1. [Abstract] The abstract states that the stability theorem shows every extremal graph is 'close' to a blow-up of the 3-prism but does not indicate the quantitative edit-distance bound or the precise notion of closeness used; this parameter is load-bearing for the subsequent analysis and should be stated explicitly in the introduction or §2.
  2. The parameter analysis is described as 'detailed' and 'finite-dimensional' but the manuscript does not indicate how many cases arise or which parameters (part-size deviations, edge densities between parts) are treated as free variables; a short roadmap or table of cases would improve readability without altering the argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the recognition of the stability theorem and parameter analysis as standard techniques that extend the verified range of the Conlon-Fox-Sudakov conjecture down to an interval containing the n/6 endpoint. The recommendation for minor revision is noted.

Circularity Check

0 steps flagged

No circularity: stability theorem and parameter analysis are independent

full rationale

The derivation proceeds by first proving a stability result (extremal graphs are edit-close to 3-prism blow-ups) and then performing a finite-dimensional case analysis on part sizes and densities to force the exact balanced six-partite structure and triangle lower bound. Both steps are standard in extremal graph theory, rely on quantitative closeness and direct counting, and do not reduce to self-definition, fitted inputs renamed as predictions, or load-bearing self-citations. The existence of some ε>0 follows from the analysis without circular reduction to the target interval.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Relies on standard graph-theoretic definitions and known stability techniques; no free parameters or new entities introduced.

axioms (2)
  • standard math Standard axioms and definitions of simple graphs, edges, triangles, and book number b(G).
    Foundational objects for the statement and proof.
  • standard math Basic properties of blow-ups of the 3-prism graph.
    Defines the equality case construction.

pith-pipeline@v0.9.0 · 10156 in / 1175 out tokens · 102736 ms · 2026-05-08T17:34:12.391893+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

  1. [1]

    Bollobás and V

    B. Bollobás and V. Nikiforov. Books in graphs.European Journal of Combinatorics, 26(2):259–270, 2005

    work page 2005

  2. [2]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov. Books versus triangles at the extremal density. SIAM Journal on Discrete Mathematics, 34(1):385–398, 2020

    work page 2020

  3. [3]

    P. Erdős. On a theorem of Rademacher–Turán.Illinois Journal of Mathematics, 6(1):122–127, 1962

    work page 1962

  4. [4]

    G. H. Hardy, J. E. Littlewood, and G. Pólya.Inequalities. Cambridge University Press, 1952

    work page 1952

  5. [5]

    Khadžiivanov and V

    N. Khadžiivanov and V. Nikiforov. Solution of a problem of P. Erdős about the maximum number of triangles with a common edge in a graph.C. R. Acad. Bulgare Sci., 32(10):1315–1318, 1979

    work page 1979

  6. [6]

    W. Mantel. Problem 28.Wiskundige Opgaven, 10:60–61, 1907

    work page 1907

  7. [7]

    D. Mubayi. Books versus triangles.Journal of Graph Theory, 70(2):171–179, 2012. Email address:ckz22000259@mail.ustc.edu.cn Email address:jiema@ustc.edu.cn Email address: wth1115060377@mail.ustc.edu.cn 24

    work page 2012