{"id":"5d79c962-554f-4b7d-b2b7-c74cebc7b347","arxiv_id":"2411.19773","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper gives better minimum-degree thresholds for forcing complete tripartite subgraphs and conditionally solves the Bollobas-Erdos-Szemeredi octahedron conjecture.","lead":"The paper improves the minimum degree that forces an octahedral K3(2) subgraph in a balanced tripartite graph, from around n+n^(11/12) down to n+2n^(5/6). It also proves a 1975 conjecture about a square-root threshold, but only when every vertex already has many neighbors in the other two parts.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.5 proof's claimed δ(G') bound is arithmetically false: with α=(35c)^{-2}, the deletion error 24(35c)^4√n dwarfs the assumed excess 305c^4√n.","rationale":"The reader's weakest assumption was the partial-degree floor in Theorem 1.5, but the actual load-bearing problem is a concrete arithmetic error inside the proof of that theorem. The proof defines α=(35c)^{-2}, then claims that after removing the exceptional sets S_i^± the minimum degree of G' is at least n' + 28c^2√n'. The loss from deletions is 24α^{-2} n^{1/2} = 24(35c)^4 n^{1/2}, which for c≥58 is roughly 118,000 times larger than the assumed excess 305c^4 n^{1/2}. Thus the inequality fails, and the subsequent application of Lemma 3.3 is not justified. Theorem 1.4 and Proposition 1.6, by contrast, appear sound; the error is localized to the main conditional theorem. Since the theorem was already superseded by Di Braccio and Illingworth, a correction of the constant or a proper restatement of Theorem 1.5 would resolve the issue, so conditional acceptance is appropriate.","tokens_in":15542,"tokens_out":30028,"duration_ms":208778,"concrete_test":"Recompute the key inequality in the proof of Theorem 1.5 with the stated α=(35c)^{-2}. For c=58, 24(35c)^4√n ≈ 4.08×10^14√n while 305c^4√n ≈ 3.45×10^9√n, so the asserted lower bound on δ(G') is false for all sufficiently large n. If the intended definition was α=(35c)^{-1}, check whether the subsequent applications of Lemmas 3.2 and 3.3 then go through; otherwise the constant in Theorem 1.5 must be revised so that the error term 24α^{-2} is dominated by the assumed excess.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 1.5, α is set to (35c)^{-2}. The sets S_i^+ and S_i^- each have size 4α^{-2} n^{1/2}, so deleting them from each part costs up to 24α^{-2} n^{1/2} = 24(35c)^4 n^{1/2}. The paper claims δ(G') ≥ δ(G) − 24α^{-2} n^{1/2} ≥ n + 305c^4 n^{1/2} − 24(35c)^4 n^{1/2} ≥ n' + 28c^2 n'^{1/2}. But 24·35^4 = 36,015,000, so the subtracted term exceeds the assumed excess 305c^4 n^{1/2} by roughly five orders of magnitude. For c ≥ 58, the displayed lower bound becomes n − O(c^4 n^{1/2}), while n' = n − 8(35c)^4 n^{1/2}; hence δ(G') is not guaranteed to be at least n' + 28c^2√n', so the reduction to Lemma 3.3 fails. This is an internal numerical inconsistency, not merely a strong extra hypothesis: as written, Theorem 1.5 is unproved.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies balanced tripartite graphs G=G3(n) and the minimum degree that forces a complete tripartite subgraph K3(s), with special attention to the octahedral graph K3(2). Theorem 1.4 gives a double-counting proof that δ(G) ≥ n + C n^{1-1/(s(s+1))} with C=2(s-1)^{1/(s+1)} forces K3(s), improving a bound of Bhalkikar and Zhao; the particular case s=2 yields δ(G) ≥ n + 2 n^{5/6}. Theorem 1.5 claims that, under an additional strong hypothesis on the minimum partial degree, δ(G) ≥ n + 305 c^4 n^{1/2} forces K3(2), which would qualitatively confirm the Bollobás–Erdős–Szemerédi conjecture in that restricted setting. Proposition 1.6 gives a lower bound on the minimum number of triangles in such graphs by n^2(3t-n)/2, with an extremal construction when n is even and t≥n/2. Section 4 supplies explicit K3(2)-free constructions with minimum degree n+(1-o(1))n^{1/2} and a gluing operation producing further examples. A note added in proof records that Problem 1.2 was subsequently settled by Di Braccio and Illingworth.","tokens_in":15819,"tokens_out":20346,"duration_ms":166642,"significance":"The double-counting proof of Theorem 1.4 is clear, self-contained, and its final comparison with the Zarankiewicz bound checks out; this is a genuine technical improvement over the previous bound, although the note added in proof indicates that the problem has since been settled with a stronger n+K n^{1-1/s} threshold. Proposition 1.6 is a nice, clean result giving an exact value of f(n,t) for even n and t≥n/2, and the constructions in Section 4 are explicit and verifiable. The main concern is Theorem 1.5: as written, its proof contains a numerical error that invalidates the reduction to Lemma 3.3, so the paper's headline conditional confirmation of the Bollobás–Erdős–Szemerédi conjecture is not established. If that theorem is repaired or removed and the paper is reframed around the results that remain new, the remaining content is publishable, but the current version cannot be accepted as it stands.","major_comments":[{"comment":"The displayed chain after (3.2) is arithmetically false. With α=(35c)^{-2}, the sets S_i^+ and S_i^- each have size 4α^{-2}√n, so n'=n-8(35c)^4√n and the deletion loss is 24α^{-2}√n = 24(35c)^4√n = 36,015,000 c^4√n. The paper claims δ(G') ≥ n+305c^4√n - 24(35c)^4√n ≥ n'+28c^2√n', but the middle expression is n-(36,015,000-305)c^4√n, which is far below n'=n-12,005,000c^4√n; indeed even δ(G')≥n' is not guaranteed. Consequently Lemma 3.3 cannot be applied and the final contradiction is unsupported. This is not a typo in a single constant: the later requirement T_{G'}(uv)≤n'/(30c)^2 forces α≤1/(900c^2), hence α^{-2}≥8.1×10^5 c^4, making the deletion loss at least 24·8.1×10^5 c^4√n, which already dwarfs the assumed excess 305c^4√n. The proof of Theorem 1.5 is therefore invalid as written; either the constant 305 must be replaced by a much larger one (of order at least 10^7–10^8 c^4 for this strategy) or the argument must be substantially reworked.","section":"Section 3, proof of Theorem 1.5"},{"comment":"The note added in proof states that Problem 1.2 was settled by Di Braccio and Illingworth with a bound n+K n^{1-1/s} for K3(s). This supersedes Theorem 1.4: for s=2 it gives the conjectured n+O(√n) threshold, and for general s the exponent 1-1/s is smaller than 1-1/(s(s+1)). Since Theorems 1.4 and 1.5 are the paper's advertised main results, the manuscript should explicitly say in the introduction which contributions remain new after [5]—primarily Proposition 1.6 and the Section 4 constructions—and should not present an improved bound for a problem that has already been solved. This is a matter of framing and significance, not of mathematical correctness, but it is load-bearing for the paper's contribution claim.","section":"Note added in proof and Introduction"}],"minor_comments":[{"comment":"The symbol T(xy) is used both for the number of triangles containing edge xy and, later in the same proof, T(z1,...,zs) is defined as a set of edges; this overloading is confusing and should be renamed, for example E(z1,...,zs).","section":"Section 2, proof of Theorem 1.4"},{"comment":"The constants 13√α and 5α in the estimates for |Wi| and |Uj| are not derived in the text; a short explanation of how they follow from Claim 3.5 (v) and (vii) would improve readability.","section":"Section 3, around (3.6)"},{"comment":"The line 'B1 = B2 ∪ B3' is informal, since B2 and B3 are subsets of different vertex classes; the intended meaning is that B1 is partitioned into two sets of size t each, and this should be said explicitly.","section":"Section 4, Construction 4.1"},{"comment":"The sentence 'Bollobás, Erdős, and Szemerédi conjectured that n+cn^{1/2} suffices and there are many K3(2)-free tripartite graphs...' could be misread as saying the existence of such graphs is part of the conjecture; a semicolon or separate sentence would remove the ambiguity.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The arithmetic issue in Theorem 1.5 is serious: the stated proof cannot be repaired by a small change in a constant, because the choice of α is forced by the triangle-count requirement and the deletion loss then dominates the assumed degree excess. At the same time, the note added in proof means the paper's two main theorems have been overtaken by [5]. If the authors can either prove a substantially weaker threshold in Theorem 1.5 or remove it and reframe the paper around Proposition 1.6 and Section 4, the remaining mathematics is sound; otherwise I would not recommend publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Stress-test note is right: Theorem 1.5's proof has a false inequality. With α=(35c)^{-2}, the deleted sets S_i^± have size 4(35c)^4 n^{1/2}, so the total deletion cost is 24(35c)^4 n^{1/2} ≈ 3.6×10^7 c^4 n^{1/2}. The assumed excess over n is only 305c^4 n^{1/2}. The displayed lower bound δ(G′) ≥ n + 305c^4 n^{1/2} − 24(35c)^4 n^{1/2} is negative for moderate c, and certainly does not imply n′ + 28c²√n′ since n′ = n − 8(35c)^4√n. This is not a typo; it breaks the reduction to Lemma 3.3. As written, Theorem 1.5 is unproved.\n\nWhat is good: Theorem 1.4 genuinely improves the threshold for K3(s) from n+O(n^{1−1/(3s²)}) to n+O(n^{1−1/(s(s+1))}) by a clean double-counting twist (counting through T1). The arithmetic in that proof checks out. Proposition 1.6 is a simple, exact triangle-count bound. The Section 4 constructions are new and yield many K3(2)-free graphs with minimum degree n+(1−o(1))√n.\n\nThe note added in proof discloses that Di Braccio and Illingworth later settled Problem 1.2, so the significance of Theorem 1.5 is mainly as a conditional result. The citation pattern is fine; the self-citations are prior results the paper improves. No invented entities, no circularity.\n\nVerdict: send it to a serious referee, but the referee should be told to check the constants in Theorem 1.5. The paper deserves review because of Theorem 1.4 and the constructions, but the flagship theorem needs a fix. I would not cite the paper until that is resolved.","headline":"The stress-test note is correct: Theorem 1.5's proof has a numerical contradiction that breaks the argument, but the paper still contains a solid Theorem 1.4 and useful constructions.","tokens_in":16419,"tokens_out":3438,"would_cite":false,"duration_ms":27007,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"A small degree surplus over n forces complete tripartite subgraphs, including the octahedral graph, and the conjectured square-root threshold holds under a partial-degree condition.","keywords":["octahedral graph","complete tripartite subgraphs","minimum degree","Zarankiewicz bound","balanced tripartite graphs","C6-blow-up","extremal graph theory","triangle counting"],"falsifier":"A concrete way to test Theorem 1.4 would be to search for an infinite family of balanced tripartite graphs with $\\delta(G)\\ge n+2n^{5/6}$ and no $K_3(2)$; the theorem predicts no such family exists for large $n$. For the conditional theorem, one could try to build a $K_3(2)$-free graph satisfying $\\delta(G)\\ge n+305c^4\\sqrt n$ and partial degrees above $(1/5+7/c)n$; the theorem predicts this is impossible, and the proof's $C_6$-blow-up lemmas identify exactly where such a graph would have to break the structure.","tokens_in":15333,"feed_emoji":"🔺","tokens_out":15968,"duration_ms":127625,"temperature":0.7,"pith_summary":"The paper studies a 1975 extremal-graph problem: how large must the minimum degree of a balanced tripartite graph with $n$ vertices in each part be to force a copy of $K_3(2)$, the octahedral graph. Its first theorem shows that $\\delta(G) \\ge n + 2n^{5/6}$ suffices, improving the earlier $n + (1+o(1))n^{11/12}$ bound and extending the argument to $K_3(s)$ with surplus $2(s-1)^{1/(s+1)}n^{1-1/(s(s+1))}$. Its second theorem confirms the original square-root conjecture under an extra condition: if every vertex also has at least $(1/5+7/c)n$ neighbours in each of the other two parts, then $\\delta(G) \\ge n + 305c^4\\sqrt n$ forces a $K_3(2)$. The paper also builds $K_3(2)$-free tripartite graphs with minimum degree $n + (1-o(1))\\sqrt n$, so the square-root order of the surplus cannot be lowered. A note added in proof records that the unconditional conjecture has since been settled elsewhere.","feed_headline":"Minimum degree n + 2n^{5/6} forces an octahedral subgraph","feed_subtitle":"The 1975 conjecture holds under a partial-degree floor; otherwise the bound improves from n^{11/12} to n^{5/6}.","key_machinery":"The counting engine is the triangle count $T(xy)$ of an edge $xy$, together with the identity $d^+(y)+d^-(y)\\ge n+t$ that follows from the minimum-degree condition. The proof of Theorem 1.4 double-counts triangles through a $t$-set $T_1$ and, for each $x\\in T_1$, a $t$-set $T_x$ of its backward neighbours, applies convexity to pass from average triangle counts to many $s$-tuples, and then invokes the standard extremal bound on $K_{s,s}$-free bipartite graphs (the Zarankiewicz bound) to force a complete $K_{s,s}$; together with the chosen $s$ vertices this is $K_3(s)$. The square-root result is carried by a structural lemma: under $\\delta\\ge n$ and a positive linear one-sided minimum $\\delta^+\\ge 2\\varepsilon n$, a $K_3(2)$-free graph must be nearly a blow-up of a six-cycle, with six parts $W_1,\\ldots,W_6$ of size about $\\delta^+(G)$ that are cyclically almost complete. A second structural lemma shows that two such six-cycle blow-ups, one from the forward orientation and one from the backward orientation, cannot coexist without creating a $K_3(2)$.","core_discovery":"The central claim is that a small surplus over $n$ in the minimum degree controls complete tripartite subgraphs. Theorem 1.4 states that for every $s\\ge 2$ and sufficiently large $n$, every balanced tripartite graph $G_3(n)$ with $\\delta(G)\\ge n + 2(s-1)^{1/(s+1)}n^{1-1/(s(s+1))}$ contains $K_3(s)$; the $s=2$ case is the octahedron guarantee $\\delta(G)\\ge n+2n^{5/6}$. Theorem 1.5 states that with minimum partial degree at least $(1/5+7/c)n$, the weaker surplus $\\delta(G)\\ge n+305c^4\\sqrt n$ still forces $K_3(2)$, matching the conjectured square-root form under this extra hypothesis. The proof actually establishes a slightly stronger inequality involving the one-sided minima $\\delta^+(G)$ and $\\delta^-(G)$, and the $K_3(2)$-free graphs admissible to the argument are shown to be nearly a blow-up of a six-cycle.","pith_inferences":["The six-cycle blow-up description suggests that the full conjecture could be approached by proving the remaining case in which both one-sided minima $\\delta^+(G)$ and $\\delta^-(G)$ are $o(n)$; the paper's closing remarks leave this case open.","The large constant $305c^4$ in the conditional theorem is far from the order of the extremal examples at $n+(1-o(1))\\sqrt n$, so the sharp constant in front of $\\sqrt n$ is a natural target; one testable avenue is to run the structural lemmas with smaller error parameters in place of $c^{-1}n$.","The triangle lower bound $f(n,t)\\ge n^2(3t-n)/2$ may be reusable as a template for counting octahedra rather than triangles: a similar complement-counting identity could convert a surplus over $n+\\sqrt n$ directly into a lower bound on the number of $K_3(2)$ copies, which would give an independent route to the conjecture."],"forward_implications":["For $s=2$, every balanced tripartite graph with minimum degree at least $n+2n^{5/6}$ contains an octahedral subgraph, improving the previous $n+(1+o(1))n^{11/12}$ threshold.","For every fixed $s$, a surplus of order $n^{1-1/(s(s+1))}$ forces $K_3(s)$; in particular, the surplus is sublinear for every $s$.","Under the partial-degree floor $(1/5+7/c)n$, the conjectured square-root minimum degree $n+305c^4\\sqrt n$ forces $K_3(2)$, confirming the conjecture in this restricted setting.","The new constructions produce many $K_3(2)$-free tripartite graphs with minimum degree $n+(1-o(1))\\sqrt n$, so the square-root surplus in the conjecture cannot be replaced by anything smaller in order of magnitude.","A note added in proof records that the unconditional form of the problem has since been settled; the present results stand as stronger bounds before that settlement and as a structural proof of the conditional form."],"supporting_citations":[{"why":"Poses the octahedral minimum-degree problem, conjectures the square-root threshold, and supplies the construction method adapted in Section 4.","marker":"[4]"},{"why":"Corrected an error in the earlier approach and established the previous bound $n+(1+o(1))n^{11/12}$, which Theorem 1.4 improves.","marker":"[2]"},{"why":"Supplies the Zarankiewicz bound on $K_{s,s}$-free bipartite graphs that drives the double-counting in Theorem 1.4 and Lemma 3.1.","marker":"[10]"}],"fun_headline_variants":["Degree n+2n^(5/6) forces octahedral subgraph","Octahedron forced by degree n+2n^(5/6)","n+2n^(5/6) minimum degree guarantees K3(2)","Conjecture on octahedral subgraph holds with partial degree floor","Improved surplus n^(5/6) yields K3(2) in tripartite graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The square-root theorem assumes, in addition to the degree condition, that every vertex is adjacent to at least about one-fifth of the vertices in each of the other two classes; without this partial-degree floor, the six-cycle blow-up structure and the inequalities that drive the proof are not available.","fun_headline_variants_meta":{"raw":{"variants":["Degree n+2n^(5/6) forces octahedral subgraph","Octahedron forced by degree n+2n^(5/6)","n+2n^(5/6) minimum degree guarantees K3(2)","Conjecture on octahedral subgraph holds with partial degree floor","Improved surplus n^(5/6) yields K3(2) in tripartite graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001277,"raw_usage":{"total_tokens":5248,"prompt_tokens":995,"completion_tokens":4253,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":611,"completion_tokens_details":{"reasoning_tokens":4160}},"tokens_in":611,"tokens_out":4253,"duration_ms":27671,"temperature":1.0,"reasoning_tokens":4160,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:49:48.518858+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete way to test Theorem 1.4 would be to search for an infinite family of balanced tripartite graphs with $\\delta(G)\\ge n+2n^{5/6}$ and no $K_3(2)$; the theorem predicts no such family exists for large $n$. For the conditional theorem, one could try to build a $K_3(2)$-free graph satisfying $\\delta(G)\\ge n+305c^4\\sqrt n$ and partial degrees above $(1/5+7/c)n$; the theorem predicts this is impossible, and the proof's $C_6$-blow-up lemmas identify exactly where such a graph would have to break the structure.","supporting_citations":[{"cited_title":"Bollob´ as, P","cited_arxiv_id":null,"evidence_quote":"Poses the octahedral minimum-degree problem, conjectures the square-root threshold, and supplies the construction method adapted in Section 4."},{"cited_title":"Bhalkikar and Y","cited_arxiv_id":null,"evidence_quote":"Corrected an error in the earlier approach and established the previous bound $n+(1+o(1))n^{11/12}$, which Theorem 1.4 improves."},{"cited_title":"K˝ ov´ ari, V","cited_arxiv_id":null,"evidence_quote":"Supplies the Zarankiewicz bound on $K_{s,s}$-free bipartite graphs that drives the double-counting in Theorem 1.4 and Lemma 3.1."}],"review_version":1}