REVIEW 2 major objections 5 minor 13 references
Sabotage the Mantel Theorem
T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read A new theorem bounds the largest triangle-free graph forced to contain a given triangle-free subgraph, matching up to constants for random and process-generated subgraphs.
desk verdict Main theorem and Corollary 1.2 are solid; the triangle-free process application rests on an unproved independence bound. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The proof mechanism is the auxiliary 3-graph $H$ whose vertex set is the edge set of $K_n$ and whose hyperedges are triples of edges that form a triangle; a triangle-free graph is exactly an independent set in $H$. The paper classifies the obstacles to adding edges to $P$ as three sets: $B_1$ (edges that complete a triangle with two edges of $P$), $B_2$ (pairs of edges that complete a triangle with one edge of $P$), and $B_3$ (new triangles entirely outside $P$). The key quantitative facts are $e(B_1)\leq N(S_2,P)$, $e(B_2)\leq e(P)(n-2)$, and the proof that $B_2$ is triangle-free whenever $P$ is; these turn the task into a Shearer problem on the triangle-free graph $B_2$, whose average degree is at most $\gamma(P)d(P)$.
What would settle it
Run the triangle-free process up to $i\approx cn^{3/2}$ for a fixed $c$, estimate the largest subset of vertices containing no edge, and compare with $n\ln d/d$ for $d=2i/n$: if the ratio tends to infinity, Corollary 1.4 is false, while Theorem 1.1 could still be true. For the deterministic theorem, a small-$n$ exhaustive search over triangle-free $P$ with $e(P)+N(S_2,P)<\lfloor n^2/4\rfloor$ that finds an extremal value below the claimed Shearer lower bound would refute it.
Extended reading notes
Core claim
The central discovery is Theorem 1.1, a two-sided estimate for $\operatorname{ex}_P(n,K_3)$, the largest triangle-free graph containing $P$. The upper bound $e(G)\leq n\alpha(P)/2$ comes from the neighbourhood of a maximum-degree vertex, which must be independent in $P$. The lower bound comes from an auxiliary 3-uniform hypergraph whose vertices are the prospective edges of $G$: triangle-free graphs are independent sets there, and the requirement $P\subseteq G$ becomes the condition that the independent set contains $P$. Deleting $P$ and the pairs that would complete a triangle with $P$, then applying Shearer's independence bound inside a balanced complete bipartite edge set, gives the stated $\psi(\gamma(P)d(P))$ lower bound. For $(\beta_1,\beta_2)$-constrained $P$ the upper and lower bounds have the same order, $n^2\ln d/d$, and the paper verifies that the uniform random triangle-free model and the triangle-free process satisfy the constraints with high probability in the stated ranges.
Load-bearing premise
The deterministic theorem is unconditional, but the triangle-free process corollary depends on an unproved coupling, cited in the paper only as a personal communication, that the largest independent set in $G(i)$ is no larger in order than that of the binomial random graph with the same density; if that fails for some $i\leq cn^{3/2}$, the corollary does not follow from the paper's proof.
Editorial extensions
If this is right
- For any $(\beta_1,\beta_2)$-constrained triangle-free $P$ with average degree $d$, the paper proves $\operatorname{ex}_P(n,K_3)=\Theta(n^2\ln d/d)$, so both the growth rate and the constant-factor range are determined.
- With high probability the uniform random triangle-free graph $T(n,d)$ is constrained for $d\in[4,cn^{1/4}]$, so $\operatorname{ex}_{T(n,d)}(n,K_3)=\Theta(n^2\ln d/d)$ in that range.
- With high probability the triangle-free process $G(i)$ is constrained for $i\in[n,cn^{3/2}]$, giving $\operatorname{ex}_{G(i)}(n,K_3)=\Theta(n^2\ln d/d)$ there, conditional on the stated independence-number coupling.
- The upper bound $n\alpha(P)/2$ is universal, so for any specific $P$ the lower bound is tight up to the factor $\alpha(P)d/\ln d$ in the constrained regime.
- In the very sparse and very dense regions discussed in the paper, the modified extremal number is $(1/4-o(1))n^2$ with high probability, while the middle range is left open.
Reading between the lines
- The unproved independence-number coupling for the triangle-free process is the single point to check: a proof of that coupling would complete the process application, and a counterexample at $i\approx cn^{3/2}$ would remove that corollary without damaging the deterministic theorem.
- The auxiliary-hypergraph encoding is likely reusable: sabotage versions of other extremal theorems can be attempted by defining $\mathcal{F}$-freeness as independence in a hypergraph on the edge set and locating the analogues of $B_1$ and $B_2$.
- The worst-case quantity $\operatorname{ex}_m(n,K_3)$ appears to interpolate between stars, which are worst near the saturation threshold, and disjoint 5-cycles at smaller $m$; locating the transition is a natural next step.
- The paper states that its corollary should survive when $P$ is not triangle-free, provided copies of each forbidden graph are counted rather than forbidden outright; verifying that would broaden the random-graph applications.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the extremal function ex_P(n,K_3), defined as the maximum number of edges in a triangle-free graph G on n vertices that contains a prescribed triangle-free graph P on the same vertex set. The main result, Theorem 1.1, gives an upper bound ex_P(n,K_3) ≤ n α(P)/2 and a lower bound of the form (⌊n^2/4⌋ − e(P) − N(S_2,P)) · ψ(γ(P)d(P)), obtained by constructing an auxiliary 3-graph, deleting forbidden pairs, and applying Shearer's independence bound to a triangle-free auxiliary graph. A corollary states that for graphs P with small independence number and small edge-degree product, ex_P(n,K_3) = Θ(n^2 log d/d). The paper then applies this corollary to two random triangle-free models: the uniform model T(n,d) (Corollary 1.3) and the triangle-free process G(i) (Corollary 1.4). The concluding remarks discuss open ranges and a general F-free extension.
Significance. If the main theorem and its corollaries are correct, the paper provides a clean and broadly applicable reduction of a natural Mantel-type problem with a prescribed subgraph to standard graph parameters (independence number, degree product). The proof of Theorem 1.1 is short, self-contained, and internally sound; the auxiliary 3-graph construction and the use of Shearer's theorem are elegant. The corollaries give interesting asymptotic statements for random triangle-free graphs. However, two advertised applications contain load-bearing gaps: the stated range in Corollary 1.3 appears wider than the cited independence bound allows, and Corollary 1.4 relies on an independence-number bound for the triangle-free process that is only supported by a personal communication. These issues do not affect the central theorem itself but do affect the paper's main applications.
major comments (2)
- [§1, Corollary 1.3 and Eq. (1)] Corollary 1.3 concludes w.h.p. that ex_{T(n,d)}(n,K_3) = Θ(n^2 ln d/d) for every d ∈ [4, c_{1.3} n^{1/4}], but the displayed independence bound (1), cited to [OPT01, Lemma 3], is stated for the narrower range d ∈ [4, c n^{1/4}/√(ln n)]. The upper-bound mechanism in Theorem 1.1(i) is α(P) ≤ 4n ln d/d, so the Θ statement requires this independence bound to hold for all d up to c_{1.3} n^{1/4}. As written, the corollary extends the range by a factor √(ln n) without proof or citation. Please either prove the extended bound, cite a theorem that implies it, or restrict Corollary 1.3 to the range covered by (1).
- [§1, Corollary 1.4 and footnote 2] Corollary 1.4 needs both Δ(G(i)) = O(Δ(G(n,p))) and α(G(i)) = O(α(G(n,p))) for p = i/ choose(n,2) and i ≤ c n^{3/2}. The maximum-degree statement is cited to [BK21, Section 3.2], but the independence-number statement is asserted as 'The same coupling argument can be repeated to show that this also holds for the independence number', supported only by footnote 2, 'Personal communication with Peter Keevash'. This is a load-bearing point: α is a global quantity and does not follow automatically from the local coupling used for degrees, and without the α bound the upper bound in Theorem 1.1(i) does not yield the Θ(n^2 ln d/d) conclusion. Please supply a proof or a precise citation to a proved theorem; otherwise Corollary 1.4 should be stated conditionally on this bound or removed from the main results.
minor comments (5)
- [§1, Eq. (1)] The typesetting of the range in (1), 'd ∈ [4, cn1/4√ln n]', is ambiguous; it should be written as c n^{1/4}/√(ln n) (or whatever is intended) so that the range in Corollary 1.3 can be compared correctly.
- [§1, paragraph on triangle-free process] The displayed line 'Δ(G(i)) = O (Δ(G(n, p)) and α(G(i)) = O (α(G(n, p))' is missing closing parentheses; it should read O(Δ(G(n,p))) and O(α(G(n,p))).
- [§2, Claim 2.6] The letter d is used both for the average degree of P and for the average degree of the auxiliary graph B_2[S']; this is slightly confusing and could be disambiguated.
- [§1, Corollary 1.2] The definition of (β1,β2)-constrained implicitly requires d(P)>1; it would be helpful to state this explicitly in the definition rather than in the following sentence.
- [§3, concluding remarks] In the sentence 'the function ex_m(n,F) reduces to sat(n,F)', the role of sat(n,F) is clear, but the connection to Erdős–Hajnal–Moon would benefit from a brief explanation of why m ≥ sat(n,F) makes the minimization trivial.
Circularity Check
No circular reasoning: the lower bound is derived from Shearer's external theorem and direct counting, and no parameter is fitted to force the conclusion.
full rationale
Theorem 1.1(ii) constructs an auxiliary 3-graph H and an independent set I inside B2[S′]. The bound |I| ≥ (⌊n²/4⌋ − e(P) − N(S2,P))·ψ(γ(P)d(P)) is obtained by applying Shearer's classical independence bound (Theorem 2.1) to the triangle-free graph B2[S′]. The quantity γ(P)d(P) is not a fitted parameter: it arises from the explicit upper bound d ≤ 2e(P)(n−2)/(⌊n²/4⌋ − e(P) − N(S2,P)) = γ(P)d(P), and ψ is the fixed Shearer function. No equation in the paper defines the target ex_P(n,K3) in terms of the claimed lower bound, and no parameter is tuned to match the result. The upper bound ex_P(n,K3) ≤ nα(P)/2 is an independent elementary observation (neighborhood of a max-degree vertex is an independent set in P). Corollaries 1.3 and 1.4 combine these bounds with external random-graph estimates; the triangle-free process independence-number bound in Corollary 1.4 is asserted via 'Personal communication with Peter Keevash' rather than proved or cited, but this is a missing justification / correctness risk, not circularity: it does not make the conclusion identical to an input by construction. The core derivation for arbitrary (β1,β2)-constrained graphs is self-contained apart from Shearer's theorem, which is an external benchmark.
Assumptions & free parameters
assumptions (4)
- standard math Shearer's theorem (Theorem 2.1): a triangle-free graph on n vertices with average degree d has independence number at least n ψ(d).
- standard math Mantel's theorem: the maximum edges in a triangle-free graph on n vertices is ⌊n²/4⌋, and the balanced bipartite graph is unique extremal.
- domain assumption [OPT01] Lemma 3 and Lemma 4: with high probability α(T(n,d)) ≤ 4n ln d/d for d ∈ [4, c n^{1/4}/√ln n] and Δ(T(n,d)) ≤ C d³ for d ∈ [4, c' n^{1/2}].
- domain assumption For the triangle-free process, α(G(i)) = O(α(G(n,p))) with p = i/C(n,2) for i ≤ c n^{3/2}, communicated personally by Peter Keevash.
Cite this review
Pith. "Pith review of Sabotage the Mantel Theorem." pith.science (2026). https://pith.science/paper/ONYWP6X6
@misc{pith2026250623794,
author = {Pith},
title = {Pith review of: Sabotage the Mantel Theorem},
year = {2026},
howpublished = {\url{https://pith.science/paper/ONYWP6X6}},
note = {Machine review of arXiv:2506.23794}
}
abstract
One of the earliest results in extremal graph theory, Mantel's theorem, states that the maximum number of edges in a triangle-free graph $G$ on $n$ vertices is $\lfloor n^2/4 \rfloor$. We investigate how this extremal bound is affected when $G$ is additionally required to contain a prescribed graph $\mathbb{P}$ as a subgraph. We establish general upper and lower bounds for this problem, which are tight in the exponent for random triangle-free graphs and graphs generated by the triangle-free process, when the size of $\mathbb{P}$ lies within certain ranges.
Reference graph
Works this paper leans on
-
[1]
Paul Balister, B \'e la Bollob \'a s, Oliver Riordan, and Richard H. Schelp. Graphs with large maximum degree containing no odd cycles of a given length. J. Combin. Theory Ser. B , 87(2):366--373, 2003
work page 2003
-
[2]
Dynamic concentration of the triangle-free process
Tom Bohman and Peter Keevash. Dynamic concentration of the triangle-free process. Random Structures Algorithms , 58(2):221--293, 2021
work page 2021
-
[3]
Tom Bohman. The triangle-free process. Adv. Math. , 221(5):1653--1677, 2009
work page 2009
-
[4]
Nannan Chen, Xizhi Liu, Lin Sun, and Guanghui Wang. Tiling H in dense graphs. arXiv preprint arXiv:2501.11450 , 2025
work page Pith review arXiv 2025
-
[5]
P. Erd o s, A. Hajnal, and J. W. Moon. A problem in graph theory. Amer. Math. Monthly , 71:1107--1110, 1964
work page 1964
-
[6]
Alan Frieze and Micha Karo \'n ski. Introduction to random graphs . Cambridge University Press, Cambridge, 2016
work page 2016
-
[7]
The triangle-free process and the R amsey number R(3,k)
Gonzalo Fiz Pontiveros, Simon Griffiths, and Robert Morris. The triangle-free process and the R amsey number R(3,k) . Mem. Amer. Math. Soc. , 263(1274):v+125, 2020
work page 2020
-
[8]
A. M. Frieze. On the independence number of random graphs. Discrete Math. , 81(2):171--175, 1990
work page 1990
Show all 13 references
-
[9]
On the evolution of structure in triangle-free graphs
Matthew Jenssen, Will Perkins, and Aditya Potukuchi. On the evolution of structure in triangle-free graphs. arXiv preprint arXiv:2312.09202 , 2023
2023 arXiv
-
[10]
Vraagstuk XXVIII
Willem Mantel. Vraagstuk XXVIII . Wiskundige Opgaven , 10(2):60--61, 1907
1907
-
[11]
u rgen Pr \
Deryk Osthus, Hans J \"u rgen Pr \"o mel, and Anusch Taraz. Almost all graphs with high girth and suitable density have high chromatic number. J. Graph Theory , 37(4):220--226, 2001
2001
-
[12]
u rgen Pr \
Deryk Osthus, Hans J \"u rgen Pr \"o mel, and Anusch Taraz. For which densities are random triangle-free graphs almost surely bipartite? Combinatorica , 23(1):105--150, 2003
2003
-
[13]
James B. Shearer. A note on the independence number of triangle-free graphs. Discrete Math. , 46(1):83--87, 1983
1983
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.