{"id":"5aeccdce-25e6-4754-a857-72320d8e3226","arxiv_id":"2506.23794","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The maximum edge count of a triangle-free graph on n vertices that must contain a prescribed triangle-free P is bounded above by nα(P)/2 and below by a Shearer-type expression, yielding Θ(n² ln d/d) for constrained P.","lead":"A new note in extremal graph theory asks: if a triangle-free graph must contain a given smaller triangle-free graph P, how many edges can it have? The authors prove general upper and lower bounds and show the answer is Θ(n² ln d / d) for constrained graphs like random triangle-free graphs.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 1.4 rests on an unproved independence-number bound for the triangle-free process; the footnote 'personal communication with Peter Keevash' is not a substitute for a proof or citation, and the Θ(n² ln d/d) claim for ex_{G(i)} collapses if the bound fails.","rationale":"The reader's weakest assumption is exactly the step I would flag. I checked the central proof: Theorem 1.1(i) is the simple maximum-degree/independence argument; Theorem 1.1(ii) is a clean application of Shearer's theorem to B2[S′], with Claims 2.3–2.5 giving e(B1) ≤ N(S2, P), e(B2) ≤ e(P)(n−2), and B2 K3-free. I found no error there. The derivation of Corollary 1.2 from Theorem 1.1 and the constraints is also sound. The remaining risk lives in the advertised applications. The reader also noted a possible range mismatch in Corollary 1.3; I regard that as secondary and fixable. The substantive gap is the Corollary 1.4 independence-number bound, which is load-bearing for the upper-bound half of the Θ result and is supported only by a personal communication. Since the reader already conditioned the verdict on this missing support, my stress-test does not change the verdict: UNCHANGED, still conditional.","tokens_in":6833,"tokens_out":9931,"duration_ms":113385,"concrete_test":"Give a formal proof or exact citation for α(G(i)) = O(n ln(2i/n)/(2i/n)) for i ≤ c n^{3/2}. One concrete route: use the differential-equation method of [BK21] to upper-bound the expected number of independent sets of size k = C n ln d/d in G(i) and show it is o(1) for some constant C and every d in the stated range; this mirrors the standard proof for G(n,p). If the expectation is not o(1) at the endpoint d = Θ(√n), the asserted coupling cannot hold in the full range and the upper bound in Corollary 1.4 does not follow from the paper's reasoning.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing gap is in Corollary 1.4. To apply Corollary 1.2 to P = G(i) one needs α(G(i)) ≤ β1 n ln d/d and e(G(i))Δ(G(i)) ≤ (1/4−β2)n² for d = 2i/n and i ≤ c_{1.4}n^{3/2}. The maximum-degree half is cited to [BK21, Section 3.2]; the independence half is asserted as 'The same coupling argument can be repeated to show that this also holds for the independence number', with only footnote 2, 'Personal communication with Peter Keevash', as support. No proof is given and no reference is supplied. This matters because the upper bound ex_P(n, K3) ≤ nα(P)/2 from Theorem 1.1(i) is the only upper-bound mechanism used for the Θ statement; without the asserted α(G(i)) bound, the proof of Corollary 1.4 has no upper bound. Independence number is a global quantity and does not follow automatically from the local degree coupling: the triangle-free acceptance rule changes the distribution of nonedges inside large candidate independent sets, so a separate argument or a precise citation to a proved theorem is required. The main Theorem 1.1 and Corollary 1.2 are not affected, but the advertised triangle-free-process application is conditionally supported at best.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7164,"tokens_out":8608,"duration_ms":88235,"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":[{"comment":"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).","section":"§1, Corollary 1.3 and Eq. (1)"},{"comment":"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.","section":"§1, Corollary 1.4 and footnote 2"}],"minor_comments":[{"comment":"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.","section":"§1, Eq. (1)"},{"comment":"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))).","section":"§1, paragraph on triangle-free process"},{"comment":"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.","section":"§2, Claim 2.6"},{"comment":"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.","section":"§1, Corollary 1.2"},{"comment":"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.","section":"§3, concluding remarks"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is sound and the proof is elegant. The main concern is the two applications: Corollary 1.3 appears to exceed the cited range, and Corollary 1.4 rests on an unproved independence-number bound. Both are fixable if the authors have the missing arguments or can adjust the statements, so I recommend major revision rather than rejection. If the authors can include a full proof of the triangle-free process independence bound, the paper would be a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick read: the main result is real and worth attention. The function ex_P(n,K3) hasn't been systematically studied, and Theorem 1.1 gives a clean two-sided bound: the upper bound via α(P) is immediate, the lower bound via the auxiliary 3-graph and Shearer's theorem is the right tool. Corollary 1.2, which turns Theorem 1.1 into a Θ(n² ln d/d) statement for (β1,β2)-constrained P, is the useful takeaway. I checked the counting arguments for B1, B2, B3 and they hold; there's no circularity. The proof is internally consistent and the claims about the newness of the problem check out.\n\nThe soft spot is Corollary 1.4. The maximum-degree bound for the triangle-free process is properly cited to BK21, but the independence-number bound \"the same coupling argument can be repeated\" is backed only by footnote 2, \"Personal communication with Peter Keevash\". That is a load-bearing step: without α(G(i)) = O(α(G(n,p))), the upper bound in the Θ statement vanishes, since the only upper-bound mechanism in Theorem 1.1 involves α(P). Independence number is a global parameter and does not follow from the local degree coupling by a \"same argument\" phrase. Either a proof or a precise citation to a theorem that contains this bound is needed. This does not affect Theorem 1.1 or Corollary 1.2.\n\nOne note on the reader's report: the alleged range mismatch in Corollary 1.3 is not there. Bound (1) is stated for d up to c n^{1/4}√ln n, which contains the Corollary 1.3 range for large n, so that worry is minor.\n\nThe short discussion of non-triangle-free P in the concluding remarks is explicitly left to future work, so I don't count it as a gap.\n\nBottom line: the paper deserves a serious referee. Send it to review, and ask for the independence-number proof for the triangle-free process, or a real citation. If that fix lands, the paper is a nice contribution; if not, Corollary 1.4 should stay conditional.","headline":"Main theorem and Corollary 1.2 are solid; the triangle-free process application rests on an unproved independence bound.","tokens_in":7677,"tokens_out":3184,"would_cite":true,"duration_ms":30744,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C80","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Mantel's theorem","triangle-free graphs","extremal number with prescribed subgraph","Shearer's bound","independence number","random triangle-free graphs","triangle-free process","average degree"],"falsifier":"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.","tokens_in":6672,"feed_emoji":"🔺","tokens_out":14590,"duration_ms":148317,"temperature":0.7,"pith_summary":"Mantel's theorem says that among triangle-free graphs on $n$ vertices, the maximum number of edges is $\\lfloor n^2/4 \\rfloor$. This paper asks how that maximum drops when the graph must also contain a prescribed triangle-free subgraph $P$. The answer is a pair of bounds: the modified extremal number is at most $n\\alpha(P)/2$, and, as long as $e(P)+N(S_2,P)<\\lfloor n^2/4\\rfloor$, it is at least $(\\lfloor n^2/4\\rfloor-e(P)-N(S_2,P))\\,\\psi(\\gamma(P)d(P))$, where $S_2$ is the two-edge path and $\\psi$ is Shearer's decreasing function. For graphs $P$ with small independence number and no vertex of excessive degree, the two bounds agree up to constants and give $\\operatorname{ex}_P(n,K_3)=\\Theta(n^2\\ln d/d)$, which covers random triangle-free graphs and the triangle-free process in the stated density ranges.","feed_headline":"Forced to contain P, triangle-free graphs keep $\\Theta(n^2\\ln d/d)$ edges","feed_subtitle":"New two-sided bounds show exactly how adding a prescribed subgraph shrinks the largest triangle-free graph.","key_machinery":"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)$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Gives the extremal bound $\\lfloor n^2/4\\rfloor$ and the balanced complete bipartite graph that seeds the lower-bound construction.","marker":"[Man07]"},{"why":"Supplies the independence-number bound $\\psi(d)$ for triangle-free graphs, which is the engine of the lower bound in Theorem 1.1(ii).","marker":"[She83]"},{"why":"Provides the bound $\\alpha(T(n,d))\\leq 4n\\ln d/d$ needed to make the uniform random triangle-free model constrained.","marker":"[OPT01]"},{"why":"Founds the triangle-free process and its $\\Theta(n^{3/2}\\sqrt{\\ln n})$ running time, the model behind Corollary 1.4.","marker":"[Boh09]"},{"why":"Develops the triangle-free process further, giving structural estimates used to compare $G(i)$ with the binomial random graph.","marker":"[FPGM20]"},{"why":"Supplies the dynamic concentration and maximum-degree estimates for the triangle-free process used in Corollary 1.4.","marker":"[BK21]"},{"why":"Provides standard random-graph bounds on independence number and maximum degree used throughout the constrained-graph arguments.","marker":"[FK16]"}],"fun_headline_variants":["Sabotaging Mantel: forced subgraph trims triangle-free max edges","Mantel's bound under sabotage: forced P cuts edges to n^2 ln d/d","Prescribed subgraph P: triangle-free edge max drops to Θ(n^2 ln d/d)","Forcing any P shrinks triangle-free edge max to n^2 ln d/d"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sabotaging Mantel: forced subgraph trims triangle-free max edges","Mantel's bound under sabotage: forced P cuts edges to n^2 ln d/d","Prescribed subgraph P: triangle-free edge max drops to Θ(n^2 ln d/d)","Forcing any P shrinks triangle-free edge max to n^2 ln d/d"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00141,"raw_usage":{"total_tokens":5656,"prompt_tokens":864,"completion_tokens":4792,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":480,"completion_tokens_details":{"reasoning_tokens":4710}},"tokens_in":480,"tokens_out":4792,"duration_ms":34685,"temperature":1.0,"reasoning_tokens":4710,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:31:40.020727+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}