{"id":"9681f0f6-e542-4cf3-a138-6e34b3594196","arxiv_id":"2608.01929","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Indispensable Markov moves for sampling graphs with fixed degree and Forman-Ricci curvature sequences have degree at least quadratic in the maximum degree, and degree-3 moves still span the lattice.","lead":"This paper works out the algebraic moves needed to resample graphs while keeping their degrees and Forman-Ricci curvatures fixed. It proves the full set of moves must contain some of quadratic size, then builds a small degree-3 lattice basis and tests a reinforcement-learning sampler.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the odd-Δ transfer in Theorem 3.5 is valid, though unproved in the text; the central quadratic lower bound stands.","rationale":"The reader's conditional verdict was motivated in part by the unproved transfer in Theorem 3.5. On inspection, the transfer is true: the kernel of B_{Δ−1} embeds into the kernel of B_Δ by zero-extension, and primitivity is preserved because any divisor in the larger kernel would also lie in the smaller one. Therefore the main quadratic lower bound is secure. I also checked the even-Δ primitivity argument (Lemmas 3.2–3.3 and Theorem 3.4), the degree computation, and the lattice-basis theorem; no correctness-threatening flaw emerged. The remaining issues noted by the reader — overstatement of the RL sampler's performance relative to Table 1 and missing variance information — are real but concern the empirical Section 5, not the central algebraic claim. Accordingly, the verdict should remain CONDITIONAL, but not because of the transfer assumption. Hence no change to the reader's verdict, while disagreeing that the transfer is the load-bearing weak point.","tokens_in":18183,"tokens_out":28251,"duration_ms":269576,"concrete_test":"For Δ=5,7,9 (odd), compute u_{Δ−1} via Equation (5), embed it by zeros into the column space of B_Δ, and use a CAS (Macaulay2 or Sage) to verify: (1) B_Δ u_{Δ−1}=0; (2) there is no nonzero v∈ker(B_Δ) with 0≤v+≤u+ and 0≤v−≤u−. This directly confirms the transfer and the primitivity claim for representative odd cases.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest assumption — that primitive moves of B_{Δ−1} are automatically primitive moves of B_Δ — is actually correct, so it is not a load-bearing threat. Let u=u_{Δ−1}, supported only on pairs from {1,...,Δ−1}. If v∈ker(B_Δ) with 0≤v+≤u+ and 0≤v−≤u−, then v is also supported on those pairs. The extra rows of B_Δ (the degree-Δ row and curvature rows 2Δ−1, 2Δ) vanish identically on such columns, and the remaining rows of B_Δ coincide with B_{Δ−1} on those columns. Hence B_{Δ−1}v=0, so v would be a divisor of u inside ker(B_{Δ−1}), contradicting the primitivity of u in B_{Δ−1}. Thus the transfer holds; the paper merely omits a one-line proof. The even-Δ construction (Lemmas 3.2–3.3, Theorem 3.4) checks out, and the lattice-basis result (Theorem 4.6) is independent support. No other flaw threatening the central claim was found.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the integer kernel of the matrix B_Δ that encodes degree and Forman–Ricci curvature frequency constraints on the joint degree matrix of a simple graph, and of its Lawrence lifting Λ(B_Δ). The main theoretical results are: (i) for every Δ ≥ 4 there exists a primitive Markov move for B_Δ of degree 2(⌊Δ/2⌋ − 1)^2 + 1, so the unique minimal Markov basis of Λ(B_Δ) contains moves whose degree grows quadratically in Δ (Theorem 3.5 and Corollary 3.6); and (ii) a lattice basis for ker B_Δ consisting of explicit degree-three moves b_{ijkℓ}, obtained as a triangular subset of all degree-three moves (Theorem 4.6). The paper also applies the actor-critic fiber sampler of Gvozdanovic and Petrovic to explore JDMs of moderate-size graphs.","tokens_in":18425,"tokens_out":30588,"duration_ms":324034,"significance":"If correct, the quadratic degree growth is a meaningful complexity result: it explains and quantifies the computational difficulty of computing Markov bases for the curvature-and-degree constrained graph sampling problem introduced by Roost et al. The explicit lattice basis of degree-three moves is a useful constructive complement, since a full Markov basis seems out of reach. The even-Δ construction in Section 3 is detailed and self-contained, and the lattice-basis construction is explicit and verifiable. The odd-Δ transfer in Theorem 3.5 is true but is presently asserted without proof; this is a gap in presentation rather than a counterexample to the claim. The reinforcement-learning experiments are exploratory and provide reproducible code, but they do not sharply benchmark the method against exact algebraic sampling.","major_comments":[{"comment":"The odd-Δ case rests on the assertion that 'the primitive moves of A_{Δ−1} are also primitive moves for B_Δ' (with A presumably meaning B). This is load-bearing for all odd Δ, since the quadratic lower bound otherwise holds only for even Δ. The statement is correct: u_{Δ−1} is supported only on pairs from {1, . . . , Δ−1}; if v ∈ ker(B_Δ) with 0 ≤ v+ ≤ u+ and 0 ≤ v− ≤ u−, then v is supported on the same pairs, the degree-Δ row and the curvature rows 2Δ−1 and 2Δ of B_Δ vanish identically on such columns, and the remaining rows coincide with B_{Δ−1}. Hence v would contradict primitivity of u_{Δ−1} in B_{Δ−1}. Please add this one-paragraph proof (and fix the A/B notation).","section":"Theorem 3.5"}],"minor_comments":[{"comment":"'A_4' and 'A_{Δ−1}' should be 'B_4' and 'B_{Δ−1}'. Also, 'the unique minimal Markov move for B_4' would be clearer as 'the unique, up to sign, primitive move for B_4'.","section":"Theorem 3.5 proof"},{"comment":"The equation 'rank(Λ(B_Δ)) = ... = d−2' uses d without defining it in this paper. Since the preceding text uses d for the number of rows in Definition 2.9 and for other quantities elsewhere, please define d explicitly (or remove the 'd−2' equality).","section":"Proposition 4.2"},{"comment":"The classification of all degree-three moves is terse, and the 'without loss of generality' step in the proof does not explicitly address diagonal pairs (e.g., e_{jj}) or repeated indices. The selected lattice basis is proved independently by the triangular submatrix in Theorem 4.6, but the classification claim would benefit from a more careful argument or a reference.","section":"Proposition 4.4"},{"comment":"In the displayed inequality, |E(G)| = 1/2(Σ_{a,b} J_ab + Σ_a J_aa) equals Σ_{a≤b} J_ab by symmetry, so the '≥' should be '='. If the intended bound is on the lifted move degree, please state that explicitly.","section":"Section 5, edge-count bound"},{"comment":"Several rows report only 1 sampled state, which suggests the RL method found no moves in those runs. This is consistent with the stated lower-bound interpretation, but the narrative that the method 'performs well' should be tempered, or additional runs/metrics should be reported.","section":"Table 1"}],"recommendation":"minor_revision","confidential_remarks":"The algebraic core of the paper is sound and the central quadratic lower bound is established once the short odd-Δ transfer argument in Theorem 3.5 is supplied. The RL section is more of a proof-of-concept than a benchmarked empirical study; if the journal gives weight to the empirical claims, the authors should add more runs and error bars or explicitly label the experiments as illustrative. The scope fits an algebraic-statistics/combinatorics audience."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read Coons–Zucal with the stress-test note. Bottom line: the central result is correct and the paper deserves a serious referee, with one presentational gap and one over-claim to fix.\n\nWhat's actually new: a family of primitive moves u_Δ for B_Δ whose degree is quadratic in Δ, giving a lower bound on the degree of indispensable moves in the unique Markov basis of Λ(B_Δ). The construction (Lemmas 3.2–3.3 and Theorem 3.4) is careful, and I traced the multiplicity argument; it works. Also new and useful: the classification of all degree-3 moves in Proposition 4.4 and the explicit lattice basis from those moves in Theorem 4.6. That is a clean, self-contained result and a practical handle for sampling algorithms. The connection to Lawrence liftings and Graver bases is standard, and I see no circularity.\n\nThe soft spots, in order of size. First, the odd-Δ case of Theorem 3.5 is asserted without proof: 'the primitive moves of A_{Δ−1} are also primitive moves for B_Δ.' The stress-test note is right that the claim is valid — the support of u_{Δ−1} only involves columns indexed by pairs from {1,…,Δ−1}, and the extra rows of B_Δ vanish on those columns — but the paper should prove it. As written, a reader has to stop and fill in a nontrivial one-liner. That's a revision, not a flaw.\n\nSecond, the RL section overstates what Table 1 shows. Many rows report a single sampled state (G(1000,0.02), Barabasi–Albert, Karate club), which is not 'performs well'; it's the algorithm failing to move. The paper does include an honest caveat about stochasticity just before the table, but the abstract and framing don't respect that caveat. The table also has no variance or run count. This section should be reframed as a preliminary demonstration on small cases, with the null results reported as null results.\n\nMinor: Theorem 4.6 has a typo ('ker Z(B'), and Theorem 3.5 uses 'A_4' where 'B_4' is meant. Not worth much.\n\nWho will get value: anyone working on Markov bases for graph spaces, especially with degree/curvature constraints, and people using algebraic statistics for network geometry. The lattice basis is the part I'd actually use; the lower bound is a genuine complexity marker.\n\nI'd send it to peer review. The referee should ask for the transfer proof and an honest revision of the RL claims, but the math is sound and the paper is a real contribution.","headline":"Correct quadratic lower bound and a clean degree-3 lattice basis; the odd-Δ transfer is unproved but valid, and the RL claims run ahead of the table.","tokens_in":18933,"tokens_out":3346,"would_cite":true,"duration_ms":31934,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["13P10","05C07"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that minimal rewiring moves for graphs with fixed degree and Forman-Ricci curvature sequences necessarily grow quadratically in size, and supplies a cheap lattice basis for sampling.","keywords":["Forman-Ricci curvature","Markov bases","Graver bases","Lawrence lifting","joint degree matrix","toric ideals","lattice bases","network geometry"],"falsifier":"For Delta=7 (or any odd Delta>=7), compute the Graver basis (the set of all primitive moves) of B_Delta with exact symbolic algebra and compare the largest degree of a primitive move with 2(floor(Delta/2)-1)^2+1; if the maximum degree is smaller, the odd-Delta part of the theorem is false.","tokens_in":18026,"feed_emoji":"🕸️","tokens_out":11427,"duration_ms":126593,"temperature":0.7,"pith_summary":"The paper studies the moves needed to walk between all simple graphs that share the same vertex-degree sequence and the same Forman-Ricci curvature frequencies. It shows that any minimal Markov basis for this problem must contain moves whose size (degree, the total weight moved) grows at least quadratically in the maximum degree Delta, by constructing explicit primitive moves that attain that growth. Since this rules out any compact description of the complete Markov basis, the authors give an explicit lattice basis made only of degree-three moves, so every move is an integer combination of cheap moves. They then show that an actor-critic reinforcement-learning sampler can use this lattice basis to explore fibers for graphs with larger maximum degrees than exact algebraic methods can reach. A sympathetic reader would care because Markov bases were the main bottleneck for sampling null graphs with prescribed curvatures.","feed_headline":"Minimal rewiring moves grow quadratically with graph max degree","feed_subtitle":"Sampling graphs with fixed curvature needs ever-larger moves; a degree-3 lattice basis keeps it feasible.","key_machinery":"The central object is the matrix B_Delta, whose rows encode, for each vertex degree and each curvature value (endpoint degree sum), the counts of a graph's joint degree matrix; vectors in its kernel are exactly the candidate rewiring moves. The paper works with the Lawrence lifting Lambda(B_Delta), the standard slack-variable extension that restricts moves to those realizable by simple graphs. The key structural fact is that the unique minimal Markov basis of a Lawrence lifting coincides with the Graver basis of the original matrix, so finding indispensable moves reduces to finding primitive moves of B_Delta. The paper's explicit move u_Delta (Equation 5, with parity-dependent coefficients a","core_discovery":"The central claim is that the algebraic complexity of sampling is unavoidably high: Theorem 3.5 constructs, for every Delta >= 4, a primitive move u_Delta in the kernel of B_Delta of degree 2(floor(Delta/2)-1)^2+1, and Corollary 3.6 lifts it to an indispensable move of degree 4(floor(Delta/2)-1)^2+2 in the unique minimal Markov basis of the Lawrence lifting Lambda(B_Delta). This makes the degree of indispensable moves quadratic in the maximum degree. Balanced against that, Theorem 4.6 gives a lattice basis for B_Delta consisting entirely of degree-three moves b_ijkl, so the paper provides both a negative complexity result and a practical positive construction. On the experimental side, the a","pith_inferences":["The quadratic lower bound concerns indispensable moves of the minimal Markov basis; it does not by itself imply that individual fibers need moves of that size. One could test whether fiber-specific move sets of bounded degree connect typical fibers, which would soften the practical bottleneck.","The odd-Delta half of the main lower bound rests on an asserted transfer of primitivity from B_{Delta-1} to B_Delta that the paper does not prove; a direct check for Delta=7 or 9 would either close the gap or expose a counterexample.","The lattice-basis construction may generalize: any edge statistic defined by sums of endpoint degrees yields the same kind of column-sum constraints, so the same degree-three triangular moves could provide lattice bases for other pairs of degree/statistic constraints.","Since the RL sampler returns only lower bounds, one could compare its discovered fiber size with the exact fiber size for small Delta; agreement would indicate that learned moves capture the fiber, while disagreement would quantify the sampling gap."],"forward_implications":["Every minimal Markov basis for Lambda(B_Delta) must contain an indispensable move of degree at least 4(floor(Delta/2)-1)^2+2, so exact symbolic computation of the basis from scratch becomes infeasible as Delta grows.","Because the primitive move u_Delta has degree quadratic in Delta, any complete listing of primitive moves for B_Delta—and hence of Graver basis elements—must include moves that large; compact closed-form descriptions of the full Markov basis are out of reach.","The degree-three moves b_ijkl generate the entire integer kernel of B_Delta as a lattice, so every Markov move can be written as an integer linear combination of moves of degree three; this gives a practical building block for sampling algorithms.","The reinforcement-learning actor-critic sampler, using the lattice basis as its action set, can explore fibers for graphs with maximum degree up to 39, including dense joint degree matrices, in cases where exact algebraic basis computation does not terminate.","The number of sampled states produced by the RL sampler is a guaranteed lower bound for the size of the fiber, not an exact count."],"fun_headline_variants":["Quadratic move growth sidestepped by degree-3 lattice basis","Graph rewiring for curvature: quadratic hardness, degree-3 fix","Quadratic growth of indispensable moves beaten by degree-3 lattice","Sampling graphs with fixed curvature: quadratic moves, but degree-3 basis"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The quadratic lower bound for odd maximum degrees depends on the paper's unproved assertion that a primitive move for B_{Delta-1} is automatically primitive for B_Delta; if that transfer fails, the bound is only established for even Delta.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic move growth sidestepped by degree-3 lattice basis","Graph rewiring for curvature: quadratic hardness, degree-3 fix","Quadratic growth of indispensable moves beaten by degree-3 lattice","Sampling graphs with fixed curvature: quadratic moves, but degree-3 basis"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000738,"raw_usage":{"total_tokens":3113,"prompt_tokens":704,"completion_tokens":2409,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":448,"completion_tokens_details":{"reasoning_tokens":2333}},"tokens_in":448,"tokens_out":2409,"duration_ms":19403,"temperature":1.0,"reasoning_tokens":2333,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T18:06:43.601169+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For Delta=7 (or any odd Delta>=7), compute the Graver basis (the set of all primitive moves) of B_Delta with exact symbolic algebra and compare the largest degree of a primitive move with 2(floor(Delta/2)-1)^2+1; if the maximum degree is smaller, the odd-Delta part of the theorem is false.","supporting_citations":[],"review_version":1}