{"id":"26758c8c-70ed-4909-b1c6-24d7594fba64","arxiv_id":"2505.05264","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper claims ex(Q_n, S_{n-1,n-1}) equals 2^{n-3}(4n-3) for every n at least 3.","lead":"A new preprint claims the exact maximum number of edges in a hypercube that avoids a balanced double-star tree, giving 2^{n-3}(4n-3) for dimension n. The claimed value is plausible, but the upper-bound proof is only sketched, so the exact result is not yet established.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Upper bound not established: Subclaim 1 in Claim 2.3 asserts the full induction step but its R1/R2/R3 partition argument is unsupported, so Theorem 1.1 rests on an unproved assertion.","rationale":"The reader's weakest-assumption identification matches my reading: the lower-bound construction is plausible, but the upper bound is the hard part, and Claim 2.3 does not supply a proof of it. Subclaim 1 is not a lemma with a verifiable derivation; it is a restatement of the inductive goal with a partition asserted rather than argued. The absence of any counting involving r, the undefined role of the right copy, and the unsupported claim that an added edge forces adjacent degree-(n+1) vertices mean the manuscript does not establish the theorem. This is an internal proof gap, not a disagreement with an external consensus. The proposed computational check on Q_4 would decide whether the claimed numerical value is at least correct for the first inductive step; if the minimum deleted-edge count were 5 or less, the theorem would be outright false, while even a value of 6 would not repair the missing partition argument. I therefore keep the reader's REJECT verdict unchanged.","tokens_in":6227,"tokens_out":25564,"duration_ms":254879,"concrete_test":"Test the n=4 instance exactly. In Q_n a subgraph is S_{n-1,n-1}-free iff no edge joins two vertices of degree n, so the problem is equivalent to choosing a set F of deleted edges such that the vertices not incident to F form an independent set; the claimed value for n=4 says the minimum such |F| is 3*2^{4-3}=6. Solve this minimum-edge-dominating-set problem on Q_4 by exhaustive search or integer programming over the 32 edges. If the minimum is at most 5, then a 27-edge S_{3,3}-free subgraph exists and Theorem 1.1 is false. If the minimum is 6, the claimed value survives the first inductive step, but the R1/R2/R3 assertion in Subclaim 1 must still be independently derived from actual deletion patterns before the proof can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim depends on the upper bound in Claim 2.3, and the whole of that bound is delegated to Subclaim 1. When intercube edges are deleted, Subclaim 1 is essentially restating what must be proved: it asserts that any edge-deleted subgraph of Q_{n+1} with more than 2^{n-2}(4(n+1)-3) edges contains S_{n,n}, for an arbitrary pattern of deletions in e[Q_n,Q_n]. The proof then introduces a partition R1,R2,R3 and asserts (i) that an additional edge can only be added to R2, and (ii) that however it is added, two adjacent degree-(n+1) vertices in R2 become adjacent, forming S_{n,n}. Neither assertion is derived. No definition of the partition in terms of the actual deletion set is given, the parameter r is never used quantitatively, and the right copy of Q_n is not analysed. The induction hypothesis only bounds S_{n-1,n-1}-free subgraphs of a copy; once intercube edges are deleted, a vertex of degree n inside a copy need not have degree n+1 in Q_{n+1}, so the no-deletion extension argument does not transfer. The phrase 'regardless of how edges are removed' is exactly the statement needing proof. Unless Subclaim 1 is supplied with a real proof, Theorem 1.1 is not established. Secondary: Claim 2.1's transformation also needs a clearer argument that the minimum degree increases when several minimum-degree vertices exist, but the decisive gap is in Claim 2.3.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Turán number ex(Q_n, S_{n-1,n-1}) of the balanced double star in the n-dimensional hypercube and claims the exact value 2^{n-3}(4n-3) for all n≥3, with small values for n=1,2. The lower bound is constructed inductively by combining two extremal graphs in the two copies of Q_n inside Q_{n+1}. The upper bound is attempted by induction: the base case n=3 is analyzed by a degree-sum argument, and the induction step is delegated to 'Subclaim 1,' which asserts that any subgraph of Q_{n+1} with more than 2^{n-2}(4(n+1)-3) edges must contain S_{n,n} regardless of how intercube edges are deleted. The paper concludes Theorem 1.1 by combining the lower-bound construction, an upper-bound claim, and a preliminary minimum-degree transformation.","tokens_in":6624,"tokens_out":14820,"duration_ms":129067,"significance":"If the claimed value were established, this would be a clean exact result in the relatively sparse literature on Turán numbers of trees in hypercubes, complementing existing work on even cycles. The lower-bound construction is a genuine contribution and, subject to verification of the base case, appears plausible. However, the upper-bound proof is not a proof: the key subclaim is asserted rather than derived, so the main theorem is currently unsupported. The paper does not include machine-checked proofs or reproducible code, and the figures essential to the lower-bound base case are not included in the text.","major_comments":[{"comment":"Subclaim 1 is the entire induction step for the upper bound, yet its proof is a qualitative sketch: the partition of the left copy into R1/R2/R3 is not defined in terms of the actual deletion set, and the two crucial assertions—that an additional edge can only be added to R2 and that this forces two adjacent vertices of degree n+1 in R2—are stated without proof or counting. No inequality involving the deletion parameter r is given, and the right copy is not analyzed. As written, Subclaim 1 merely restates what must be proved, so Claim 2.3 and Theorem 1.1 do not follow from the text.","section":"§2, Claim 2.3, Subclaim 1"},{"comment":"The induction hypothesis cannot be applied to the left copy Gn when intercube edges are deleted: Gn need not be S_{n-1,n-1}-free, because an S_{n-1,n-1} inside Gn would extend to S_{n,n} only if the two relevant cross edges to the right copy are still present. The proof never quantifies the deleted intercube edges, so the phrase 'regardless of how edges are removed' is exactly the unproven assertion. This is load-bearing, as it breaks the transfer of the no-deletion argument to the deletion case.","section":"§2, Claim 2.3, part (2)"},{"comment":"The minimum-degree transformation is not rigorously justified. The proof does not show that deleting p1s1 and adding vp1 preserves S_{n-1,n-1}-freeness in all cases, nor does it handle the situation where multiple vertices achieve the minimum degree t and the selected neighbor p1 changes after each operation. Since the final proof of Theorem 1.1 uses Claim 2.1 to assume δ(G_n)=n−1, this gap propagates to the upper-bound argument.","section":"§2, Claim 2.1"},{"comment":"The base case contains invalid inferences; for example, 'Since all neighbors of u5 in G3 have degree 3, it follows that dG3(u5)=3' does not hold if u5 has few or no neighbors, and the case analysis does not rule out u5 having degree 1 or 2. While the n=3 statement is likely true and could be checked by exhaustive search, the written proof is incomplete.","section":"§2, Claim 2.3, base case n=3"}],"minor_comments":[{"comment":"The abstract contains a grammatical error: 'the Turán number of the balanced star Sn,n is has been studied' should be 'has been studied.'","section":"Abstract"},{"comment":"The notation 'd(x) i.e.|N(v)|' is inconsistent; it should be d(v)=|N(v)|.","section":"§1"},{"comment":"The base case of Claim 2.2 is justified only by reference to Figure 1, which is not included in the text; the structural difference between G3 and G′3 should be described explicitly.","section":"§2, Claim 2.2"},{"comment":"The sentence 'Suppose that deleting at most r intercube edges in e[Qn,Qn], there is no Sn,n-free subgraph Gn+1⊆Qn+1 with e(Gn+1)≥...' has an unclear quantifier; it should be rephrased as 'there exists an Sn,n-free subgraph' or 'every subgraph contains an Sn,n' to match the intended contradiction.","section":"§2, Claim 2.3, Subclaim 1"},{"comment":"The statement of Theorem 1.1 in Section 3 as n×2^{n-1}−3×2^{n-3} is equivalent to 2^{n-3}(4n−3), but the equivalence is not noted, and the two forms appearing in the paper may confuse readers.","section":"§3, Theorem 1.1"}],"recommendation":"reject","confidential_remarks":"The manuscript is very short and the main upper-bound proof is essentially a placeholder: Subclaim 1 of Claim 2.3 is the crux of the induction and is asserted, not proved. I do not see how a revision within the current approach could be minor; the authors would need to supply a genuine proof of the deletion case or a different argument for the upper bound. The lower-bound construction is a useful first step, but it cannot carry the paper on its own. There is also a mismatch between the paper's title/subject (hypercube Turán numbers) and the lengthy discussion of planar Turán numbers in the introduction, which seems tangential."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the honest read. The paper takes a natural question—the Turan number of a balanced double star in the hypercube—and proposes a clean formula, 2^{n-3}(4n-3). The lower-bound construction in Claim 2.2 is genuinely nice: take two copies of extremal Q_n subgraphs on opposite facets, add all 2^n cross edges, and rely on the condition that no two corresponding vertices are both of full degree. That construction is plausible, and the n=3 base case can be checked by hand, so the lower bound likely holds.\n\nThe problem is the upper bound. Claim 2.3 is the whole game, and its Subclaim 1 essentially asserts the induction step: any edge-deleted subgraph of Q_{n+1} with more than the claimed number of edges must contain S_{n,n}, for arbitrary deletion patterns on the cross edges. The proof of that subclaim is a terse partition into R1/R2/R3 with no quantitative counting, no derivation that the extra edge forces two adjacent degree-(n+1) vertices, and no account of how deleting cross edges lowers degrees inside each copy. The phrase \"regardless of how edges are removed\" is exactly what needs proof, not something you can assume. So as written, Theorem 1.1 is not established.\n\nThere are smaller issues too. Claim 2.1's degree-raising transformation is handwavy about why it never creates two adjacent full-degree vertices, and the n=3 upper bound in Claim 2.3 has a couple of \"necessarily contains\" steps that would need a careful case check. The citation pattern is fine: the authors correctly separate planar double-star results from hypercube cycle results, and the exact value they claim does look new.\n\nFor a reader working on hypercube Turan problems, the lower-bound construction is worth knowing, and this paper is a good cautionary example of an induction step being asserted rather than proved. It deserves a serious referee, because the formula may well be true and the lower-bound idea is reusable, but it needs major revision with a complete proof of Claim 2.3 before it can be accepted.","headline":"The lower-bound construction is nice and the formula is plausible, but the upper bound rests on an unproved assertion, so Theorem 1.1 is not established as written.","tokens_in":7096,"tokens_out":3755,"would_cite":false,"duration_ms":36831,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every $n \\ge 3$, the densest subgraph of the hypercube $Q_n$ containing no balanced double star $S_{n-1,n-1}$ has exactly $2^{n-3}(4n-3)$ edges, and the paper proves this bound is both necessary and attainable.","keywords":["Turán number","balanced double star","hypercube","H-free subgraph","extremal graph theory","degree condition","exact extremal value"],"falsifier":"A direct computer check at $n=4$ would settle the theorem: search subgraphs of $Q_4$ (16 vertices, 32 edges) for one with 27 edges in which no edge joins two vertices of degree 4; existence refutes $\\mathrm{ex}(Q_4, S_{3,3}) = 26$, while a maximum of 26 corroborates the construction and the induction base. Such a search can be posed as an integer program or SAT instance with degree-4 variables and a clause forbidding adjacency between two degree-4 endpoints. The $n=3$ case (claimed maximum 9 of 12 edges) is small enough to check exhaustively by the same formulation.","tokens_in":6053,"feed_emoji":"⭐","tokens_out":22548,"duration_ms":198525,"temperature":0.7,"pith_summary":"The paper determines the exact Turán number of the balanced double star $S_{n-1,n-1}$ in the $n$-dimensional hypercube $Q_n$: every subgraph that contains no copy of this tree has at most $2^{n-3}(4n-3)$ edges, and there are subgraphs attaining exactly this many, for every $n \\ge 3$. The forbidden tree, the double star, is obtained from an edge by attaching $n-1$ further leaves to each endpoint. The key reduction is that in the bipartite hypercube adjacent vertices share no common neighbour, so a copy of the double star appears exactly when the subgraph contains an edge whose two endpoints both have the maximum possible degree $n$; the extremal problem then asks how many edges can be kept while keeping all degree-$n$ vertices mutually non-adjacent. The paper proves the answer by an inductive construction that pairs two extremal subgraphs across the two halves of $Q_{n+1}$, together with an induction for the upper bound. This is the first exact Turán number for a double star in a hypercube, a family whose planar versions have been studied but whose hypercube behaviour was previously open, and one of the few exact answers in a subject where even the four-cycle problem still has only bounds.","feed_headline":"Dodge the double star in Q_n: delete exactly 3·2^(n−3) edges","feed_subtitle":"First exact Turán number for a double star in a hypercube: the extremal graph keeps 1 − 3/(4n) of all edges.","key_machinery":"The load-bearing mechanism is the translation of the forbidden double star into a degree condition: since adjacent vertices in $Q_n$ share no common neighbour, a subgraph contains $S_{n-1,n-1}$ exactly when it has an edge joining two vertices of degree $n$, the maximum possible degree. The Turán problem thereby becomes a constrained subgraph problem that the paper handles by induction on dimension, using the factorization $Q_{n+1} = Q_n \\times K_2$. The construction step pairs two extremal graphs of $Q_n$ that have disjoint full-degree vertex sets, one in each half of $Q_{n+1}$, and adds all $2^n$ intercube edges; the disjointness guarantees no intercube edge joins two vertices that both reach degree $n+1$. The upper-bound step partitions the surviving vertices of one half into three classes $R_1, R_2, R_3$ according to which cube-edges and intercube-edges are retained, and asserts that any surplus edge must fall in $R_2$ and create two adjacent vertices of degree $n+1$, that is, an $S_{n,n}$.","core_discovery":"Theorem 1.1 states that $\\mathrm{ex}(Q_n, S_{n-1,n-1}) = 2^{n-3}(4n-3)$ for every $n \\ge 3$, with the special values $0$ for $n=1$ and $2$ for $n=2$. Because $Q_n$ has $n \\cdot 2^{n-1}$ edges, this is equivalent to saying that every $S_{n-1,n-1}$-free subgraph must delete at least $3 \\cdot 2^{n-3}$ edges, and that a construction deleting exactly that many exists. The paper's core observation is that adjacent vertices of the hypercube have no common neighbour, so the double star is present precisely when an edge joins two vertices of the maximum possible degree $n$; the extremal problem therefore reduces to keeping the full-degree vertices pairwise non-adjacent while maximizing edges. The proof shows that a maximum-edge solution can be assumed to have minimum degree $n-1$; that there are two extremal subgraphs $G_n$ and $G'_n$ with no vertex of degree $n$ common to both; and that placing these two in the two copies of $Q_n$ inside $Q_{n+1} = Q_n \\times K_2$, with all $2^n$ intercube edges present, yields extremal subgraphs in the next dimension with $2^{n-2}(4(n+1)-3)$ edges. The upper bound is proved by induction on $n$ through the same two-copy split.","pith_inferences":["The reduction 'no two full-degree vertices adjacent' suggests the template extends to nearby double stars $S_{k,l}$: exact values would then be governed by how many degree-$n$ vertices a subgraph can carry with no adjacent pair, a question that is computable in small dimensions and might yield a closed formula for a whole family.","The assembly rule — two extremal graphs with disjoint full-degree sets, one per half of $Q_{n+1}$, plus all cross edges — is a general recipe for degree-constrained Turán problems on Cartesian products; grids and toruses are the natural places to test it next.","Nothing in the proof rules out extremal graphs beyond the two constructed ones; a symmetry classification of the 26-edge subgraphs of $Q_4$ would show whether the construction undercounts the extremal family.","The contrast with the even-cycle problems, where only asymptotic bounds are known, points to a rough heuristic: for trees anchored on one central edge, the extremal number in a bipartite host is set by the local degree budget rather than by isoperimetric density."],"forward_implications":["The bound is sharp in both directions: keeping more than $2^{n-3}(4n-3)$ edges forces an $S_{n-1,n-1}$, while deleting exactly the complementary $3 \\cdot 2^{n-3}$ edges is always possible.","The extremal density is $1 - 3/(4n)$, so a subgraph can keep a fraction tending to 1 of the hypercube's edges while still avoiding a double star whose two wings both have size $n-1$.","For every $n \\ge 3$ there are at least two distinct extremal subgraphs, and any maximum-edge $S_{n-1,n-1}$-free subgraph of $Q_n$ can be assumed to have minimum degree exactly $n-1$.","Instantiating the formula gives $\\mathrm{ex}(Q_3, S_{2,2}) = 9$ and $\\mathrm{ex}(Q_4, S_{3,3}) = 26$, concrete values that anchor the induction and can be checked directly."],"supporting_citations":[{"why":"Initiates the hypercube Turán problem $\\mathrm{ex}(Q_n, H)$ with the four-cycle question; supplies the framework and notation the paper extends.","marker":"[4]"},{"why":"Introduces the double-star Turán number and provides the planar exact values and bounds that motivate asking the same question in hypercubes.","marker":"[5]"},{"why":"Establishes $\\mathrm{ex}(Q_n, C_{4k}) = o(e(Q_n))$, the even-cycle line of results that frames the paper's contrast with an exact double-star value.","marker":"[2]"}],"fun_headline_variants":["Dodge double star: cut 3·2^{n−3} edges in Q_n","Hypercube double star: exact max edges is 2^{n−3}(4n−3)","First exact Turan number for a double star in a hypercube","Exact Turan: ex(Q_n, S_{n−1,n−1}) = 2^{n−3}(4n−3)","Delete exactly 3·2^{n−3} edges to stay S_{n−1,n−1}-free in Q_n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole upper bound rests on the structural claim, called Subclaim 1 inside Claim 2.3, that no matter which edges between the two halves of $Q_{n+1}$ are deleted, a subgraph that still has too many edges must contain two adjacent vertices of degree $n+1$; the paper states this via a partition of vertices into three classes but gives no derivation of the partition's decisive properties, so the induction collapses if some deletion pattern escapes it.","fun_headline_variants_meta":{"raw":{"variants":["Dodge double star: cut 3·2^{n−3} edges in Q_n","Hypercube double star: exact max edges is 2^{n−3}(4n−3)","First exact Turan number for a double star in a hypercube","Exact Turan: ex(Q_n, S_{n−1,n−1}) = 2^{n−3}(4n−3)","Delete exactly 3·2^{n−3} edges to stay S_{n−1,n−1}-free in Q_n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002134,"raw_usage":{"total_tokens":8401,"prompt_tokens":1180,"completion_tokens":7221,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":796,"completion_tokens_details":{"reasoning_tokens":7086}},"tokens_in":796,"tokens_out":7221,"duration_ms":51656,"temperature":1.0,"reasoning_tokens":7086,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:12:39.198529+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct computer check at $n=4$ would settle the theorem: search subgraphs of $Q_4$ (16 vertices, 32 edges) for one with 27 edges in which no edge joins two vertices of degree 4; existence refutes $\\mathrm{ex}(Q_4, S_{3,3}) = 26$, while a maximum of 26 corroborates the construction and the induction base. Such a search can be posed as an integer program or SAT instance with degree-4 variables and a clause forbidding adjacency between two degree-4 endpoints. The $n=3$ case (claimed maximum 9 of 12 edges) is small enough to check exhaustively by the same formulation.","supporting_citations":[{"cited_title":"On some problems in graph theory, combinatorial analysis and combinatorial number theory","cited_arxiv_id":null,"evidence_quote":"Initiates the hypercube Turán problem $\\mathrm{ex}(Q_n, H)$ with the four-cycle question; supplies the framework and notation the paper extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes $\\mathrm{ex}(Q_n, C_{4k}) = o(e(Q_n))$, the even-cycle line of results that frames the paper's contrast with an exact double-star value."}],"review_version":1}