{"id":"76c486d0-e8d4-4526-a217-1ac495dedcdc","arxiv_id":"2509.01607","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A parallelized RL search over graphs produces three new counterexamples to conjectured Laplacian spectral radius bounds, alongside a speedup claim that is only weakly supported.","lead":"This thesis applies a parallel cross-entropy reinforcement learning method to search for graphs that break published upper bounds on the Laplacian spectral radius, reporting three new counterexamples. The core engineering changes are parallel model training and an action space that mutates the previous best graph; the evidence for the performance gains is thinner than the evidence for the counterexamples.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"New counterexamples in Appendix A are unverified; if the reward/conjecture formulas miscompute, the central outperformance claim loses its only novel support.","rationale":"The reader's weakest assumption is exactly the load-bearing point: the graphs in Appendix A must violate the named conjectures for the central claim to hold. I agree this is the least secure link. The paper provides no numerical verification, and the self-identified RNG risk makes the search pipeline suspect. A straightforward independent computation would settle it. Since the reader already rated the paper CONDITIONAL with this concern, my stress test does not change the verdict; it adds a concrete falsification test. I considered the performance-comparison weakness (no error bars, no counterexample found in the Figure 10 runs) but that is secondary: even if the timing claims are soft, the mathematical value of the paper lies in the new counterexamples, so verifying them is the first priority.","tokens_in":10634,"tokens_out":5957,"duration_ms":61719,"concrete_test":"Write an independent script that reads each adjacency matrix in Appendix A, constructs the graph Laplacian L = D − A, computes its largest eigenvalue μ (e.g., via numpy.linalg.eigvalsh), and evaluates each listed conjecture formula exactly for all vertices and edges using the definitions d_v and m_v. Verify μ > bound for all claimed counterexamples, especially the circled Conjectures 2, 32, and 61. Also cross-check the conjecture numbering and formula transcription against Brankov et al. (2006). If any circled inequality fails, the new-counterexample claim is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim—that the model outperforms the original implementation in the number of counterexamples found—rests on the circled entries in the Section 3 table (conjectures 2, 32, and 61). Appendix A provides adjacency matrices and conjecture formulas and asserts that 'the spectral radius of the Laplacian matrix of the graph is larger than the stated conjecture,' but it gives no computed spectral radius values and no comparison against the bounds. Because the conjecture formulas are complex maxima over degree and average-neighbor-degree terms, a transcription error (e.g., in the nested radicals of Conjectures 52/53 or the index mapping from Brankov et al.) or a bug in the reward computation would silently invalidate the claimed counterexamples. The paper itself flags implementation risk in Section 3: 'It is possible that during the modularization of the randomization function the effect of threaded models on the RNG seed was overlooked, leading to unexpected results.' If any of the circled inequalities fail, the model did not find new counterexamples and the outperformance claim in the number of counterexamples is unsupported. The time-complexity/runtime claim is secondary and not sufficient to validate the paper's stated contribution.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a parallelized, reinforcement-learning implementation (based on a cross-entropy method) for searching for counterexamples to 68 conjectured upper bounds on the Laplacian spectral radius of a graph, originally generated by Brankov et al. The authors reimplement Stevanovic et al.'s code, introduce a redefined action space that toggles bits of the current observation matrix, and run multiple models in parallel. The main claims are (i) the new implementation outperforms the original in both time per generation and in the number of counterexamples found, and (ii) the search discovers three new counterexamples, to Conjectures 2, 32, and 61, using four graphs listed in Appendix A. The paper includes adjacency matrices and conjecture formulas for these graphs but does not report any computed Laplacian spectral radius or bound values.","tokens_in":10910,"tokens_out":4822,"duration_ms":57563,"significance":"If the three claimed counterexamples are correct, the paper would make a modest but real contribution to extremal spectral graph theory: it would close three open conjectures from Brankov et al.'s list and demonstrate that a simple decentralized cross-entropy method can find graphs that standard local search misses. The code is publicly available, which is a strength for reproducibility. However, the verification of the counterexamples is entirely external to the text: the appendix asserts the inequalities but provides no numerical evidence. Since the search reward is defined as the spectral radius minus the conjectured bound, the discovery procedure is coherent and not circular, but an implementation error in either the spectral radius computation or the conjecture formula transcription would invalidate the central claim. The time-complexity comparison also lacks statistical detail. The paper's significance therefore hinges on an independent verification that is neither provided nor pointed to in the repository in enough detail.","major_comments":[{"comment":"The central novelty is the three circled entries in the table: Conjectures 2, 32, and 61 are marked with '◦', which the text defines as 'new counter-examples'. Appendix A provides adjacency matrices and expressions for the conjectured bounds, but it never gives the computed Laplacian spectral radius µ(G) for any of the four graphs, nor the numerical value of the conjectured bound. The appendix only states that 'the spectral radius of the Laplacian matrix of the graph is larger than the stated conjecture'. This is a load-bearing verification gap: the conjecture formulas are intricate maxima over degree and average-neighbor-degree terms (e.g., Conjectures 52/53 contain nested radicals), and the reward computation in the code uses the same formulas, so a bug in formula transcription or spectral radius evaluation would silently produce false positives. The paper even flags a possible RNG-see","section":"Section 3, Appendix A"},{"comment":"The performance comparison rests on 'the average of 15 runs of 400 generations', but no error bars, standard deviations, or significance tests are reported. The figure also appears to compare different numbers of parallel models with different per-model batch sizes (200 vs. 500), and the text says the 5-model version initially underperforms for that reason. The paper's concluding sentence claims superiority in 'time-complexity', but the runtime comparisons are described only qualitatively ('reduced the time to process a generation by up to a third') with no hardware or timing methodology. Moreover, the text acknowledges a possible bug in the randomization function's RNG seed handling, which could affect both the reward trajectories and the discovered graphs. This makes the performance claim hard to evaluate. Please provide per-run data, error bars, and a clear specification of what is be","section":"Section 3, Figure 10"},{"comment":"The paper's second stated contribution is the 'novel redefining of the action space' to XOR the model's action with the observation matrix. However, the experimental section does not isolate the effect of this change: the comparisons vary the number of parallel models and the initialization insertion percentage simultaneously. It is therefore unclear whether the observed improvements come from the parallelization, the new action space, the GELU activation, or the initialization strategy. In addition, Section 2.3 says the default hidden sizes are 72 and 12, while Figure 9's caption says 24 and 12; please reconcile this inconsistency. An ablation study (original action space vs. new action space, with parallelization held fixed) would strengthen the attribution of the claimed improvement.","section":"Section 2.1, Section 2.3"}],"minor_comments":[{"comment":"Typographical errors: 'Wagnar's approach' in the abstract and 'Stevonovic's' in the contributions section. The abstract also uses 'Wagnar' inconsistently with the title's 'Wagner'.","section":"Abstract/Introduction"},{"comment":"The table legend should be expanded. It is unclear what 'previously closed' means: presumably closed by Stevanovic et al., but the text should say so explicitly and cite the corresponding results. The symbol placement in the table is also hard to read; a clearer table with explicit columns for each graph would help.","section":"Section 3, Table"},{"comment":"The conjecture formulas are typeset without the inequality that defines them as upper bounds. For example, Conjecture 2 is simply listed as 'max 2m_v^2/d_v' with no '≤ µ(G)' or 'µ(G) ≤ ...'. Adding the full inequality would remove ambiguity and make the counterexample check transparent.","section":"Appendix A"},{"comment":"The claim that parallelization 'reduced the time to process a generation by up to a third' is not accompanied by any measurement details. Please specify the hardware, the timing methodology, and whether the comparison used identical hyperparameters.","section":"Section 2.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript reads like a thesis excerpt and is somewhat informal for a research paper. The main issue is not the method's originality but the lack of verifiable numerical evidence for the claimed new counterexamples. I would be willing to accept a revised version that includes a full verification table for Appendix A and a more rigorous statistical presentation of the performance comparison. If the authors can provide machine-checkable verification and the three counterexamples check out, the paper would be a useful contribution to the literature on automated counterexample search in spectral graph theory."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the real content here is the three circled entries in Table 1 — new counterexamples to conjectures 2, 32, and 61 from Brankov–Hansen–Stevanović. The RL engine is an incremental tweak of Stevanović's reimplementation: parallel threads plus an XOR action space so a fraction of each batch starts from the previous top observation. That is fine engineering, but not a methodological breakthrough. The counterexamples, if they check out, are the contribution.\n\nWhat the paper does well: it is honest. It gives adjacency matrices for four graphs, names which conjectures each graph kills, admits the 15-run averages have no error bars, and flags the possible RNG seed bug from threading. The repository is public. Nothing is hidden.\n\nWhere it hurts: the appendix never gives the Laplacian spectral radius or the bound value for any graph. You get an assertion that 'the spectral radius is larger than the stated conjecture' and a wall of formulas. A single transcription error in the nested radicals of, say, Conjecture 52 would silently kill a claimed counterexample. The stress-test note is right: this is the load-bearing assumption, and it is unverified in the text. The fix is trivial — print the numbers alongside the matrices — which makes the omission more annoying than fatal. The performance claim ('outperforms in time-complexity and number of counterexamples') rests on one experiment, one conjecture, and no error bars. The RNG caveat further weakens it. I would not hang much on that claim.\n\nBottom line: if the three counterexamples verify, this closes three small open problems from a 2006 automated conjecture paper. That's a legitimate, modest result. The method part is a reasonable incremental contribution. The paper deserves a serious referee, but the version that comes back should have a table of computed spectral radii and bounds, error bars on the timing/reward curves, and a clear statement about the RNG issue. I'd take it to a reading group as a good example of why verification matters in computer-assisted graph theory.","headline":"Three plausible new counterexamples to 2006 Laplacian-radius conjectures, but the paper makes you fetch a calculator to believe them.","tokens_in":11385,"tokens_out":2190,"would_cite":true,"duration_ms":25141,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","68T05","90C59"],"pacs":[],"model":"deepseek-v4-flash","headline":"A parallelized reinforcement-learning search over graphs finds more counterexamples to conjectured Laplacian spectral radius bounds, including three previously open cases, while running faster than the baseline.","keywords":["reinforcement learning","cross-entropy method","Laplacian spectral radius","graph theory","counterexamples","parallel search","action space","spectral bounds"],"falsifier":"Compute the largest Laplacian eigenvalue of each of the four adjacency matrices in Appendix A and evaluate the corresponding conjecture formula on that graph; if any graph's spectral radius does not strictly exceed its stated bound, the central claim fails. For the performance claim, re-run the comparison on multiple conjectures with fixed random seeds and measure wall-clock time and number of counterexamples found per run.","tokens_in":10537,"feed_emoji":"🎯","tokens_out":8081,"duration_ms":79147,"temperature":0.7,"pith_summary":"This paper tries to show that a parallelized reinforcement-learning search, based on the cross-entropy method, can find counterexamples to conjectured upper bounds on the largest eigenvalue of a graph's Laplacian matrix more efficiently and more successfully than earlier code. It reports four small graphs that falsify many of the 68 open bounds in a known automated-conjecture catalogue, including three bounds that had no previously known counterexample. The engine of the method is a policy network that learns to edit graphs with a bit-flip action space, seeded from the previous best graph, while multiple independent models explore different regions of graph space. If the reported counterexamples hold up, the paper both closes three concrete conjectures and demonstrates a reusable recipe for AI-assisted conjecture falsification in extremal graph theory.","feed_headline":"RL search disproves three Laplacian spectral bounds","feed_subtitle":"A parallel cross-entropy method beats prior code in speed and yield, with four graphs breaking dozens of open bounds.","key_machinery":"The central mechanism is the cross-entropy method: a policy network proposes graphs, the top 10% by reward update the network, and the top 5% are carried into the next generation. The reward is the graph's Laplacian spectral radius minus the conjectured bound, so ordinary graphs get negative rewards and a counterexample yields a positive one. Two modifications carry the argument: (1) multiple policy networks train in parallel on disjoint batches, and (2) the action is a bit-wise exclusive-or against the observation, so a portion of each batch starts at the previous generation's best graph and mutates it instead of constructing from the zero matrix. This second change is congruent to the old","core_discovery":"The paper claims that running several cross-entropy reinforcement-learning agents in parallel, with an action space redefined so an agent can mutate the previous best graph rather than build from zero, outperforms the prior single-agent implementation: it finds more counterexamples to conjectured upper bounds on the Laplacian spectral radius in less wall-clock time. It reports four graphs that falsify many of the 68 open bounds from an earlier automated-conjecture catalogue, including three bounds (conjectures 2, 32, 61) for which no counterexamples had been previously published. The decentralization is meant to escape the cross-entropy method's tendency to stall at local optima.","pith_inferences":["If independently verified, the three new counterexamples stand as a mathematical result independent of the reinforcement-learning framing; the method acts as a discovery tool rather than a proof generator.","The same parallel search could be pointed at other eigenvalue-based conjectures (adjacency spectral radius, normalized Laplacian, distance matrices) as long as a reward function can be defined, though the paper does not report such experiments.","The paper itself flags a possible random-number-seed artifact from threading; an ablation with fixed seeds across model counts would clarify whether the speedups are genuinely due to parallelism or to implementation details.","A controlled comparison with zero seeding of the top graph would isolate whether the quarter-of-batch seeding is the main driver of the performance gain, since the reported experiments do not vary that factor alone."],"forward_implications":["Three previously open conjectured upper bounds (numbers 2, 32, 61) from the cited catalogue are false, witnessed by graphs on 12 and 20 vertices; any repair of these bounds must accommodate these graphs.","The parallel, local-optimum-initialized cross-entropy method is faster and finds more counterexamples than the single-model baseline, making it a practical template for automated conjecture falsification in spectral graph theory.","The four reported graphs each serve as counterexamples to many distinct conjectures, showing that a single extremal graph can witness a cluster of similar bounds.","The redefined action space reduces to the original when starting from the zero matrix, so the observed gains come from parallel decentralization and seeding with the previous top graph rather than from the XOR formulation alone."],"supporting_citations":[{"why":"Supplies the original cross-entropy method for constructing graph-theory counterexamples; this work's starting point.","marker":"[1]"},{"why":"The re-implementation used as the performance baseline and the source of the previously known counterexample set.","marker":"[2]"},{"why":"The catalogue of 68 open conjectured upper bounds on the Laplacian spectral radius; provides the conjectures under test.","marker":"[4]"},{"why":"Defines the cross-entropy optimization algorithm that the paper's training loop implements.","marker":"[11]"},{"why":"Introduces decentralized cross-entropy training, which motivates running multiple models in parallel.","marker":"[12]"}],"fun_headline_variants":["Parallel RL breaks three Laplacian bounds","RL agent swarm topples spectral radius conjectures","New RL method finds graphs breaking three bounds","Parallel cross-entropy RL disproves open graph conjectures"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is that the four Appendix A graphs genuinely violate the listed conjectures and that the reported speedups are not artifacts of the threading-related random-number-seed behaviour the paper itself flags; an error in the eigenvalue computation, in transcribing the conjecture formulas, or in the RNG handling would collapse the central claims.","fun_headline_variants_meta":{"raw":{"variants":["Parallel RL breaks three Laplacian bounds","RL agent swarm topples spectral radius conjectures","New RL method finds graphs breaking three bounds","Parallel cross-entropy RL disproves open graph conjectures"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000416,"raw_usage":{"total_tokens":1894,"prompt_tokens":569,"completion_tokens":1325,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":313,"completion_tokens_details":{"reasoning_tokens":1266}},"tokens_in":313,"tokens_out":1325,"duration_ms":11726,"temperature":1.0,"reasoning_tokens":1266,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:21:16.488819+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the largest Laplacian eigenvalue of each of the four adjacency matrices in Appendix A and evaluate the corresponding conjecture formula on that graph; if any graph's spectral radius does not strictly exceed its stated bound, the central claim fails. For the performance claim, re-run the comparison on multiple conjectures with fixed random seeds and measure wall-clock time and number of counterexamples found per run.","supporting_citations":[{"cited_title":"Automated conjectures on upper bounds for the largest laplacian eigenvalue of graphs,","cited_arxiv_id":null,"evidence_quote":"The catalogue of 68 open conjectured upper bounds on the Laplacian spectral radius; provides the conjectures under test."},{"cited_title":"A tutorial on the cross-entropy method,","cited_arxiv_id":null,"evidence_quote":"Defines the cross-entropy optimization algorithm that the paper's training loop implements."},{"cited_title":"A simple decentralized cross-entropy method,","cited_arxiv_id":null,"evidence_quote":"Introduces decentralized cross-entropy training, which motivates running multiple models in parallel."}],"review_version":1}