{"id":"54c4ece7-b2b5-47e4-a863-e9b30825e014","arxiv_id":"2511.21144","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Girth-diameter cages of fixed degree and girth have order growing at a rate between M(k,g)/g and n(k,g)/g, this ratio is computable in finite time, and new exact orders include (3;4,d), (3;5,d), and a (3;7,35)-cage on 136 vertices.","lead":"For graphs with fixed degree k and no cycles shorter than g, the paper determines how the minimum number of vertices grows with the diameter d: asymptotically it sits between the Moore bound divided by g and the known cage order divided by g. It also computes exact smallest orders for several new cases, including a 136-vertex cubic graph of girth 7 and diameter 35.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Strictness of the lower bound in Theorem 1 depends on an unpublished generator; a missed graph would invalidate f(3,7)>22/7, so the 'neither bound sharp' clause is unverified.","rationale":"I read the paper looking for a mathematical flaw in the asymptotic ratios. The lower-bound counting (Proposition 1) and the upper-bound construction (Proposition 3) both hold up: the windowed sums are justified by the girth condition, and the even-k cap works because subdividing an edge does not reduce endpoint degrees. The computability proof in Theorem 2 is somewhat high-level but not central to the ratio statement. The place where the central claim is least secure is exactly where the reader located it: the strict inequality f(3,7)>22/7 in Proposition 4. This is the only witness for the 'lower bound is not sharp' half of Theorem 1, and its proof depends on an exhaustive enumeration by an unpublished program. The Appendix is honest about using multigraph, but the absence of source, parameters, or a certificate means a skeptic cannot tell whether the enumeration is complete. That is not an ad hominem against the authors; it is a standard verification gap for a computational step that carries a load-bearing part of the theorem. The reader's CONDITIONAL verdict is appropriate. I would not change it: the mainstream inequalities remain proven, and the paper provides a GitHub repository and sanity checks for its main algorithm, but the strictness claim needs an independent confirmation before full acceptance.","tokens_in":20194,"tokens_out":21687,"duration_ms":221118,"concrete_test":"Independently re-enumerate all connected graphs with 22+α vertices for α∈{2,3} that satisfy the Appendix A boundary degree conditions (vertices in the first boundary level have degree 0,1,2, at least one with degree ≥1; vertices in the last boundary level have degree ≤3, at least one with degree <3), have girth at least 7, and pass the distance filter 'every vertex of degree <3 has a vertex at distance ≥7'. Use a different exhaustive generator, e.g., nauty's geng with exact degree-sequence constraints or a fresh canonical backtracking search, and confirm the survivor count is zero for both α. Also request the multigraph source from Brinkmann and compare counts on the same degree sequences.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The analytic core of Theorem 1 (Propositions 1–3) appears sound: the sliding-window counting in Proposition 1 is a legitimate tree-counting argument, and the even-k upper-bound construction in Proposition 3 works because subdividing an edge in the terminal copy of M leaves the two endpoint degrees at k, so identifying the degree-2 subdivision vertex with the degree-(k−2) terminal wr restores k-regularity. The load-bearing weakness is Proposition 4's proof that f(3,7)>22/7. The case |N_{i+j}|=1 is handled analytically, but α=2 and α=3 are discharged only by 'computer verification' in Appendix A. That verification uses multigraph, an unpublished generator by Brinkmann, with no public source, parameter files, or certificate; the description of the degree sequences and filter is too coarse to reproduce independently. If multigraph missed any connected graph satisfying the stated degree-sequence/girth constraints and the distance filter, then 'no such G′ exists' could be false. In that event f(3,7)=22/7 is not ruled out, and the 'neither bound sharp' clause of Theorem 1 loses its only lower-bound witness. This is a genuine correctness risk for the central claim, not merely a style or reproducibility preference.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies (k;g,d)-cages, smallest k-regular graphs of girth g and diameter d, and the asymptotic slope f(k,g) of the cage order as d → ∞. Theorem 1 asserts M(k,g)/g ≤ f(k,g) ≤ n(k,g)/g, and that neither inequality is sharp for all pairs. The lower bound comes from a neighbourhood-counting argument (Prop. 1), the upper bound from gluing modified copies of a cage (Prop. 3), and the non-sharpness from f(3,7) > 22/7 together with f(4,7) < n(4,7)/7 (Prop. 4). Theorem 2 states that f(k,g) is computable in O_{k,g}(1) time via 'repeatable graphs'. The paper also determines n(3;4,d) and n(3;5,d) with exact cage counts, and describes an exhaustive generation algorithm used to determine n(k;g,d) for 177 triples, 107 of them new, including a (3;7,35)-cage of order 136.","tokens_in":20430,"tokens_out":34229,"duration_ms":335638,"significance":"If correct, Theorem 1 gives a clean asymptotic linear-order result for a recently introduced extremal problem and connects the cage and degree-diameter worlds; Theorem 2 is a neat finiteness result. The neighbourhood-counting lower bounds and the gluing construction in Propositions 1 and 3 are elegant, and the paper provides executable code for its main generator together with sanity checks against GENREG and the literature. However, the strictness clause of Theorem 1 rests on a computational verification using an unpublished generator with no public certificate, the exact-count Propositions 7 and 9 are far too compressed (and one displayed formula does not parse algebraically), and the initial-graph description of the generation algorithm is ambiguous. These issues are fixable but currently prevent full verification of the paper's central and advertised claims.","major_comments":[{"comment":"The proof of f(3,7)>22/7 is the only lower-bound non-sharpness witness in Theorem 1. It is discharged by exhaustively generating graphs with 'multigraph', an unpublished generator by Brinkmann. The appendix gives no public source code, no parameter files, no exact list of the degree sequences tested, and no certificate of exhaustiveness. The description 'we determined each degree sequence' and a 'simple filter program' is not reproducible. If the generator missed any graph satisfying the stated constraints, the conclusion f(3,7)>22/7 is not established and the 'neither bound sharp' clause of Theorem 1 loses its only lower-bound witness. The authors should either make the verification fully reproducible (code, inputs, outputs/certificates) or replace it by an independent analytic or certified proof.","section":"Prop. 4 / Appendix A"},{"comment":"The exact cage counts are stated after very compressed case analyses. In Prop. 7, the d≡0 (mod 4) formula is not supported by the displayed calculation: as printed, ⌊(d−4)/8⌋+(3+1)(d−4)/8+(1+3)(5+2)+(3+2+2) evaluates to 42 for d=16, whereas the stated right-hand side 27+d+⌊(d−4)/8⌋ evaluates to 44. Either the expression or the formula is a typo. More generally, the enumerated 'possibilities for the end block' and the counts in Prop. 9 (e.g., 60 options, 112, 66) are asserted without derivations. If these counts are part of the contribution, the case analysis must be written out or accompanied by a verifiable certificate.","section":"§4.1, Props. 7 and 9"},{"comment":"The paper says it 'starts from the tree T of order M′(k;g,d) corresponding to Proposition 1'. For d>2t, the lower bound M′ is the sum of disjoint Moore trees in consecutive layers, not a connected tree. If makeTree returns a connected tree of that order, it need not be a subgraph of every (k;g,d)-graph, so the exhaustive generation would not be exhaustive; if it returns a forest, the pseudocode and text should say so and prove the forest is contained in every target graph. As written, the exhaustiveness claim underlying the 107 new exact orders, including the (3;7,35) case, is not fully supported.","section":"§4.2, Algorithms 1–2"}],"minor_comments":[{"comment":"The generator used in Appendix A only enumerates connected graphs. The graph G′ is indeed connected under the equality conditions in Prop. 4, but this is not stated or proved; it should be made explicit so that the restriction to connected graphs is justified.","section":"Appendix A"},{"comment":"The pigeonhole step in the proof of Theorem 2 is terse. Please spell out that one takes a shortest interval between two equal g-window types; this bounds the length of the repeatable subgraph and gives a finite set of possible ratios, which is needed for the positive gap c>f(k,g) in the removal argument.","section":"§3, Theorem 2"},{"comment":"The phrase 'u disjoint from at least one shortest cycle' is ambiguous. Since the construction's correctness depends on the distance between the two new vertices v and w being at least g, please state explicitly how this condition ensures that distance.","section":"Prop. 3"},{"comment":"The definition of f(k,g) as the smallest constant with n(k;g,d) ≤ f(k,g)d + O_{k,g}(1) should explicitly say 'for all sufficiently large d' to avoid ambiguity about the constant depending on k and g.","section":"Introduction"},{"comment":"In Table 4, entries such as '(3;7,7)' report '≥1' cages; this is not an exact count. The caption already indicates this, but it would help to state in the text that the algorithm did not exhaustively count cages in those rows, only determined the order.","section":"Table 4"}],"recommendation":"major_revision","confidential_remarks":"The analytic core of the paper appears plausible and significant, but the strictness clause of Theorem 1 is not independently verifiable as submitted because it relies on an unpublished generator without certificates. The exact-count Propositions 7 and 9 also need careful checking; the Prop. 7 d≡0 formula may indicate a real error rather than a mere typo. I would not reject, but the paper should not be accepted until these points are resolved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The main result is Theorem 1: f(k,g) is sandwiched between M(k,g)/g and n(k,g)/g, and neither bound is sharp for all pairs. The analytic arguments for the bounds (Prop 1–3) are clean and I couldn't find a hole. Theorem 2, saying f(k,g) is computable in constant time for fixed k,g, is a nice theoretical contribution. The computational part is real: exact n(3;g,d) for g=4,5, counts, and 107 new triples, with code and data on GitHub and House of Graphs. That's a lot of reproducible work.\n\nNow the soft spot. The strictness of the lower bound for (3,7) — the only witness that the lower bound isn't always sharp — relies on a computer verification in Appendix A that uses multigraph, an unpublished generator by Brinkmann. There's no public source, no parameter files, no certificate. If that generator missed a connected graph with the stated degree sequences and girth/distance constraints, then f(3,7)=22/7 is not ruled out, and Theorem 1's 'neither bound sharp' clause loses its lower-bound witness. This is a genuine gap, not a style quibble. The authors need to either provide the artifact or replace the verification with a more transparent and independently checkable enumeration. The upper-bound witness for non-sharpness (f(4,7) 22/7 is false.","tokens_in":20041,"feed_emoji":"🕸️","tokens_out":6953,"duration_ms":55901,"temperature":0.7,"pith_summary":"The paper establishes that for any fixed degree k and girth g, the order n(k;g,d) of a smallest k-regular graph of girth g and diameter d is asymptotically f(k,g)·d + O(1), where f(k,g) is a constant sandwiched between M(k,g)/g and n(k,g)/g. This converts an open extremal problem into a linear asymptotic with a computable slope: Theorem 2 says f(k,g) can be determined in constant time for fixed k,g. The paper also proves exact formulae for cubic graphs of girth 4 and 5, and computationally determines 107 previously unknown exact orders, the largest being a (3;7,35)-cage of order 136. A reader should care because this connects the two major extremal problems — the Cage Problem and the Degree Diameter Problem — and gives a precise prediction for a whole family of graphs that was previously unstudied.","feed_headline":"Cage order grows linearly with diameter, slope between two bounds","feed_subtitle":"For any fixed degree and girth the asymptotic ratio is now computable in constant time.","key_machinery":"The lower bound comes from a neighbourhood-counting argument: in any (k;g,d)-graph, pick two vertices at distance d and count the vertices in shells around them. The resulting bound M'(k;g,d) is sharp in several cases and implies f(k,g) ≥ M(k,g)/g. The upper bound is constructive: take a (k,g)-cage, remove a vertex or edge, and chain copies together with matchings so that the girth is preserved and the diameter grows linearly; this yields f(k,g) ≤ n(k,g)/g. For Theorem 2, the key object is a 'repeatable graph' — a finite slab of consecutive neighbourhoods whose two ends are isomorphic — which can be glued to itself to produce arbitrarily long graphs whose order-diameter ratio is fixed; a pig","core_discovery":"The central claim is Theorem 1: for all integers k,g≥3, M(k,g)/g ≤ f(k,g) ≤ n(k,g)/g, where f(k,g) is the infimum constant such that n(k;g,d) ≤ f(k,g)d + O_{k,g}(1). The theorem also asserts that neither inequality is sharp for all pairs — for instance f(3,7) > 22/7 and f(4,7) < n(4,7)/7. Theorem 2 strengthens this by showing that f(k,g) is computable in O_{k,g}(1) time via a search over finitely many 'repeatable graphs'. Alongside these asymptotic results, the paper determines n(3;4,d) and n(3;5,d) exactly for all d, counts the corresponding cages, and uses a new exhaustive generation algorithm to settle 107 additional triples (k,g,d), including a (3;7,35)-cage of order 136.","pith_inferences":["One could test whether the linear asymptotic extends to non-regular graphs by replacing the Moore bound with the classical lower bound for graphs of given minimum degree and diameter; the same shell-counting idea might yield an analogous ratio for the order-diameter problem for graphs of minimum degree.","The fact that f(k,g) is finitely computable suggests that the order-diameter tradeoff for girth-diameter cages is a 'local-to-global' property: the asymptotic is fully determined by the finite set of possible neighbourhood slabs, so a database of such slabs would settle any fixed (k,g) permanently.","The reproducibility gap — the strictness proof for f(3,7) depends on an unpublished generator — could be closed by a certificate-producing exhaustive search; until then, the numerical value f(3,7) is conditional on that generator's completeness.","The observed periodicity in the computed n(3;7,d) values (add 24 every 7 in d beyond a threshold) suggests that a general pattern of linear recurrences with period g may hold for all (3,g) pairs; verifying this for g=8 would be a natural next step."],"forward_implications":["For every fixed (k,g), the asymptotic order of girth-diameter cages is determined up to an additive constant once f(k,g) is computed; no further asymptotic search is needed.","The sandwich theorem gives a new invariant f(k,g) that measures how far a (k,g)-cage is from being diameter-optimal, independent of the additive constant.","When a (k, g)-Moore graph exists, n(k;g,d) is determined up to a constant, so the theorem resolves the asymptotic order of girth-diameter cages for g∈{3,4}, g=5 with k∈{2,3,7}, and g∈{6,8,12} for appropriate k.","The exact determination of n(3;4,d), n(3;5,d) and the count of cages gives a complete finite description of all extremal graphs in those families.","If Question 1 (every even-girth cage with d≤g is bipartite) is answered positively, the longstanding conjecture that every even-girth cage is bipartite follows directly."],"fun_headline_variants":["Cage order-diameter ratio has computable asymptotics","Exact cage orders for girths 4,5; 107 new cases settled","Constant-time bound for cage ratio, plus exact small-girth values","Largest settled cage: order 136 for (3,7,35)","New exhaustive algorithm settles 107 cage cases"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof that f(3,7) is strictly greater than 22/7 depends on an exhaustive search performed by an unpublished graph-generation program whose output is not independently verifiable; if that search missed a 24-vertex substructure satisfying the stated conditions, the strictness of the lower bound for (3,7) collapses.","fun_headline_variants_meta":{"raw":{"variants":["Cage order-diameter ratio has computable asymptotics","Exact cage orders for girths 4,5; 107 new cases settled","Constant-time bound for cage ratio, plus exact small-girth values","Largest settled cage: order 136 for (3,7,35)","New exhaustive algorithm settles 107 cage cases"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000414,"raw_usage":{"total_tokens":2000,"prompt_tokens":790,"completion_tokens":1210,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":534,"completion_tokens_details":{"reasoning_tokens":1119}},"tokens_in":534,"tokens_out":1210,"duration_ms":11061,"temperature":1.0,"reasoning_tokens":1119,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T20:05:00.872496+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Independently enumerate all connected graphs of order 24 with the degree sequences and neighbourhood constraints described in the paper's computer-verification appendix (vertices of degree 3 except for two small boundary sets). If any graph satisfies the required distance condition between the two boundary sets, the claimed inequality f(3,7) > 22/7 is false.","supporting_citations":[],"review_version":1}