{"id":"6353fdf9-6667-4fdb-ab38-cb83c20f0a44","arxiv_id":"2607.17895","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The minimum spectral radius over weighted graphs with prescribed average degree is an explicit bi-regular expression, and the paper characterizes and counts when simple graphs attain it.","lead":"This paper finds the smallest possible spectral radius for graphs with a fixed average degree, by first solving an easier continuous version in which edge weights may be fractional. It then proves exactly when an ordinary simple graph can match that continuous answer, yielding partial progress on Hong's 1993 conjecture.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reducible case of Theorem 1.5 applies induction to components not in M_{n_i,e_i}; the equality chain is unjustified and the natural fix fails.","rationale":"The reader's weakest assumption identifies the same gap: the reducible case of Theorem 1.5 assumes component-level optimality and applies induction to components that may not belong to the required family. I examined whether this is merely a harmless omission and found it is load-bearing. The induction hypothesis is stated only for M_{n,e} with integer e, i.e., even total sum; components with odd total sums are not covered. Moreover, the equality max_i ρ(M_i)=max_i ρ1(d_i) does not follow from the induction hypothesis alone, because a component of a global minimizer is not shown to be a minimizer for its own total sum. A natural patch would be to strengthen the theorem to all integer total sums, but that stronger statement fails already for n=4, total sum 5: the degree sequence (2,1,1,1) forces ρ ≥ √7/2 ≈ 1.323 by the RMS bound, whereas ρ1(5/4) ≈ 1.303. Thus the proof gap is not cosmetic; it requires a genuinely new argument for disconnected minimizers with odd-sum components. I do not, however, find a counterexample to the theorem itself for even total sums; the irreducible case and Theorem 1.4 appear sound. The conditional verdict remains appropriate: the paper's central structural theorem and the resulting lower bound are not fully proven as written, but the claim is plausible and may be repairable. I therefore keep the reader's CONDITIONAL verdict unchanged.","tokens_in":25929,"tokens_out":33482,"duration_ms":286672,"concrete_test":"Rigorously solve the convex optimization problem for 4×4 symmetric non-negative matrices with integral row sums summing to 5 (e.g., via KKT conditions or verified interval arithmetic) to confirm τ(4,5) ≥ √7/2 > (√13−1)/2 = ρ1(5/4). This disproves the natural generalization of Theorem 1.5 to arbitrary integer total sums, showing that the reducible-case induction in §4 cannot be patched by the standard extension and that the proof as written is incomplete.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Theorem 1.5 (Section 4, paragraph 'Consider first the case where matrix M has a non-trivial decomposition...'), the chain ρ1(d) ≥ ρ(M) = max_i ρ(M_i) = max_i ρ1(d_i) ≥ ρ1(max_i d_i) ≥ ρ1(d) is used to conclude that every component has average degree d and hence, by induction, degree set {d1,d2}. Two things are unjustified. First, the induction hypothesis applies only to matrices in M_{n_i,e_i} with integer e_i, but a component's total sum s_i need not be even, so M_i may not belong to any such family. For instance, when (n,e)=(6,5), a plausible minimizer is the direct sum of two copies of the n=3, total-sum-5 matrix with degrees {1,2}; each component has odd total sum and lies outside every M_{3,e}. Second, the equality max_i ρ(M_i)=max_i ρ1(d_i) assumes each component is itself a minimizer for its own subproblem, which is not established. A natural repair—extending Theorem 1.5 to arbitrary integer total sums—is false: for n=4 and total sum 5, Proposition 1.2 gives ρ ≥ √7/2 ≈ 1.323, while ρ1(5/4)=(√13−1)/2 ≈ 1.303. Thus the reducible case is a genuine unpatched gap in the proof of the structural theorem and of the lower bound ρ(G_{n,e}) ≥ ρ1(2e/n).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the minimization of the spectral radius ρ(G) over simple n-vertex, e-edge graphs G_{n,e}. It relaxes the problem to symmetric non-negative n×n matrices with integral row sums and total sum 2e (family M_{n,e}), and proves (Theorem 1.5) that every minimizer in M_{n,e} must be bi-regular with degrees ⌊2e/n⌋ and ⌊2e/n⌋+1. This yields a closed-form lower bound ρ1(2e/n) on ρ(G_{n,e}). The paper also characterizes exactly when this bound is attained by a simple graph (Theorem 1.6), gives a number-theoretic condition for the ratio ν (Theorem 1.7), and counts the number E(n) of edge values for which the bound is tight (Theorem 1.8), proving E(n) grows linearly at worst and super-linearly on average. The proof of the bi-regular formula (Theorem 1.4) is complete; the induction for the general case handles the irreducible case through perturbation lemmas, but the reducible case relies on an induction hypothesis applied to components that may lie outside the induction domain.","tokens_in":26258,"tokens_out":19670,"duration_ms":162529,"significance":"The main results are significant if the proof of Theorem 1.5 can be completed. Theorem 1.4 is a clean, self-contained contribution to the weighted relaxation. The counting and characterization results (Theorems 1.6–1.8) are elegant and appear internally consistent conditional on Theorem 1.5. The paper gives explicit, parameter-free derivations and a new lower bound that improves on known Hoffman/RMS and entropy bounds. However, because the central structural theorem is used as the foundation for the lower bound and the enumeration, the unpatched gap in its proof currently blocks acceptance.","major_comments":[{"comment":"The equality chain ρ1(d) ≥ ρ(M) = max_i ρ(M_i) = max_i ρ1(d_i) ≥ ρ1(max_i d_i) ≥ ρ1(d) applies the induction hypothesis to each component M_i without verifying that M_i belongs to M_{n_i,e_i} for an integer e_i. A component's total sum s_i = n_i d_i can be odd, so M_i is not in any M_{n_i,e_i}; for example, when (n,e)=(6,5) a direct sum of two 3-vertex components with total sum 5 each has s_i odd. The equality max_i ρ(M_i)=max_i ρ1(d_i) is therefore unjustified. An attempted repair by extending Theorem 1.5 to all integral total sums is false: for n=4 and total sum 5, Proposition 1.2 gives ρ ≥ √7/2 ≈ 1.323, while ρ1(5/4) = (√13−1)/2 ≈ 1.303. This gap invalidates the proof of Theorem 1.5, and with it the lower bound ρ(G_{n,e}) ≥ ρ1(2e/n) and the structural conclusions used in Sections 6–7.","section":"Section 4, proof of Theorem 1.5, reducible case"},{"comment":"The claim that 'if d<1, then d_i ≤ 1 for all i' is false. For n=6, e=2, take components of sizes 2 and 4 with total sums 3 and 1; the first component has average degree 1.5 while the global average is 2/3 < 1. Thus even in the subcase d<1, the components need not have average degree at most 1, and the induction step as written does not apply. This is a separate obstruction in the same reducible-case argument.","section":"Section 4, proof of Theorem 1.5, d<1 case"}],"minor_comments":[{"comment":"The paragraph beginning 'The maximization problem has been extensively studied...' appears twice, with the second copy followed by Hong's bound; please remove the duplication.","section":"Section 1.1"},{"comment":"For e=0, the conclusion refers to M_{d1,n1,d2,n2} with n2=0, which is not a defined family (Theorem 1.4 assumes n2>0). Please handle e=0 explicitly.","section":"Theorem 1.5"},{"comment":"The notation ρ(G)=ρ_min(G) in the introduction is potentially confusing; consider using ρ_min consistently.","section":"Section 2"},{"comment":"The perturbation matrix E^{(ij)} includes diagonal entries -1; this is clear from Corollary 2.7 but the notation in Lemma 2.8 could be annotated to avoid confusion.","section":"Lemma 2.8 and Corollary 2.7"}],"recommendation":"major_revision","confidential_remarks":"The reducible-case gap is serious and may require substantial new ideas. If the authors cannot repair it, the paper's main claims are unsupported. I recommend treating this as a major revision with the expectation of a rigorous fix, not just minor edits."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this paper has a real new result — the exact minimum spectral radius for the weighted relaxation (Theorem 1.4), the structural characterization of weighted minimizers (Theorem 1.5), and the count of simple realizations via Pillai's function (Theorems 1.7–1.8). The perturbation machinery in Sections 2–3 is solid; the irreducible case of Theorem 1.5 is convincing. The bound genuinely improves the Hoffman RMS and entropy bounds in many regimes, and the enumeration result is a nice bonus.\n\nThe soft spot is the reducible case in the proof of Theorem 1.5. The proof decomposes a global minimizer into components and applies the induction hypothesis to each component as if it were a member of some M_{n_i,e_i}. But a component's total sum can be odd, so it need not belong to any such family. The induction hypothesis doesn't apply to it as stated. The stress-test note that flagged this added a numerical counterexample to the 'natural repair' — that example has the wrong ρ1 value (they used the wrong branch of formula (5)); for n=4, total sum 5, the bi-regular matrix actually attains ρ1 = 4/3. So the repair may well be true. Still, the proof as written has an unpatched gap: the chain max_i ρ(M_i) = max_i ρ1(d_i) is not justified without a lemma covering odd-sum components.\n\nAlso minor: the abstract's phrasing about Hong's conjecture could be read as claiming more for simple graphs than the paper actually establishes; the body handles this with Theorem 6.5, so it's merely a framing issue.\n\nNet: the central claims are very likely true, the machinery is reusable, and the mistakes are local. This deserves a serious referee; I'd ask the authors to add a proper lemma for the reducible case — e.g., prove the lower bound ρ(M_i) ≥ ρ1(d_i) for all integral-row-sum components, or handle odd-sum components by doubling or parity arguments — before accepting the structural theorem as fully proven.\n\nWho gets value: spectral graph theorists and extremal graph theorists, especially those working on degree-constrained spectral minimization. It's a good candidate for a reading group, and I'd cite it once the gap is closed.","headline":"The weighted relaxation is solved cleanly and gives real new bounds, but Theorem 1.5's reducible-case induction has a genuine gap around odd-sum components; worth refereeing with a requested patch.","tokens_in":26779,"tokens_out":18849,"would_cite":true,"duration_ms":143419,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C35","05C07","15A42"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper solves the weighted relaxation and shows the minimum spectral radius for an n-vertex, e-edge graph equals a closed bi-regular formula in the average degree 2e/n, and that any simple graph attaining it has degrees differing by at","keywords":["spectral radius","average degree","extremal graphs","weighted adjacency matrices","bi-regular graphs","Hong's conjecture","Pillai's arithmetical function","spectral radius lower bound"],"falsifier":"For a concrete pair such as n=6, e=7, numerically minimize the spectral radius over the convex set of 6×6 non-negative symmetric matrices with integral row sums summing to 14, and compare the optimum to ρ1(7/3); any value below ρ1 would refute Theorem 1.5. Alternatively, take a disconnected candidate minimizer for some larger (n,e) and check whether each component's spectral radius equals ρ1 of that component's own average degree; a failure would isolate the unproved component-optimality step.","tokens_in":25789,"feed_emoji":"🕸️","tokens_out":6787,"duration_ms":61711,"temperature":0.7,"pith_summary":"Given only the number of vertices and edges, how small can a graph's spectral radius be? This paper answers the question for a natural relaxation: allow non-negative symmetric adjacency matrices with integral row sums instead of only 0/1 entries. It proves that the minimum spectral radius in this wider family equals an explicit function of the average degree d=2e/n, achieved by weighted bi-regular graphs with degrees floor(d) and floor(d)+1. That closed-form expression gives a new lower bound for ordinary simple graphs, improving two previously known bounds. The authors then characterize exactly when a simple graph can realize the relaxed minimum: the parameters must satisfy four number-theoretic conditions, and in those cases the extremal graph's minimum and maximum degree differ by at most one, confirming Hong's 1993 conjecture for those configurations. Counting the number of such realizable edge counts shows it always grows at least linearly with n and is Θ(n log n) on average.","feed_headline":"Spectral radius minimum pinned by a bi-regular formula","feed_subtitle":"Weighted relaxation yields a closed-form lower bound; extremal simple graphs have degrees differing by at most one.","key_machinery":"The proof centers on the convexity of the spectral radius on symmetric matrices together with first-order perturbation theory (Corollaries 2.6 and 2.7): moving weight between two vertices of unequal Perron-eigenvector entries lowers ρ at rate −(xi−xj)^2/||x||^2. Repeated application forces any minimizer to have Perron entries constant on degree classes, an empty induced subgraph on the low-degree class, and a regular induced subgraph on the high-degree class, reducing the problem to a 2×2 matrix whose spectral radius is the closed form ρ0(d1,n1,d2,n2) = (1/2)[d2−d1(n1/n2) + sqrt(4d1²(n1/n2)+(d2−d1(n1/n2))²)]. Theorem 1.5 shows the average-degree relaxation collapses to this bi-regular formul","core_discovery":"The central claim is Theorem 1.5: among symmetric n×n non-negative matrices with integral row sums and total sum 2e, the smallest spectral radius is ρ1(2e/n), where ρ1 is defined from the bi-regular formula ρ0(d1,d2,ν) of Theorem 1.4 with d1=⌊2e/n⌋, d2=d1+1, and ν={2e/n}. Any minimizer is bi-regular: the degree-d1 vertices induce an empty subgraph and the degree-d2 vertices induce a regular subgraph. For simple graphs, this yields the lower bound ρ(G_{n,e}) ≥ ρ1(2e/n). Theorem 1.6 gives necessary and sufficient conditions for the existence of an ordinary graph in the extremal bi-regular family, and Theorem 1.7 extracts the list of average degrees for which the bound is attained by a discrete","pith_inferences":["Because E(n) averages Θ(n log n) out of ~n²/2 possible edge counts, the density of (n,e) pairs for which the relaxed bound is tight tends to zero; proving Hong's conjecture in full generality would require a strictly stronger lower bound than ρ1 for most pairs, so this paper delineates the boundary of the weighted relaxation.","The same convexity-plus-perturbation argument could be applied to other extremal spectral problems on weighted matrices, such as minimizing the spectral radius of the non-backtracking matrix under an average-degree constraint, as the authors themselves suggest.","The connectedness characterization (Theorem 6.5) provides explicit construction patterns (star, double-star, regular core with leaves) for connected graphs with prescribed spectral radius, which might be useful for designing expanders or graphs with controlled spectral gaps.","If the direct-sum induction step in the proof of Theorem 1.5 can be repaired, the structural rigidity (empty V1, regular V2) would hold for disconnected minimizers as well; until then, the structural conclusion is fully established only for irreducible minimizers."],"forward_implications":["For every n,e, ρ(G_{n,e}) ≥ ρ1(2e/n), which improves on both the root-mean-square and the entropy-based lower bounds in the covered cases.","If the bound is attained by a simple graph, its maximum and minimum degree differ by at most one, so Hong's conjecture holds for every average degree appearing in the list (3).","The four conditions of Theorem 1.6 give a complete, checkable criterion for when the weighted minimum is realized by an ordinary graph.","The number E(n) of non-trivial edge counts for which the relaxation is tight satisfies E(n) ≥ ⌊(3n−5)/2⌋, with equality exactly when n is prime or twice a prime, and E(n) grows super-linearly along an infinite family of highly composite, square-free integers.","For large average degree d, the gap between ρ1(d) and the trivial bound d decays as Δ²ν(1−ν) max(ν,1−ν)/d, where Δ=1 and ν is the fractional part of d."],"fun_headline_variants":["Bi-regular extremals set spectral radius floor","Hong's conjecture settled for specific degrees","Fractional graph problem solved exactly","Closed-form lower bound for spectral radius","Bi-regular formula delivers tight spectral bound"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"In the disconnected case of the proof of Theorem 1.5 (Section 4), the argument assumes every direct-sum component of a global minimizer is itself a minimizer for its own subproblem — a step the text does not justify, and which is delicate because a component's total edge weight may be odd and thus outside the family to which the induction hypothesis applies.","fun_headline_variants_meta":{"raw":{"variants":["Bi-regular extremals set spectral radius floor","Hong's conjecture settled for specific degrees","Fractional graph problem solved exactly","Closed-form lower bound for spectral radius","Bi-regular formula delivers tight spectral bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000687,"raw_usage":{"total_tokens":2924,"prompt_tokens":691,"completion_tokens":2233,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":435,"completion_tokens_details":{"reasoning_tokens":2170}},"tokens_in":435,"tokens_out":2233,"duration_ms":22242,"temperature":1.0,"reasoning_tokens":2170,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T16:43:27.975432+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a concrete pair such as n=6, e=7, numerically minimize the spectral radius over the convex set of 6×6 non-negative symmetric matrices with integral row sums summing to 14, and compare the optimum to ρ1(7/3); any value below ρ1 would refute Theorem 1.5. Alternatively, take a disconnected candidate minimizer for some larger (n,e) and check whether each component's spectral radius equals ρ1 of that component's own average degree; a failure would isolate the unproved component-optimality step.","supporting_citations":[],"review_version":1}