{"id":"a4c5d80f-e313-42a8-a4fb-82b2cd9fbeed","arxiv_id":"2511.07247","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"New computational constructions give new record upper bounds for n(k,g) in 11 cases, including n(4,10) ≤ 320, n(3,16) ≤ 936, and n(3,17) ≤ 2048.","lead":"These authors used four complementary computer search methods to find smaller regular graphs with no short cycles than anyone had found before, in 11 cases of the classic 'cage problem.' The standout bound drops the best known size of a 4-regular girth-10 graph from 384 to 320 vertices.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"All eleven bounds rest on computational certificates that are not independently re-verified in the preprint; a bug in the girth/completion verifier could invalidate the affected bound.","rationale":"The paper's main mathematical architecture is sound: explicit graphs, if valid, directly imply the eleven upper bounds; the lift framework is standard; the excision sets are carefully described and coherent with the known Moore cages used as starting graphs. The strongest internal support is the validation suite—disabling individual prunes reproduces the same lifts, and BTA matches three external generators on smaller instances. However, none of that independently re-certifies the final large graphs, and the manuscript explicitly sends readers to an external repository for the certificates. This is exactly the reader's weakest assumption, and it is load-bearing because a single verifier bug could invalidate one or more bounds. The concrete test suggested above would settle the concern: if the independent checks pass, the conditional can be lifted; if not, the affected bound is unsupported. I therefore see no reason to move the reader's CONDITIONAL verdict, just a clear path to upgrade it.","tokens_in":18437,"tokens_out":15025,"duration_ms":161505,"concrete_test":"Download the eleven certificate graphs from https://github.com/AGT-Kulak/smallRegGirthGraphs and verify each with an independent tool: compute the degree sequence, the order, and the exact girth using a different implementation (e.g., SageMath's girth() or a from-scratch cycle-enumeration script), and check that the results match the stated (k,g). For the five lift-based bounds, additionally reconstruct the lift from the posted base graph, group, and voltage assignment, recompute its girth using Proposition 1 with an independently written walk enumerator, and check isomorphism to the posted graph. For the six excision bounds, re-run the completion from the excised graph with an independent or at least freshly compiled version of the generator and verify the outputs. If all eleven pass, the central claim stands; if any fails, that bound must be withdrawn.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is an existence claim for eleven explicit graphs. In the preprint the machine-readable certificates live in an external repository, and the argument that each graph has the required order, degree, and girth depends on software: for the five lift-based bounds, on Proposition 1 together with the closed-walk enumerator of Algorithm 2 and the final girth routine from [29]; for the six excision bounds, on the external (k,g)-graph completion generator from [24,38] used to repair the excised graph. For the excision cases the paper reports 100 graphs each, but all 100 come from the same generator, so they are not independent confirmation. If any of these verifiers has an implementation bug—a missed short closed walk, an off-by-one in girth, acceptance of a non-regular or low-girth completion—the corresponding upper bound would be false even if the repository is populated. The paper's validation (disabling prunes and matching three independent generators on smaller instances) is reassuring but does not by itself certify the final large graphs. This is not a mathematical inconsistency; it is the load-bearing empirical weak spot.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper reports new upper bounds for the classical cage problem n(k,g) using computational search methods based on lifts of voltage graphs and on excision. The authors develop four algorithms: an exhaustive backtracking search over voltage assignments (BTA), a tabu search heuristic, a hill climbing heuristic, and an excision procedure that deletes a set of vertices from a known (k,g+1)-graph and completes the remainder to a k-regular graph of girth at least g. Applying these methods, they claim eleven improved upper bounds: n(3,16)≤936, n(3,17)≤2048, n(4,9)≤270, n(4,10)≤320, n(4,11)≤713, n(5,9)≤1116, n(6,11)≤7783, n(8,7)≤774, n(10,7)≤1608, n(12,7)≤2890, and n(14,7)≤4716. They also report improvements for edge-girth-regular, vertex-girth-regular, and (g+1)-cycle-free graphs, as well as 34 newly determined orders in (k,g)-spectra. The paper includes validation of the lift-based generators by disabling pruning optimizations and comparing with three independent implementations.","tokens_in":18704,"tokens_out":11500,"duration_ms":106917,"significance":"If the eleven bounds are correct, this is a significant contribution to the cage problem, several of whose best bounds have been stagnant for years. The improvement n(4,10)≤320, down from the 22-year-old bound 384, is particularly notable. The lift-based framework is methodologically interesting, and the validation strategy—disabling each pruning optimization and matching three independent external generators—is a commendable sanity check. The public repository with code and data is a strength. However, the central claim is purely existential, and the paper's own validation does not cover the excision-based part, so the reader must trust an external completion generator. The paper explicitly acknowledges that the certificates are in the repository rather than in the manuscript.","major_comments":[{"comment":"Six of the eleven new cage bounds (n(4,11)≤713, n(6,11)≤7783, n(8,7)≤774, n(10,7)≤1608, n(12,7)≤2890, n(14,7)≤4716) rely on the external (k,g)-graph completion generator of [24,38]. The completed graphs are not exhibited in the preprint, and §4.1 validates only the lift-based pipelines (disabling prunes, comparing with three generators); no cross-check of the completion generator is reported. The sentence 'even if an implementation would be incorrect, the certificates ... are available' does not resolve this: if the verifier is faulty, the certificates can be invalid. Please include the completed graphs (e.g., graph6/edge lists) for all six cases and provide/point to an independent verifier (order, degree, girth) with the results stated in the paper.","section":"§3.6 and §4.1"},{"comment":"The excision sets for the (4,12) and (6,12) cages are described informally: for (4,12) one vertex is removed from 'either N2(u)∩N4(v) or N4(u)∩N2(v)', and for (6,12) three vertices are removed from N3(u,v), without identifying the vertices. Fig. 3 is a schematic drawing, not a unique specification. This makes the constructions irreproducible without the external data. Please specify the exact excised vertex sets, or give the lists of vertices for the particular cages used.","section":"§3.6/Fig. 3"},{"comment":"The tabu search accepts neighbors with g_nbr = gmin−2 (Table 1), and the paper consistently speaks of 'minimum girth' rather than 'girth exactly g'. The final filter ISINTERESTING is not formally defined, so it is not clear from the paper that every reported graph has girth exactly the target g (a (k,g)-graph) rather than merely at least g (which would not prove the claimed upper bound on n(k,g)). Please state explicitly that each reported graph was verified to have girth exactly g, and describe the verification routine (e.g., the algorithm from [29]).","section":"§3.4.2 and §3.3"}],"minor_comments":[{"comment":"Typo: 'the the order of r'.","section":"§2"},{"comment":"The function name is written as NOTCANONICAL in Algorithm 1 but ISNOTCANONICAL in Algorithm 4; unify the notation.","section":"Algorithms 1 and 4"},{"comment":"For Figs. 4a, 4b, 4f the caption says group elements are 'numbered by their index as given by GAP's MultiplicationTable'; this is not self-contained. Include the group presentation or an explicit table of voltages.","section":"Fig. 4"},{"comment":"'for even degrees 8≤k≤14' is ambiguous; rephrase as 'for even k with 8≤k≤14'.","section":"§3.6"},{"comment":"The text says 100 graphs per excision case; please state whether all 100 were independently verified for degree and girth, or only by the completion generator itself.","section":"§4"}],"recommendation":"major_revision","confidential_remarks":"The paper is from a credible group and the lift-based part is carefully validated. My main reservation is the excision branch: six of the eleven central bounds depend on an external generator that is not cross-checked, and the completed graphs are not in the manuscript. I would recommend major revision requiring explicit certificates and independent verification for those cases. Once that is addressed, the paper should be a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know: this paper delivers eleven improved upper bounds for the classical cage problem, the most striking being n(4,10) dropping from 384 to 320, and it supports every claim with explicit graphs and public code. I largely trust the main results.\n\nThe constructions are the real news. Several of the old bounds had stood for 22 years, and n(4,11) and n(6,11) get their first non-trivial upper bounds. The method is not a single breakthrough but a sensible integration of lift-based exhaustive search, tabu search, hill climbing, and excision. The lift machinery is standard (Proposition 1 is a known characterization of girth in voltage lifts), and the authors use it carefully. The excision bounds are modest but real, obtained by modifying de Ruiter and Biggs' excised sets and completing the graphs with a known generator.\n\nThe paper also does something rare in computational extremal graph theory: it validates the implementation by disabling each pruning optimization and by matching three independent generators exactly. That is genuine evidence that the search programs are not silently missing or double-counting. The authors also post all graphs and source code, which is the right way to make existence claims credible.\n\nSoft spots, in proportion: the full verification of the final large graphs still rests on software — the closed-walk enumerator for the lift bounds and the completion generator for the excision bounds. The stress-test note is right that a bug in those verifiers could invalidate a specific bound, and the 100 graphs per excision case are not independent confirmation because they come from the same generator. But this is a standard risk in computational constructions, not a flaw in the paper's logic. The authors' validation mitigates it substantially, and the certificates are downloadable for independent checking.\n\nOne legitimate editorial gripe: the preprint mentions additional vgr upper bounds but omits them for \"space constraints,\" pointing to the repository instead. That is an odd choice in a preprint, where space is not a real constraint; those tables should be included or the claim stated more modestly. Also, some hyperparameters in the tabu search are empirically chosen, but that does not affect the correctness of the existence claims.\n\nWho this is for: anyone working on cage numbers or computational search for regular graphs, and to a lesser extent the network-design crowd that uses these graphs. It deserves a serious referee. The referee should verify a few of the certificates independently and ask the authors to put the missing vgr tables back in, but the central results look solid and publishable.","headline":"Eleven new cage upper bounds, including a big drop for n(4,10), backed by explicit graphs and strong validation; the main residual risk is software verification, not the mathematics.","tokens_in":19235,"tokens_out":1448,"would_cite":true,"duration_ms":18840,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C25","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"Eleven cage upper bounds fall, with n(4,10) dropping from 384 to 320.","keywords":["cage problem","extremal graph theory","lifts of voltage graphs","graph generation algorithms","regular graphs","girth","upper bounds","tabu search"],"falsifier":"Download the eleven posted graphs and run an independent, straightforward routine that checks vertex count, degree sequence, and shortest cycle; any discrepancy—especially any cycle shorter than the claimed girth or a vertex of wrong degree—would refute the corresponding bound. For the six excision-based bounds, re-running the (k,g)-completion on the excised (k,g+1)-cages must reproduce a k-regular graph of girth g on the claimed number of vertices.","tokens_in":18358,"feed_emoji":"🕸️","tokens_out":7185,"duration_ms":69157,"temperature":0.7,"pith_summary":"The paper's central claim is that four complementary construction methods—exhaustive and heuristic searches over voltage-graph lifts, a hill-climbing base-graph search, and an excision-and-completion technique—produce explicit regular graphs that improve the best known upper bounds for eleven (k,g) pairs of the classical cage problem. If the claimed graphs are correct, n(3,16) ≤ 936, n(3,17) ≤ 2048, n(4,9) ≤ 270, n(4,10) ≤ 320, n(4,11) ≤ 713, n(5,9) ≤ 1116, n(6,11) ≤ 7783, n(8,7) ≤ 774, n(10,7) ≤ 1608, n(12,7) ≤ 2890, and n(14,7) ≤ 4716. Several of these records had stood for 22 years, and the n(4,10) bound is reduced by 64 vertices, from 384 to 320. The same machinery yields new results for related problems: 21 upper bounds for edge-girth-regular graphs, 29 for vertex-girth-regular graphs, 6 for (k,g,g+1)-graphs, and 34 previously undetermined orders in (k,g)-spectra. A reader should care because exact cage numbers are known for only a handful of parameter pairs; each improved bound tightens the gap between the Moore lower bound and the smallest known construction.","feed_headline":"Eleven cage upper bounds improved, n(4,10) falls to 320","feed_subtitle":"Voltage-graph lifts and vertex excision shave 64 vertices off the long-standing (4,10) cage bound and break 22-year-old records.","key_machinery":"The central construction is the lift of a base graph by a finite group: a small voltage graph whose darts carry group elements, expanded into a covering graph with |Γ| copies of each base vertex. Girth of the lift is characterized by Proposition 1—the shortest closed non-reversing walk whose net voltage is the identity—which lets the search prune voltage assignments without constructing full lifts. Spanning-tree reductions, group and edge automorphisms, and incremental cycle checks cut the assignment space, while exhaustive backtracking and tabu search explore it, and a hill-climbing heuristic grows base graphs and voltages together. The second key mechanism is excision: removing a carefully","core_discovery":"The paper asserts that by combining voltage-graph lifts with excision, it constructs explicit k-regular graphs of girth g whose orders improve the best known upper bounds for n(3,16), n(3,17), n(4,9), n(4,10), n(4,11), n(5,9), n(6,11), n(8,7), n(10,7), n(12,7), and n(14,7). The most striking single result is n(4,10) ≤ 320, a 64-vertex drop from the long-standing 384 bound. The same computational campaign also settles 34 previously open membership questions in (k,g)-spectra and tightens many bounds for edge-girth-regular, vertex-girth-regular, and (k,g,g+1)-graphs. The graphs themselves are posted online, so each bound is accompanied by a certificate that can be independently checked.","pith_inferences":["The 64-vertex drop for n(4,10) suggests the true value may sit well below 384, possibly within a few dozen vertices of the Moore bound of 242; an exact determination could be attempted by extending these lift searches to orders 280–320.","The bipartiteness of the new even-girth graphs suggests that focusing lift searches on bipartite voltage assignments could be a cheap filter for other even-girth cages beyond these cases.","The excision improvements for even degrees 8–14 rely on the structural observation that (k,8)-cages have exactly k vertices at distance 2 from both of two distance-4 vertices; if this pattern extends to larger even k, the same excision-plus-completion recipe could improve n(k,8) for all even k."],"forward_implications":["Eleven upper bounds on n(k,g) are improved; most notably n(4,10) drops from 384 to 320, a 64-vertex improvement.","For n(4,11) and n(6,11), the new bounds are the first non-trivial upper bounds; previously only the generic inequality n(k,g) < n(k,g+1) applied.","The new (3,16) and (4,10) graphs are bipartite, offering additional support for the open conjecture that every even-girth cage is bipartite.","For even degrees 8, 10, 12, 14 and girth 7, the excision technique improves each upper bound by three vertices, showing a systematic saving over previous excision sets.","The variant results include 21 new edge-girth-regular, 29 new vertex-girth-regular, 6 new (k,g,g+1)-graph bounds (several tight), and 34 previously undetermined orders in (k,g)-spectra."],"fun_headline_variants":["Cage problem: 11 bounds improved, (4,10) drops to 320","Voltage lifts and excision crack cage bounds, 22-year records fall","New cages: 11 upper bounds tightened, n(4,10) cut by 64","Cage hunters slash 11 bounds, best (4,10) cage now 320 vertices","Four algorithms push cage bounds down, (4,10) bound shattered"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the software that verifies the order, degree, and girth of each posted graph (and completes the excised graphs) is correct; if any checker has a bug, a claimed upper bound could be false even though the graph file exists.","fun_headline_variants_meta":{"raw":{"variants":["Cage problem: 11 bounds improved, (4,10) drops to 320","Voltage lifts and excision crack cage bounds, 22-year records fall","New cages: 11 upper bounds tightened, n(4,10) cut by 64","Cage hunters slash 11 bounds, best (4,10) cage now 320 vertices","Four algorithms push cage bounds down, (4,10) bound shattered"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000218,"raw_usage":{"total_tokens":1376,"prompt_tokens":941,"completion_tokens":435,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":685,"completion_tokens_details":{"reasoning_tokens":325}},"tokens_in":685,"tokens_out":435,"duration_ms":5116,"temperature":1.0,"reasoning_tokens":325,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T23:04:27.185095+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Download the eleven posted graphs and run an independent, straightforward routine that checks vertex count, degree sequence, and shortest cycle; any discrepancy—especially any cycle shorter than the claimed girth or a vertex of wrong degree—would refute the corresponding bound. For the six excision-based bounds, re-running the (k,g)-completion on the excised (k,g+1)-cages must reproduce a k-regular graph of girth g on the claimed number of vertices.","supporting_citations":[],"review_version":1}