Pith. sign in

REVIEW 3 major objections 5 minor 19 references

On the order-diameter ratio of girth-diameter cages

T0 review · 3 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The order of any girth-diameter cage grows linearly with its diameter, and the asymptotic slope is trapped between two classical bounds.

desk verdict The paper delivers a clean asymptotic framework for girth-diameter cages and substantial computational results; the main caveat is that one strictness claim rests on an unavailable generator. read the letter →

arxiv 2511.21144 v2 pith:FY7GVTEB submitted 2025-11-26 math.CO cs.DM

Stijn Cambie , Jan Goedgebeur , Jorik Jooken , Tibo Van den Eede This is my paper · ORCID
classification math.COcs.DM MSC 05C35
keywords girth-diametercagescageproblemdegreediameterextremalgraphtheoryMooreboundorder-diameterratioexhaustivegenerationrepeatablegraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Prop. 4 / Appendix A] 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.
  2. [§4.1, Props. 7 and 9] 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.
  3. [§4.2, Algorithms 1–2] 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.
minor comments (5)
  1. [Appendix A] 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.
  2. [§3, Theorem 2] 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.
  3. [Prop. 3] 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.
  4. [Introduction] 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.
  5. [Table 4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the bounds are derived by direct Moore-tree counting and explicit constructions; the repeatable-graph method is proved in-paper, and the computer-verification issue is a correctness/reproducibility risk, not a circular reduction.

full rationale

I walked the derivation chain: Proposition 1 gives a genuine lower bound on n(k;g,d) by summing Moore-bound contributions over overlapping neighbourhood windows; this yields M(k,g)/g <= f(k,g) without assuming f. Proposition 3 constructs an explicit infinite family from a (k,g)-cage whose order-to-diameter ratio tends to n(k,g)/g, giving f(k,g) <= n(k,g)/g; the target ratio is not an input. Proposition 4's strictness part uses a concrete external graph for (4,7), and for (3,7) relies on exhaustive generation in Appendix A. The latter is an unverified computational step (unpublished multigraph generator, no source or certificate), but it is not circular: a missed graph would falsify the claim, not make it true by construction. Section 3's repeatable-graph notion is said to be based on the authors' [4], but Definition 1, Proposition 5 and the extension lemmas are proved in this paper; Theorem 2's finite-enumeration argument reasons about the defining asymptotic property of f and does not reduce to the self-citation. The computational values are sanity-checked against GENREG and known results, and no fitted parameter is renamed as a prediction. The Appendix A completeness gap should be treated as a correctness/reproducibility risk, not as circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

Central claims rest on standard Moore-bound and girth facts and on computational exhaustiveness of three tools. No free parameters are fitted: f(k,g) is defined as an infimum and all constants in the counting formulas are derived from structural case analysis, not fit to data. No new physical or mathematical entities are postulated.

assumptions (3)
  • standard math For every k≥2 and g≥3 there exists a k-regular graph of girth g, and hence a (k,g)-cage (Sachs).
    Invoked throughout Prop 1 and Prop 3 to justify the existence of cages and the starting graphs for the constructions.
  • standard math The Moore bound M(k,g) is a lower bound on the order of every k-regular graph of girth g.
    Basis of all lower-bound formulas and of the inequality f(k,g) ≥ M(k,g)/g.
  • domain assumption The computational tools (Algorithm 1/2, GENREG, multigraph) are exhaustive on the ranges used.
    The 107 exact values and the Appendix A verification for f(3,7)>22/7 assume completeness; only limited cross-validation against GENREG is reported, not a formal certificate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the order-diameter ratio of girth-diameter cages." pith.science (2026). https://pith.science/paper/FY7GVTEB

@misc{pith2026251121144,
  author       = {Pith},
  title        = {Pith review of: On the order-diameter ratio of girth-diameter cages},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FY7GVTEB}},
  note         = {Machine review of arXiv:2511.21144}
}
abstract

