{"id":"9d72d099-05a1-4d53-ade2-6ac959503a93","arxiv_id":"2607.25917","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every n ≥ 5, the n-dimensional dual-cube contains two completely independent spanning trees; for n ≥ 6 the paper gives a recursive construction with diameter bounds 5n+5 and 5n+7.","lead":"This paper proves that the dual-cube network F_n contains two completely independent spanning trees—two edge-disjoint communication backbones that leave no vertex over-burdened—for every dimension n ≥ 5, and gives a recursive algorithm to build them. The result is plausible and useful for fault-tolerant routing, but the proof currently rests on an unshipped computer-assisted base case and contains a few internal inconsistencies.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's base-case enumeration undercounts configurations: fixing u=0000 leaves 15·C(14,2)=1365 distinct cases, not C(15,3)=455, so the reported ILP check covers at most one third of the required pairs.","rationale":"The reader identified Lemma 1's ILP base case as the weakest load-bearing assumption, focusing on the lack of shipped code and certificates. Our stress-test finds a more specific and more serious flaw: even the enumeration count in the manuscript is wrong by a factor of three. Fixing u=0000, the distinct configurations are 15·C(14,2)=1365, not C(15,3)=455, because the partner v of u is distinguished from the second pair {x,y}. The three pairings of a given 4-set are generally inequivalent under automorphisms, so checking one per triple cannot suffice. This directly threatens the induction base of Lemma 1 and hence the existence theorem for all n≥5. However, this is a gap in the written proof rather than a demonstrated counterexample; if the missing cases are feasible, the theorem stands. The reader's CONDITIONAL verdict therefore remains appropriate, and our finding does not move it. We partially agree with the reader because we share the identification of the base case as load-bearing, but we supply a concrete counting defect not noted in the reader's weakest_assumption. The proposed test—running the ILP on all 1365 configurations—would settle whether the concern lands.","tokens_in":21534,"tokens_out":24097,"duration_ms":187831,"concrete_test":"Re-run the ILP from Appendix A for all 1365 configurations: fix u=0000; for each v in V(Q_4)\\setminus{0} and each unordered pair {x,y} disjoint from {0,v}, impose y1_u=y1_v=1 and y2_x=y2_y=1 and test feasibility. Equivalently, start from the 455 reported triples and explicitly test the other two assignments of v within each triple. If all 1365 are feasible, Lemma 1's base case holds and the proof can be repaired by updating the count; if any is infeasible, Theorem 2 is false as stated. Publishing the solver code and certificates would also settle reproducibility.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 1's base case (n=4) is the foundation of Theorem 2: every cluster is Q_{n-1}, so for n=5 the clusters are Q_4 and Lemma 1 must hold for every two disjoint vertex pairs. The proof reports an exhaustive ILP verification with u=0000 and 'enumerate all possible choices of the remaining vertices v, x, y', claiming the number of instances is C(15,3)=455. But v is distinguished as the other vertex of the first pair while {x,y} is an unordered second pair, so the correct count is 15·C(14,2)=1365. Choosing an unordered triple {a,b,c} and running the ILP once does not cover the three distinct requirements: {u,a} in T1 with {b,c} in T2, {u,b} in T1 with {a,c} in T2, and {u,c} in T1 with {a,b} in T2. These are not equivalent under hypercube automorphisms fixing 0 because the internal Hamming distance of the second pair differs (e.g., triple {1,2,12} in Q_4 gives second-pair distances 2, 3, and 3). Thus the reported 'exhaustive' verification omits up to 910 configurations. If any omitted configuration is infeasible, Lemma 1 fails and the whole construction for all n≥5 collapses. The paper ships no ILP code or feasibility certificates, so the claim cannot be checked from the manuscript. This is a concrete, load-bearing gap in the existence proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every n ≥ 5 the n-dimensional dual-cube F_n admits two completely independent spanning trees (CIST), and gives a recursive algorithm, F-2CIST-Recursive, claimed to produce two CIST with diameters 5n+5 and 5n+7 for n ≥ 6. The proof strategy is to decompose F_n into clusters isomorphic to Q_{n-1}, first finding two edge-disjoint Hamiltonian paths in the quotient graph K_{2^{n-1},2^{n-1}}, then constructing local CIST inside every cluster with prescribed internal vertices matched to the cross-edge endpoints. A base case for n = 5 is obtained by ILP plus a local optimization step.","tokens_in":21968,"tokens_out":22358,"duration_ms":171446,"significance":"If the proof is repaired, the result is a natural and useful contribution: it establishes the first CIST existence theorem for the dual-cube, a sparser hypercube variant, and it gives an explicit recursive construction with linear diameter. The conceptual decomposition into an inter-cluster Hamiltonian-path problem and a local hypercube CIST problem with prescribed internal vertices is elegant and likely to be reusable. The paper also proposes a plausible conjecture about lifting k CIST from Q_n to F_{n+1}. However, the proof as written is not reliable: the base-case verification is undercounted, a central induction case is missing, Lemma 2 is false as stated, and the diameter formulas in Theorem 4 are asserted rather than proved. These are load-bearing issues, though they appear repairable within the existing framework.","major_comments":[{"comment":"The claimed exhaustive ILP verification is not exhaustive. Fixing u = 0000, v has 15 choices and {x,y} is an unordered pair from the remaining 14 vertices, so the number of configurations is 15·C(14,2) = 1365, not C(15,3) = 455. Enumerating unordered triples {v,x,y} covers only one role assignment per triple; the three assignments are not equivalent under automorphisms fixing 0 because the internal Hamming distance of the second pair depends on which vertex is v. This is load-bearing because Lemma 1 is invoked for every cluster Q_{n-1} in Theorem 2. Please correct the enumeration, run all 1365 (or provide a rigorous reduction), and make the ILP instances or feasibility certificates available.","section":"Section 3, Lemma 1, base case"},{"comment":"The induction omits the 2+2 distribution in which {u,v} lie in one copy of Q_n and {x,y} lie in the other. Cases 1–3 cover 4+0, 3+1, and 2+2 with one vertex of each tree in each copy, but not u_i=v_i=0, x_i=y_i=1. Consequently the assertion in Case 4 that the only remaining pattern is u_i=v_i≠x_i=y_i for every i is false. In addition, Case 3 is internally inconsistent: after stating that the relevant cross-pairs are (u^{i,0},v^{i,1}) and (x^{i,0},y^{i,1}), the subcases switch to (u,y) and (x,v), and Subcase 3.2 assumes u0–y1 is an edge but then connects copies using (v0,v1) and (x0,x1), never using the assumed edge. A coherent repair of this induction is needed before Lemma 1 can support Theorem 2.","section":"Section 3, Lemma 1, induction step"},{"comment":"The construction P_p and P_q is not edge-disjoint for arbitrary distinct primes p,q. In K_{m,m} the paths share edges whenever p ≡ ±q (mod m). For example, with m=16, p=3 and q=13, the edge 7_0–10_1 lies on both P_3 and P_13. Since m=2^{n-1}, such pairs of primes exist in the stated range. The underlying existence claim is true — K_{m,m} has edge-disjoint Hamiltonian cycles — but the lemma as stated is false. Because the explicit P_p/P_q are used to determine the required internal vertices in each cluster, the construction in Theorems 2 and Algorithm 1 must either use a correct edge-disjoint pair of Hamiltonian paths or add a hypothesis on p,q.","section":"Section 3, Lemma 2"},{"comment":"The proof of Theorem 4 asserts diam(T_1)=5n+5 and diam(T_2)=5n+7 for n≥6, but no induction calculation is given. 'By repeating the same construction recursively, we obtain the following equality' is not a proof: one must account for the distances within the four copies, the lengths contributed by the three cross-edges, and the choice of the extremal copies at each level. The base values in §4.2 are 29 and 31, so the recurrence would give 35 and 37 for n=6, but the paper does not show how these are computed from the local tree data. Please provide a genuine inductive distance analysis.","section":"Section 4, Theorem 4"},{"comment":"The explicit base-case data for F_5 is internally inconsistent. In Table 4, the row for cluster 14^0 contains the parent value 20 in a 16-vertex Q_4 cluster, which is outside the vertex set. Several vectors in Tables 3 and 4 have fewer than 16 entries (e.g., rows 7^0 and 11^0 in Table 3). Since these local trees are the basis for the diameter claims and the recursive algorithm, the tables need to be regenerated and corrected, or the code/solver output must be supplied so the reader can verify the claimed F_5 construction.","section":"Section 4 and Appendix B"}],"minor_comments":[{"comment":"Theorem 3 states diameters 28 and 31, while §4.2 computes diam(T_1)=29 and diam(T_2)=31, and the abstract/introduction say 29 and 31. Please reconcile.","section":"Section 4, Theorem 3"},{"comment":"Algorithm 3 calls F-2CIST-Base for the F_5 copies, but the proof of Theorem 4 uses trees produced by F-2CIST-Base and F-2CIST-Enhanced. Clarify which algorithm is actually the base of the recursion.","section":"Section 4, Algorithm 3"},{"comment":"There is a typo: 'Q^{i,0}_1' should be 'Q^{i,0}_n'.","section":"Section 3, Lemma 1, Case 3.1"},{"comment":"The formatting of Tables 3 and 4 makes the columns (cluster, generators, center, parent vector) hard to parse; a legend explaining the row format would help.","section":"Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The core idea is sound and the result is likely correct after repairing the proof, so I do not recommend rejection. However, the current manuscript has several load-bearing gaps: the base-case ILP enumeration is undercounted by a factor of three, Lemma 1's induction misses a case and mixes up the cross-pairs in Case 3, Lemma 2 is false as stated for arbitrary distinct primes, and Theorem 4's diameter formula lacks a proof. The computational base case is also not reproducible without the ILP code or certificates. I would ask the authors to fix these points and to supply the missing verification artifacts before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper gives a real new result — two completely independent spanning trees in F_n for n≥5 — and a recursive construction with linear diameters. The high-level scheme is sound: contract clusters to K_{m,m}, take two edge-disjoint Hamiltonian paths, then fill each Q_{n-1} cluster with local CIST whose generator pairs match the cross-edge endpoints. Lemma 1, allowing prescribed internal vertex pairs in hypercube CIST, is a useful new tool. The appendix tables for F5 are concrete, and the authors are honest about the 700-hour failed attempt on F4.\n\nThe soft spots are in the verification, not the architecture. Lemma 1's base case is load-bearing: every cluster is Q_{n-1}, so n=5 needs all configurations in Q4. The paper says fixing u=0000 leaves C(15,3)=455 instances, but the actual count is 15*C(14,2)=1365. The extra cases are not equivalent under hypercube automorphisms fixing 0, because the internal Hamming distance of the second pair differs. The reported ILP run therefore covers at most a third of the required configurations, and no ILP code or certificates are shipped. If even one omitted configuration is infeasible, Theorem 2 collapses. That is a genuine gap in the written proof. Fixing it may be routine — the claim is plausible — but it has to be fixed.\n\nLemma 2 also has a false subclaim: two distinct primes do not by themselves guarantee edge-disjoint Hamiltonian paths in K_{m,m} (m=8, p=3, q=5 is a counterexample). The underlying existence is standard and cited, so this is repairable.\n\nTheorem 4 is weaker than the abstract suggests: the diameter recurrence is asserted, not proved, and the F5 base case is inconsistent in the text (29 vs 28 for T1). The n≥6 diameter claim needs a real proof, not a 'by repeating the same construction' statement.\n\nNet: the central existence claim is probably true, and the framework is worth publishing. But this version should not be accepted as is. The base-case verification and the diameter recurrence need to be supplied. Send it to a serious referee, ask for those fixes.","headline":"New existence result for two CIST in dual-cubes with a genuinely useful cluster-based framework — but the load-bearing base case is under-verified as written.","tokens_in":22403,"tokens_out":4284,"would_cite":true,"duration_ms":39393,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C05","05C38","05C40","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The n-dimensional dual-cube F_n contains two completely independent spanning trees for every n ≥ 5, and a recursive algorithm constructs them with diameters 5n+5 and 5n+7 for n ≥ 6.","keywords":["dual-cube","completely independent spanning trees","hypercube","Hamiltonian paths","complete bipartite graph","interconnection networks","fault-tolerant routing","diameter"],"falsifier":"Re-run the integer-linear-programming model for all 455 (v,x,y) configurations in Q_4 with the generator constraints; if any instance is infeasible, Lemma 1's base case fails and Theorem 2 collapses. Separately, instantiate Lemma 2's construction with m=8 and primes p=3, q=5 to see that the two Hamiltonian paths in K_{8,8} share edges, contradicting the lemma as stated.","tokens_in":21449,"feed_emoji":"🌐","tokens_out":10052,"duration_ms":80382,"temperature":0.7,"pith_summary":"Completely independent spanning trees are pairs of spanning trees that share no edges and no vertex that is internal to more than one tree; they give two openly-disjoint routes between any two vertices. The paper establishes that the n-dimensional dual-cube F_n — a hypercube-like network with the same degree but fewer edges per vertex — contains such a pair for every n ≥ 5. The proof decomposes F_n into hypercube clusters, uses the fact that the clusters form a complete bipartite graph, threads two edge-disjoint Hamiltonian paths through that quotient, and then fills each cluster with two local spanning trees whose prescribed internal vertices match the cross-edge endpoints. A recursive algorithm extends the construction to all n ≥ 6 with diameters 5n+5 and 5n+7, and the authors conjecture that k CIST in the hypercube imply k CIST in the dual-cube. If correct, this gives the dual-cube the same fault-tolerant routing backbone as the hypercube at lower wire density.","feed_headline":"Two independent spanning trees exist in every dual-cube for n ≥ 5","feed_subtitle":"The recursive construction achieves diameters 5n+5 and 5n+7, bringing fault-tolerant routing to a link-sparse network.","key_machinery":"The cluster decomposition of F_n is the load-bearing structure: it turns a large graph into a complete bipartite quotient K_{2^{n-1},2^{n-1}} whose vertices are hypercubes. Lemma 1 ('generator pairs') guarantees local CIST inside Q_{n-1} with any two prescribed vertices internal in each tree; Lemma 2 supplies two edge-disjoint Hamiltonian paths on the quotient. The combination fixes, for each cluster, which vertices must be internal in T_1 and T_2, so gluing local trees along the paths yields two spanning trees that are edge-disjoint and share no internal vertex. The recursive diameter control selects cross-edges close to local centers, producing the 5n+5 / 5n+7 diameters.","core_discovery":"The central claim is that the n-dimensional dual-cube F_n contains two completely independent spanning trees for every n ≥ 5. The proof decomposes F_n into its (n−1)-dimensional hypercube clusters, treats the quotient of clusters as a complete bipartite graph, and shows that two edge-disjoint Hamiltonian paths on that quotient can be combined with local CIST inside each cluster. The key lemma asserts that for any n ≥ 4 and any two disjoint vertex pairs in Q_n, there exist two CIST of Q_n in which the prescribed pairs are internal vertices; the base case n=4 is verified exhaustively by an integer-linear-programming search. The recursive algorithm F-2CIST assembles the trees from an optimized","pith_inferences":["The quotient-plus-local-generators scheme is a reusable template: any network built from hypercube clusters wired as a complete bipartite graph should inherit CIST from edge-disjoint Hamiltonian structures on the quotient, so other hypercube variants with cluster layouts are natural targets.","The per-dimension diameter increment of 5 is tied to the chosen inter-cluster shortest-path trees; adjusting the local tree shapes or the cross-edge selection rule could reduce the constant.","The base case n=4 is checked by an unreleased ILP, so a human-readable constructive proof for Q_4 would remove the computational dependency from the whole induction.","The text reports F_5 diameters as 29 and 31 in the introduction and 28 and 31 in Theorem 3; resolving this discrepancy is needed before benchmarking the recursive formula."],"forward_implications":["Every dual-cube F_n with n ≥ 5 supports two CIST, so between any two vertices there are two internally vertex-disjoint paths, one in each tree.","For n ≥ 6, the F-2CIST-Recursive algorithm yields two explicit CIST with diameters 5n+5 and 5n+7, growing linearly with the dimension.","At the same vertex count, the dual-cube's CIST diameters stay close to the hypercube's 2n−1, so the link-sparse topology remains competitive for fault-tolerant routing.","If Conjecture 1 holds, k CIST in Q_n would produce k CIST in F_{n+1}, potentially multiplying the number of independent routing backbones."],"fun_headline_variants":["Dual-cube gets two independent spanning trees for n ≥ 5","Recursive CIST construction for dual-cube, n ≥ 5","Two CISTs in dual-cube: recursive proof for all n ≥ 5","Hypercube-based proof yields two CISTs in dual-cube","Dual-cube CIST: recursive algorithm, diameters 5n+5 and 5n+7"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The construction rests on a computer search over all 455 configurations in the 4-dimensional hypercube base case, which the paper reports as feasible without releasing the program or certificates.","fun_headline_variants_meta":{"raw":{"variants":["Dual-cube gets two independent spanning trees for n ≥ 5","Recursive CIST construction for dual-cube, n ≥ 5","Two CISTs in dual-cube: recursive proof for all n ≥ 5","Hypercube-based proof yields two CISTs in dual-cube","Dual-cube CIST: recursive algorithm, diameters 5n+5 and 5n+7"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000238,"raw_usage":{"total_tokens":1295,"prompt_tokens":642,"completion_tokens":653,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":386,"completion_tokens_details":{"reasoning_tokens":547}},"tokens_in":386,"tokens_out":653,"duration_ms":5232,"temperature":1.0,"reasoning_tokens":547,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T01:08:58.531458+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the integer-linear-programming model for all 455 (v,x,y) configurations in Q_4 with the generator constraints; if any instance is infeasible, Lemma 1's base case fails and Theorem 2 collapses. Separately, instantiate Lemma 2's construction with m=8 and primes p=3, q=5 to see that the two Hamiltonian paths in K_{8,8} share edges, contradicting the lemma as stated.","supporting_citations":[],"review_version":1}