{"id":"6263f965-c798-462a-b448-05c6be6160c9","arxiv_id":"2411.17351","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper reports exhaustive lists of bi-regular cages for 24 parameter triples, improves the lower bound for ({4,5};7) from 66 to 69, and improves 122 upper bounds.","lead":"Scientists developed computer algorithms for finding the smallest graphs with vertices of two allowed degrees and no cycles shorter than a given length, producing new complete lists for 24 cases and better bounds for 122 more. The work is a step in the long-studied 'cage problem' of extremal graph theory, where even small improvements often require months of computation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exhaustiveness of biregGen at orders 66–68 rests on pruning rules whose correctness is not independently verified at that scale; an over-pruning bug would falsify the lower-bound claim.","rationale":"The strongest claims in the paper are computational exhaustiveness statements: the 24 exhaustive cage lists and the improved lower bound n({4,5};7) ≥ 69. Both require that biregGen neither misses graphs nor wrongly prunes valid partial graphs. The reader’s weakest-assumption analysis correctly identifies the pruning completeness at the exact tested orders as the main risk. My reading of the algorithm suggests the pruning rules are plausible and the coordinate-wise maximal m-placement argument is a necessary-condition argument that is likely sound; I did not find an internal inconsistency or a concrete counterexample. The paper also provides real supporting evidence: released code, reproducible data, checks against two independent generators on smaller orders, and a clean generalization of the gluing theorem. However, the proof of Theorem 2.4 is external, and the critical order-68 search was not cross-checked by any independent exhaustive method or machine-checkable certificate. That is a genuine epistemological gap rather than a demonstrated mathematical error. Because the authors disclose the limitation, provide substantial sanity checks, and the central construction appears coherent, the concern does not by itself overturn the verdict. It does justify keeping the confidence at moderate and, ideally, asking for an independent certificate of the headline lower bound before relying on it as a theorem. No verdict change is needed relative to the reader’s ACCEPT.","tokens_in":29294,"tokens_out":21220,"duration_ms":203292,"concrete_test":"Encode the existence of a ({4,5};7)-graph on 68 vertices as a SAT instance: one Boolean variable per possible edge, degree constraints forcing every vertex to have degree 4 or 5, and girth constraints forbidding all cycles of length less than 7. Solve with a complete SAT solver (e.g., CaDiCaL or Kissat) and validate the resulting unsatisfiability certificate in DRAT format with a certified checker such as drat-trim. If the certificate verifies, the nonexistence claim is settled independently of biregGen’s pruning rules. If a model is found, the paper’s improved lower bound is wrong.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper’s headline nonexistence claim — that there is no ({4,5};7)-graph on 66, 67, or 68 vertices — depends entirely on the completeness of the backtracking search in Algorithm 2 at exactly those orders. Completeness in turn depends on the pruning rules in Sections 2.2 and 2.3 never discarding a partial graph that could be completed to a girth-7 graph with degrees in {4,5}. The most delicate rule is the maximal m-placement pruning, which is justified by Theorem 2.4. Theorem 2.4 is not proved in the paper; its proof is delegated to the third author’s Master’s thesis [47]. The Appendix A sanity checks compare outputs with geng and multigraph only for much smaller orders and for cases with small graph counts; they do not exercise the search at n=68, where the computation took roughly 185 CPU days. A subtle off-by-one in the m-placement level computation for even girth, or an over-application of the coordinate-wise maximum argument, would not be caught by those smaller tests. No specific error is identified here, but this is the load-bearing point on which the improved lower bound and several exhaustive cage lists rest, and it is not independently certified at the critical scale.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies bi-regular cages, i.e. ({r,m};g)-graphs of minimum order. It presents three methods: (1) an exhaustive backtracking generator called biregGen, which leads to exhaustive lists of cages for 24 triples (r,m,g) and improves the lower bound for n({4,5};7) from 66 to 69; (2) constructions that start from r-regular graphs and improve 49 upper bounds; and (3) a generalization of a gluing theorem of Aguilar, Araujo-Pardo and Berman, yielding 73 further upper-bound improvements. The paper includes pseudocode, a GitHub repository with code and data, and an appendix with sanity checks against geng and multigraph for smaller orders.","tokens_in":29527,"tokens_out":18511,"duration_ms":155630,"significance":"If correct, the paper is a substantial contribution to the computational study of bi-regular cages. The exhaustive lists for 24 triples are new and provide a rich source of data; the improvement of the lower bound for n({4,5};7) from 66 to 69 is a concrete advance; and the 122 improved upper bounds, obtained through systematic constructions, are a valuable resource. The availability of code and the sanity checks against independent generators are strengths that support reproducibility. The main caveat is that the exhaustiveness of the generator at the critical orders is not independently verified, and the key pruning theorem is not proved in the paper.","major_comments":[{"comment":"Theorem 2.4, which gives the order of a bi-regular Moore tree in terms of the numbers of degree-m vertices on each level, is not proved in the paper; the proof is delegated to the third author's Master's thesis [47]. This theorem is the mathematical basis for the maximal m-placement pruning rule of Section 2.3, and therefore for the exhaustiveness of biregGen. The paper should include a complete, self-contained proof or at least a detailed derivation, because the current text gives only Observation 2.3 and a reference to an external thesis.","section":"Section 2.1, Theorem 2.4"},{"comment":"The improved lower bound n({4,5};7) ≥ 69 rests on the nonexistence of ({4,5};7)-graphs on 66, 67, and 68 vertices, as reported by the implementation of Algorithm 2. The sanity checks in Table 4 compare biregGen with geng and multigraph only for orders up to 29 (and for some cases up to order 20 with larger counts). These checks do not exercise the search at the critical orders 66–68, where one run alone took roughly 185 CPU days. An over-pruning bug or an implementation error that only manifests at larger orders would invalidate the lower-bound claim and some of the exhaustive lists. The authors should provide additional validation for these orders (for example, an independent generator, a formal completeness argument for the pruning rules, or a certificate that the search space was fully exhausted) or explicitly state this as a limitation.","section":"Section 2.5.2 and Appendix A"}],"minor_comments":[{"comment":"The sentence 'the largest ratio n({r,m};g)/|V_m| in the table is 0.231' is incorrect as stated: for ({3,4};5) the ratio n/|V_m| is at least 13/3 ≈ 4.33. The intended ratio is probably |V_m|/n, which for that triple is at most 3/13 ≈ 0.231. Please correct the wording.","section":"Section 2.5.1, first paragraph"},{"comment":"The condition 'if method was called with graph that is isomorphic with G then return' is informal. Please specify how the isomorphism test is performed (e.g., using nauty) and under what circumstances a previously processed graph is recognized, since this is important for the completeness of the enumeration.","section":"Algorithm 2, line 2"},{"comment":"Construction 3.1 says to add an edge between two different vertices of G_reg. For simple graphs this only works when the chosen vertices are non-adjacent; this condition should be stated explicitly.","section":"Section 3, Construction 3.1"},{"comment":"The two approximate algorithms for computing the maximum number of vertices and edges at a given pairwise distance are not described. Please provide at least a short outline or a reference, so that the reader can assess how conservative the resulting upper bounds might be.","section":"Section 4.1, last paragraph"},{"comment":"The notation 'BMT' and the level sets L_d, L_{d,k} are used extensively; a small diagram or a reference to Figure 1 would help the reader keep track of the root conventions for even versus odd girth.","section":"Throughout, Section 2"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the scope of the journal and the computational results are valuable. The main concern is the verifiability of the exhaustive search at the critical orders; the authors should be encouraged to provide a self-contained proof of Theorem 2.4 and additional validation for the orders 66–68, or at least a clear correctness argument for the pruning rules. The repository and sanity checks are positive factors that should be highlighted in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper is a genuine contribution to the cage problem. The new computational results are substantial: exhaustive lists of bi-regular cages for 24 triples, a new lower bound n({4,5};7) >= 69, 49 improved upper bounds from regular-graph-based constructions, and 73 more from a generalized gluing theorem. The constructions in Section 3 are simple but effective, and Theorem 4.2 is a clean extension of Aguilar-Araujo-Pardo-Berman with a cycle-length argument that holds up on inspection. The code and data are on GitHub, and the Appendix A sanity checks against geng and multigraph provide real evidence that the generator is correct at the tested scales.\n\nThe soft spot is exactly where the stress-test note lands: the nonexistence claim at orders 66–68 rests on the completeness of biregGen, which in turn rests on pruning rules whose correctness at that scale is not independently certified. Theorem 2.4's proof is delegated to a Master's thesis; that is a minor accessibility issue, since the formula is elementary and can be checked directly. More importantly, the sanity checks stop well short of n=68, where the search took 185 CPU days. That is a genuine limitation of computational papers of this kind, not a defect the authors hid. They also disclose the truncation of some construction runs and the use of approximate algorithms for large seed graphs. Given that the Moore-bound-style arguments back the pruning, and the generator matches independent generators on every tested case, I do not see a specific over-pruning bug. But the lower-bound claim is load-bearing and would be falsified by one.\n\nThe paper is for people working on cage constructions and computational extremal graph theory. It deserves a serious referee: the computational claims need checking and the bound tables need verification, but the material is important within the subfield and the presentation is honest. I would send it to review.","headline":"Solid computational paper that settles exact orders and counts for two dozen small bi-regular cage triples and improves many bounds; the exhaustive lower-bound claim rests on a well-documented search whose pruning correctness at the critical scale is not independently verified, but no concrete flaw is identified.","tokens_in":30060,"tokens_out":1836,"would_cite":true,"duration_ms":18758,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C07","05C35","05C85","68R10","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper's exhaustive generator determines all pairwise non-isomorphic ({r,m};g)-cages for 24 triples and shows no ({4,5};7)-graph exists on 66–68 vertices.","keywords":["bi-regular cages","cage problem","girth","exhaustive generation","backtracking algorithm","Moore bound","degree sequences","graph algorithms"],"falsifier":"Run an independent exhaustive generator or a SAT-based search for ({4,5};7)-graphs on 66, 67, and 68 vertices; finding even one such graph would immediately falsify the claimed lower bound of 69 and the completeness of biregGen for those orders.","tokens_in":29109,"feed_emoji":"🔍","tokens_out":9522,"duration_ms":67558,"temperature":0.7,"pith_summary":"The paper develops computational methods to find bi-regular cages, graphs of a fixed girth whose vertices have exactly two allowed degrees. Its main claim is that a new exhaustive backtracking generator, biregGen, determines all pairwise non-isomorphic ({r,m};g)-cages for 24 triples (r,m,g) that were previously unknown. Running this generator at orders 66, 67 and 68 produces no ({4,5};7)-graph, which raises the lower bound n({4,5};7) from 66 to 69. The paper also improves 122 upper bounds on cage orders: 49 via constructions starting from r-regular graphs, and 73 via a generalization of a gluing theorem for (r,g)-graphs. If the exhaustive claims are correct, these are exact new facts about small bi-regular cages, not merely heuristic bounds.","feed_headline":"Exhaustive cage search yields 24 lists and lifts ({4,5};7) bound to 69","feed_subtitle":"Complete census in 24 cases; no ({4,5};7)-graph on 66, 67, or 68 vertices.","key_machinery":"The central object is the bi-regular Moore tree (BMT), the analogue of the Moore tree for two degrees r and m. The argument's engine is Theorem 2.4, a closed formula for the order of a BMT in terms of the placement of degree-m vertices on its levels; this formula drives the maximal m-placement pruning rule and the distance-between-degree-m-vertices constraint. The exhaustive generator biregGen is a backtracking search that starts from a BMT augmented by isolated vertices and recursively adds edges, using these pruning rules plus an isomorphism check to guarantee it outputs each graph exactly once. For the upper-bound improvements, the constructions are: adding an edge to an r-regular graph (Construction 3.1), deleting non-adjacent edges and attaching a new vertex (Constructions 3.2 and 3.3), and identifying remote vertices of several (r,g)-graphs (Theorem 4.2).","core_discovery":"The central claim is that the backtracking algorithm biregGen, built on a bi-regular Moore tree and two new pruning rules, exhaustively generates all pairwise non-isomorphic ({r,m};g)-graphs of a given order for the 24 triples listed in Table 1, yielding the complete cage lists and the nonexistence of ({4,5};7)-graphs on 66, 67, or 68 vertices. The paper further claims that the generalized gluing construction (Theorem 4.2) and the regular-graph constructions improve 73 and 49 upper bounds, respectively, for n({r,m};g). The authors state these as proven computational results, subject to the correctness of the implementation and the completeness of the pruning rules.","pith_inferences":["If the completeness of the pruning rules holds at all orders, the same biregGen approach can be applied to other small open cases, though the paper notes the computational cost grows steeply (about 185 CPU days for order 68 alone).","The observation that degree-m vertices are never adjacent in any of the 24 cage lists suggests a possible structural theorem: for girth at least 5, no bi-regular cage has adjacent degree-m vertices; checking this on additional triples would be a natural next step.","The generalized gluing theorem may yield infinite families of bi-regular graphs with prescribed girth; the paper's approximate algorithms for finding many vertices and edges at pairwise distance could be refined into exact algorithms for larger orders.","The lower-bound claim could be independently checked by encoding the search for orders 66–68 as a SAT or constraint-solving problem; a satisfying assignment would refute the completeness claim."],"forward_implications":["The 24 exhaustive lists are established; for example, the unique ({3,4};10)-cage on 82 vertices is confirmed by biregGen.","The lower bound n({4,5};7) ≥ 69 holds: no ({4,5};7)-graph exists with 66, 67, or 68 vertices.","49 upper bounds on n({r,m};g) are improved by constructions from r-regular graphs, using existing censuses as seeds.","The generalized gluing theorem improves 73 further upper bounds, bringing the total number of improved bounds to 122.","The same generator could settle n({3,8};8), since running it for order 74 would decide between the known bounds 74 and 75."],"supporting_citations":[{"why":"Base backtracking algorithm for (r,g)-graphs that biregGen extends to two-degree graphs.","marker":"[32]"},{"why":"Supplies the pruning rule used to eliminate edges that would violate girth constraints.","marker":"[23]"},{"why":"Provides the even-girth lower bounds and the distance-between-degree-m-vertices pruning rule.","marker":"[7]"},{"why":"Gives lower bounds for even girth used in the pruning logic.","marker":"[3]"},{"why":"The theorem that Theorem 4.2 generalizes to all girths and more degree pairs.","marker":"[2]"},{"why":"Establishes existence of ({r,m};g)-graphs and covers the easy case g=4.","marker":"[13]"}],"fun_headline_variants":["Bi-regular cages: 24 new exhaustive lists and 69 bound","Cage algorithm: 24 complete lists, 122 upper bounds improved","Computational census: 24 bi-regular cage families found","New bounds for bi-regular cages from exhaustive search","Exhaustive generation finds 24 cage lists, lifts bound to 69"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exhaustive results rest on the pruning rules never discarding a graph that could be completed to a valid ({r,m};g)-graph, and since the nonexistence for orders 66–68 was only sanity-checked on smaller orders, an over-pruning bug confined to larger searches would invalidate them.","fun_headline_variants_meta":{"raw":{"variants":["Bi-regular cages: 24 new exhaustive lists and 69 bound","Cage algorithm: 24 complete lists, 122 upper bounds improved","Computational census: 24 bi-regular cage families found","New bounds for bi-regular cages from exhaustive search","Exhaustive generation finds 24 cage lists, lifts bound to 69"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000523,"raw_usage":{"total_tokens":2538,"prompt_tokens":962,"completion_tokens":1576,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":578,"completion_tokens_details":{"reasoning_tokens":1485}},"tokens_in":578,"tokens_out":1576,"duration_ms":9739,"temperature":1.0,"reasoning_tokens":1485,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:13:34.960666+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an independent exhaustive generator or a SAT-based search for ({4,5};7)-graphs on 66, 67, and 68 vertices; finding even one such graph would immediately falsify the claimed lower bound of 69 and the completeness of biregGen for those orders.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Base backtracking algorithm for (r,g)-graphs that biregGen extends to two-degree graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the pruning rule used to eliminate edges that would violate girth constraints."},{"cited_title":"Araujo-Pardo, G","cited_arxiv_id":null,"evidence_quote":"Provides the even-girth lower bounds and the distance-between-degree-m-vertices pruning rule."},{"cited_title":"Araujo-Pardo, C","cited_arxiv_id":null,"evidence_quote":"Gives lower bounds for even girth used in the pruning logic."},{"cited_title":"Semicubic cages and small graphs of even girth from voltage graphs","cited_arxiv_id":"2305.03290","evidence_quote":"The theorem that Theorem 4.2 generalizes to all girths and more degree pairs."},{"cited_title":"Chartrand, R","cited_arxiv_id":null,"evidence_quote":"Establishes existence of ({r,m};g)-graphs and covers the easy case g=4."}],"review_version":1}