For integers $k,g,d$, a $(k;g,d)$-cage (or simply girth-diameter cage) is a smallest $k$-regular graph of girth $g$ and diameter $d$ (if it exists). The order of a $(k;g,d)$-cage is denoted by $n(k;g,d)$. We determine asymptotic lower and upper bounds for the ratio between the order and the diameter of girth-diameter cages as the diameter goes to infinity. We also prove that this ratio can be computed in constant time for fixed $k$ and $g$. We theoretically determine the exact values $n(3;g,d)$, and count the number of corresponding girth-diameter cages, for $g \in \{4,5\}$. Moreover, we design and implement an exhaustive graph generation algorithm and use it to determine the exact order of several open cases and obtain -- often exhaustive -- sets of the corresponding girth-diameter cages. The largest case we generated and settled with our algorithm is a $(3;7,35)$-cage of order 136.

Figures

Figures reproduced from arXiv: 2511.21144 by the authors.

Figure 1
Figure 1. Illustration of the construction in Proposition 3 for (k, g) = (3, 4) and r = 3. Next, it is natural to wonder whether for all integers k, g ≥ 3, we have f(k, g) = M(k,g) g or f(k, g) = n(k,g) g . We will show that this is not the case [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. The example showing that f(4, 7) < n(4,7) 7 = 67 7 . 4 It can be downloaded from https://houseofgraphs.org/graphs/54041 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. A graph that is repeatable with respect to k = 3 and g = 4 (where vertices in N0 are shown larger). We now show that repeatable graphs indeed give rise to an upper bound on f(k, g). Here, we will make use of the following two near-trivial lemmas, that can be used to extend partial constructions to desired ones. Lemma 1. Given any sequence of natural numbers such that the sum is even, there is a (not necessarily conn… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Removing a repeatable subgraph (k = 3, g = 4, a = 1, b = 8, d = 9). Removing iteratively a repeatable subgraph of minimum length, if all ratios |Na∪...∪Nb−g| b−a+1−g would exceed f(k, g), one deduces a contradiction as follows. (This is similar to [4, page 3], with the…
Figure 5
Figure 5. Figure 5: Example of end block and gadget which are decoded by 133 and 1221. For d ≡ 2 (mod 4), we can combine one 1341 or 1332 with a 133 and some 1221s. For d ≡ 3 (mod 4), not mentioning the 1221s, one can have the combinations 133 + 122221 + 133, 1341 + 1341, 1341 + 1332, 133…
Figure 6
Figure 6. Figure 6: (3, 5, 13)-graph of order 34, easily modified to (3, 5, d)-graph for 10 ≤ d ≤ 14. By a careful analysis, one can also count the number of (3; 5, d)-cages. Proposition 9. The number of (3; 5, d)-cages for d ≥ 6 equals    d −  d 10  for d ≡ 1 (mod 5)…
Figure 7
Figure 7. Figure 7: A 2-connected non-bipartite (4; 4, 5)-cage. https://houseofgraphs.org/graphs/54022 on the House of Graphs [5]) is a 2-connected non-bipartite (4; 4, 5)-cage. Moreover, (k; g, d)-cages with d > g can never be (k, g)-cages since Sauer proved that every (k, g)-cage G sati…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 2 linked inside Pith

  1. [1]

    The Art of Discrete and Applied Mathematics8(3), Paper No

    Araujo-Pardo, G., Conder, M., García-Colín, N., Kiss, G., Leemans, D.: A note on girth-diameter cages. The Art of Discrete and Applied Mathematics8(3), Paper No. 3.06, 7 (2025)

    2025

  2. [2]

    Journal of Graph Theory23(2), 139–149 (1996)

    Brinkmann, G.: Fast generation of cubic graphs. Journal of Graph Theory23(2), 139–149 (1996)

    1996

  3. [3]

    Combinatorics, Probability and Computing4, 317 – 329 (1995)

    Brinkmann, G., McKay, B.D., Saager, C.: The smallest cubic graphs of girth nine. Combinatorics, Probability and Computing4, 317 – 329 (1995)

    1995

  4. [4]

    arXiv preprint arXiv:2502.08626 (2025)

    Cambie, S., Jooken, J.: Sharp results for the Erdős, Pach, Pollack and Tuza problem. arXiv preprint arXiv:2502.08626 (2025)

    arXiv 2025

  5. [5]

    Discrete Applied Mathematics325, 97–107 (2023), available at:https://houseofgraphs.org/

    Coolsaet, K., D’hondt, S., Goedgebeur, J.: House of Graphs 2.0: A database of interesting graphs and more. Discrete Applied Mathematics325, 97–107 (2023), available at:https://houseofgraphs.org/

    2023

  6. [6]

    Journal of Combinatorial Theory, Series B47(1), 73–79 (1989)

    Erdős, P., Pach, J., Pollack, R., Tuza, Z.: Radius, diameter, and minimum degree. Journal of Combinatorial Theory, Series B47(1), 73–79 (1989)

    1989

  7. [7]

    Electronic Journal of Combinatorics DS16, 48 (2013)

    Exoo, G., Jajcay, R.: Dynamic cage survey. Electronic Journal of Combinatorics DS16, 48 (2013)

    2013

  8. [8]

    Journal of Discrete Algorithms9(2), 166–169 (2011)

    Exoo, G., McKay, B.D., Myrvold, W., Nadon, J.: Computational determination of (3,11) and (4,7) cages. Journal of Discrete Algorithms9(2), 166–169 (2011)

    2011

Show all 19 references
  1. [9]

    arXiv preprint arXiv:2503.06466 (2025)

    Eze, L.C., Jajcay, R., Jajcayová, T., Závacká, D.: Theoretical and computa- tional approaches to determining sets of orders for(k, g)-graphs. arXiv preprint arXiv:2503.06466 (2025)

    2025 arXiv

  2. [10]

    Discussiones Mathematicae Graph Theory34(1), 187–191 (2014)

    Knor, M.: Smallest regular graphs of given degree and diameter. Discussiones Mathematicae Graph Theory34(1), 187–191 (2014)

    2014

  3. [11]

    Electronic Journal of Combinatorics4(2), R13 (1997)

    Lazebnik, F., Ustimenko, V.A., Woldar, A.J.: New upper bounds on the order of cages. Electronic Journal of Combinatorics4(2), R13 (1997)

    1997

  4. [12]

    In: 9th Annual ACM-SIAM Symposium on Discrete Algorithms

    McKay, B.D., Myrvold, W., Nadon, J.: Fast backtracking principles applied to find new cages. In: 9th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 188–191 (1998)

    1998

  5. [13]

    Journal of Symbolic Computation60, 94–112 (2014)

    McKay, B.D., Piperno, A.: Practical graph isomorphism, II. Journal of Symbolic Computation60, 94–112 (2014)

    2014

  6. [14]

    Journal of Graph Theory30(2), 137–146 (1999)

    Meringer, M.: Fast generation of regular graphs and construction of cages. Journal of Graph Theory30(2), 137–146 (1999)

    1999

  7. [15]

    Electronic Journal of CombinatoricsDS14(2012)

    Miller, M., Širáň, J.: Moore graphs and beyond: A survey of the degree/diameter problem. Electronic Journal of CombinatoricsDS14(2012)

    2012

  8. [16]

    Journal of the London Mathematical Society1(1), 423–429 (1963)

    Sachs, H.: Regular graphs with given girth and restricted circuits. Journal of the London Mathematical Society1(1), 423–429 (1963)

    1963

  9. [17]

    Sitzungsberichte Österreich

    Sauer, N.: Extremaleigenschaften regulärer Graphen gegebener Taillenweite I & II. Sitzungsberichte Österreich. Acad. Wiss. Math. Natur. Kl. (1967), s-B II, 176:9–25, 27-43

    1967

  10. [18]

    https://github

    Van den Eede, T.: Source code of the programgirthDiamGen. https://github. com/AGT-Kulak/girthDiamGen(2025), GitHub repository

    2025

  11. [19]

    Wong, P.K.: Cages—a survey. Journal of Graph Theory6(1), 1–22 (1982) On the order-diameter ratio of girth-diameter cages 21 A Details on computer verification used in Proposition 4 In this section we present some details of the computer verification we used in the proof of Pro...

    1982

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.