Pith. sign in

REVIEW 2 major objections 4 minor 38 references

Improved lower bounds on the maximum size of graphs with girth 5

T0 review · 2 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read A hill-climbing search that seeds each order n with modified near-extremal graphs of neighboring orders improves the best-known lower bound on ex(n; {C3, C4}) for every n from 74 to 198 except 96 and 97, which it ties.

desk verdict A useful, checkable set of new lower bounds that mostly stands up, but the comparison table undercounts two known cage bounds and should be corrected. read the letter →

arxiv 2508.05562 v1 pith:RDTB45WR submitted 2025-08-07 math.CO cs.DM

Jan Goedgebeur , Jorik Jooken , Gwenaël Joret , Tibo Van den Eede This is my paper · ORCID
classification math.COcs.DM MSC 05C3505C85
keywords extremalgraphtheoryTuránnumbergirth5cageshill-climbingheuristiclocalsearchlowerboundsex(n{C3C4})
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

This paper aims to improve the best-known lower bounds on $ex(n;\{C_3,C_4\})$ — the largest number of edges in an $n$-vertex graph with no triangle and no 4-cycle (girth at least 5) — for every $n$ from 74 to 198, orders beyond the reach of exact computation. Its method is a randomized hill-climbing local search, descended from a heuristic built for finding cages, with one new twist: each order $n$ is seeded with graphs obtained by lightly modifying the best graphs already found for $n-1$ and $n+1$, so that good patterns propagate along the range over multiple passes. The paper claims this beats every previously known lower bound for 123 of the 125 orders, ties at $n=96,97$, and yields double-digit gains for larger $n$ (e.g., $n=164$ rises from 880 to 940 edges). If right, the results narrow the gap toward Erdős's conjectured asymptotic $ex(n;\{C_3,C_4\}) \sim \frac{1}{2}\sqrt{2}\,n\sqrt{n}$, and because every certificate graph is published, the bounds can be verified independently.

What carries the argument

Two mechanisms carry the argument. Algorithm 1 is a randomized local search: from a girth-5 seed graph of order $n$, it repeatedly adds a legal edge — one whose addition creates no triangle or 4-cycle — choosing with probability $p$ an edge maximizing $\deg(u)+\deg(v)$, otherwise a uniformly random legal edge; when stuck, it deletes a small random set of edges (recency-protected) and resumes. Algorithm 2 propagates: each order $n$ is initialized with graphs from $n-1$ and $n+1$, modified by one vertex addition or deletion; the initial pool has known extremal graphs to order 64 and small $(k,5)$-cages (orders 80, 96, 124, 126, 154, 156, 203). The legality check's girth test is described, not

What would settle it

Download the graph6 files from the paper's repository and verify each entry of Table 1 with an independent program: count vertices and edges, and test girth $\ge 5$ by checking that no vertex pair has two distinct length-$\le 4$ connecting walks (or enumerate cycles directly). If any listed graph has a triangle or 4-cycle, or a mismatched edge count, that row's claimed improvement collapses to the previous lower bound. A weaker informative check: re-run Algorithm 1 at a mid-range $n$ from random seeds and compare with the propagated-seed runs.

Watch

Extended reading notes

Core claim

The paper's discovery is computational: a small modification of a known local-search scheme yields record-size girth-5 graphs across a whole interval of orders. The central claim: for every $n \in \{74,\dots,198\}$ except 96 and 97, Algorithm 2 outputs an explicit $n$-vertex graph with girth at least 5 and more edges than the best previous lower bound (e.g., $n=164$: 880→940 edges). The runs also improve four upper bounds on the minimum order of bi-regular girth-5 cages, and the authors judge the bounds near-exact for $n\le 100$. The load-bearing part is propagation: near-extremal graphs of orders $n-1$ and $n+1$, modified by one vertex insertion or deletion, seed each hill-climbing trial.

Load-bearing premise

The reported graphs really are certificates — each has exactly $n$ vertices, exactly the listed number of edges, and no triangle or 4-cycle — which rests on the correctness of the girth check used for 'legal' insertions in Algorithm 1 and on faithful transcription of the seed graphs, since no pseudo-code for that check and no machine-verified certificate files appear in the paper.

Editorial extensions

If this is right

  • If the bounds are correct, Table 1 supplies explicit certificate graphs — for instance a 164-vertex girth-5 graph with 940 edges — that improve the previous record lower bound for 123 of the 125 orders in {74,...,198}.
  • The gap to the general upper bound (about $\frac{1}{2}n\sqrt{n}$ edges) narrows for every improved order, and the authors estimate the values are close to exact for $n \le 100$.
  • Four improved upper bounds on the minimum order of bi-regular cages of girth 5 are obtained as a by-product of the same runs (Section 3.2).
  • The authors note the method adapts directly to $ex(n;\{C_3,\dots,C_{g-1}\})$ for girth $g \ge 6$, which they have not yet explored.
  • Because code and all output graphs are published, the new bounds are reproducible and independently checkable.

Reading between the lines

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

  • The two unimproved orders, 96 and 97, coincide with the order of the smallest known (9,5)-graph and its successor — a conjunction the paper does not point out; this suggests those two entries may need a better (9,5)-cage, not more hill-climbing.
  • The largest gains occur at the top of the range (n = 160–180), where seed graphs are thinnest; re-running Algorithm 2 with cage seeds removed, and again with propagation disabled, would separate how much of the improvement each mechanism contributes.
  • If propagation is the real driver, the results are empirical evidence that near-extremal girth-5 graphs form a locally continuous sequence in n; mining the published graphs for an explicit infinite construction family could be a route toward Erdős's conjecture.
  • A dedicated run of the same neighbor-seeding idea on bi-regular cages of girth 5 would likely improve more than the four incidental upper bounds reported here.
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

2 major / 4 minor

Summary. The paper presents a new local-search heuristic for constructing n-vertex graphs of girth at least 5 with many edges, applied to the range n = 74,...,198. The algorithm is a randomized variant of the hill-climbing method of Exoo, McKay, Myrvold, and Nadon, initialized with known extremal graphs and small (k,5)-cages, then propagated between nearby orders. The authors report improved lower bounds on ex(n;{C3,C4}) for all n in the range except n = 96,97, where they match the existing bounds, and they make the graphs and code available on GitHub. They also report four improved upper bounds on the order of bi-regular cages of girth 5.

Significance. If the posted graph files are valid certificates, the paper supplies explicit lower bounds for a range where exact methods are currently infeasible, improving the state of the art at most values of n. The algorithmic idea of propagating good seed graphs across neighboring orders is simple and practical, and the use of the extremal/cage literature as a starting point is well motivated. The artifact sharing (graphs in graph6 format and code) is a definite strength and makes the individual bounds verifiable by third parties. The paper is primarily a computational contribution rather than a new theorem, but the reported numbers are of genuine interest to the extremal-graph and cage communities.

major comments (2)
  1. [Table 1 / Table 2 (Sections 1 and 2.2)] The "Previous" column is internally inconsistent with the seed graphs listed in Table 2. A (10,5)-graph on 124 vertices has 10·124/2 = 620 edges, and a (11,5)-graph on 154 vertices has 11·154/2 = 847 edges. Table 1 gives Previous lower bounds of 611 (n=124) and 837 (n=154), both below the edge counts of graphs the paper itself cites as known. Thus the improvements at those two rows are overstated: 629 vs. 620 (not 629 vs. 611) and 860 vs. 847 (not 860 vs. 837). The claim that the New bounds improve on existing lower bounds may still be true at these orders, but the table's label "Best known bounds from the literature" is not accurate, and the reported margins are wrong. The authors should re-benchmark every entry against the actual best known bounds, including the cage values in Table 2, and correct the narrative about doubledigit improvements if those examples are affected.
  2. [Section 2.1 / Section 2.2] The algorithm parameters needed to reproduce the table entries are not fully specified. The paper defines p, totalNumIters, numItersTooRecent, and kmax, but states only that p is "around 0.5 seems to give the best results"; it does not give the actual values used to generate Table 1, nor the number of passes in the outer loop, nor random seeds. In addition, the local search critically depends on checking whether adding an edge creates a C3 or C4, but no pseudo-code or description of the girth test is provided. Since the entire contribution rests on the validity of the reported graphs, the paper should either document these details in an appendix or state that the published code, with its default settings and seeds, reproduces exactly the values in Table 1. Without this, the computational results are not reproducible from the paper alone.
minor comments (4)
  1. [Section 1] Typo: "its size is its the number of edges" should be "its size is the number of edges".
  2. [Table 2 caption] The caption shows garbled text ("initialize ���� in Algorithm 2"); presumably this should be "initialize best in Algorithm 2".
  3. [References / Appendix A] The text refers to Appendix A for the sources of the Previous column, but the appendix is not present in the provided full text. If it is missing from the submitted version, it must be included; if it is present in the actual submission, the referee did not see it, and the Table 1 inconsistency with Table 2 should nevertheless be resolved.
  4. [Section 2.2] The phrase "allow to `propagate' good patterns" is awkward; consider "allow good patterns to propagate".

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the reported lower bounds are explicit constructed graphs, not fitted parameters or restatements of the inputs.

full rationale

The derivation chain is non-circular. The algorithm is seeded with previously published extremal graphs from [6] and small (k,5)-cages from [18,28,34], but those are external benchmark data, not the claimed results. Algorithm 1 adds only legal edges (edges whose addition keeps girth at least 5) and deletes edges randomly; Algorithm 2 propagates modified near-extremal graphs across neighboring n. The New column of Table 1 is, by construction, the size of explicit n-vertex graphs found by this search. Each such graph is an independent certificate: if it truly has n vertices, girth at least 5, and m edges, then ex(n;{C3,C4}) >= m follows immediately. No parameter is fitted to the New column, no target value is used in the fitness function, and the algorithm does not optimize against the Previous column of Table 1. The reuse of external graphs as seeds is legitimate input, and the output graphs are not defined in terms of the numbers they are said to improve. The self-citations that appear ([24], [27]) concern computational methods and code availability; they are not load-bearing for the lower-bound certificates. The apparent inconsistency between Table 1's Previous values at n=124 and n=154 and the edge counts of the (10,5)- and (11,5)-cages listed in Table 2 is a benchmarking/correctness issue about the comparison baseline, not a circular reduction of the construction to its inputs. The absence of machine-verified certificates is likewise a verification risk, not evidence of circularity. No load-bearing step equates a prediction with an input by definition or by self-citation.

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

The lower-bound claim itself introduces no fitted constants; the free parameters only tune the search. All mathematical premises are external theorems or implementation assumptions, and no new mathematical entities are invented.

free parameters (4)
  • p (probability of choosing max degree-sum edge) = about 0.5
    Chosen by trial and error among values in [0,1]; affects search performance, not the validity of output graphs.
  • totalNumIters
    Iteration budget for localSearch; tuned experimentally, value not stated in the text.
  • numItersTooRecent
    Threshold preventing recently deleted edges from being removed again; tuned experimentally.
  • kmax
    Maximum number of edges deleted per iteration; tuned experimentally.
assumptions (4)
  • standard math For n >= 7, every extremal graph for {C3,C4} has girth exactly 5.
    Quoted from Garnick and Nieuwejaar [23] and used in Section 1 to equate the extremal problem with maximum size of girth-5 graphs.
  • standard math When a Moore graph of girth g and order n exists, it is the unique graph in EX(n;{C3,...,Cg-1}).
    Theorem 4 in Abajo and Diánez [3], stated as Theorem 1; used to motivate choosing (k,5)-cages as seed graphs.
  • domain assumption Seed graphs from [6], [34], [28] and [18] have the claimed orders, degrees, and girth.
    These seeds initialize the 'best' data structure in Algorithm 2 (Table 2); an invalid seed could propagate into invalid lower bounds.
  • domain assumption The 'legal edge' check in localSearch exactly tests whether adding an edge creates a triangle or a 4-cycle.
    Section 2.1 describes selecting 'legal edges' that do not violate the girth constraint; the paper gives no formal proof or code-level specification of this cycle test, and correctness of all reported bounds rests on it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved lower bounds on the maximum size of graphs with girth 5." pith.science (2026). https://pith.science/paper/RDTB45WR

@misc{pith2026250805562,
  author       = {Pith},
  title        = {Pith review of: Improved lower bounds on the maximum size of graphs with girth 5},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RDTB45WR}},
  note         = {Machine review of arXiv:2508.05562}
}
abstract

We present a new algorithm for improving lower bounds on $ex(n;\{C_3,C_4\})$, the maximum size (number of edges) of an $n$-vertex graph of girth at least 5. The core of our algorithm is a variant of a hill-climbing heuristic introduced by Exoo, McKay, Myrvold and Nadon (2011) to find small cages. Our algorithm considers a range of values of $n$ in multiple passes. In each pass, the hill-climbing heuristic for a specific value of $n$ is initialized with a few graphs obtained by modifying near-extremal graphs previously found for neighboring values of $n$, allowing to `propagate' good patterns that were found. Focusing on the range $n\in \{74,75, \dots, 198\}$, which is currently beyond the scope of exact methods, our approach yields improvements on existing lower bounds for $ex(n;\{C_3,C_4\})$ for all $n$ in the range, except for two values of $n$ ($n=96,97$).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 35 canonical work pages

  1. [1]

    Abajo, C

    E. Abajo, C. Balbuena, and A. Diánez. New families of graphs without short cycles and large size. Discrete Applied Mathematics, 158(11):1127–1135, 2010

    work page 2010

  2. [2]

    Abajo, C

    E. Abajo, C. Balbuena, and A. Diánez. Girth of {C3, . . . , Cs}-free extremal graphs. Discrete Applied Mathematics, 160(9):1311–1318, 2012

    work page 2012

  3. [3]

    Abajo and A

    E. Abajo and A. Diánez. Graphs with maximum size and lower bounded girth.Applied Mathe- matics Letters, 25(3):575–579, 2012

    work page 2012

  4. [4]

    Abajo and A

    E. Abajo and A. Diánez. Exact value ofex(n; {C3, ..., Cs}) for n ⩽ ⌊ 25(s−1) 8 ⌋. Discrete Applied Mathematics, 185:1–7, 2015

    work page 2015

  5. [5]

    Abajo and A

    E. Abajo and A. Diánez. Exact values ofex(ν; {C3, C4, . . . , Cn}). Discrete Applied Mathematics, 158(17):1869–1878, 2010

    work page 2010

  6. [6]

    Afzaly and B

    N. Afzaly and B. D. McKay.https://users.cecs.anu.edu.au/~bdm/data/extremal.html

    work page

  7. [7]

    N. Alon, M. Krivelevich, and B. Sudakov. Turán numbers of bipartite graphs and related Ramsey- type questions. Combinatorics, Probability and Computing, 12(5-6):477–494, 2003

    work page 2003

  8. [8]

    Sizes of the extremal girth 5 graphs of orders from 40 to 49

    J. Backelin. Sizes of the extremal girth 5 graphs of orders from 40 to 49. arXiv preprint arXiv:1511.08128, 2015

    work page Pith review arXiv 2015

Show all 38 references
  1. [9]

    Balbuena, M

    C. Balbuena, M. Cera, A. Diánez, and P. García-Vázquez. On the girth of extremal graphs without shortest cycles.Discrete Mathematics, 308(23):5682–5690, 2008

    2008

  2. [10]

    Balbuena and X

    C. Balbuena and X. Marcote. Monotonicity of the order of(D; g)-cages. Applied Mathematics Letters, 24(11):1933–1937, 2011

    1933

  3. [11]

    N. H. Bong. Some new upper bounds ofex(n; {C3, C4}). AKCE International Journal of Graphs and Combinatorics, 14(3):251–260, 2017

    2017

  4. [12]

    Charton, J

    F. Charton, J. S. Ellenberg, A. Z. Wagner, and G. Williamson. Patternboost: Constructions in mathematics with a little help from AI.arXiv preprint arXiv:2411.00566, 2024

    2024 arXiv

  5. [13]

    Coolsaet, S

    K. Coolsaet, S. D’hondt, and J. Goedgebeur. House of Graphs 2.0: A database of interest- ing graphs and more. Discrete Applied Mathematics, 325:97–107, 2023. Available at https: //houseofgraphs.org/

    2023

  6. [14]

    Downs, R

    M. Downs, R. Gould, J. Mitchem, and F. Saba. (D; n)-cages. Congressus Numerantium, 308(32):179–183, 1981. 10

    1981

  7. [15]

    P. Erdős. Some recent progress on extremal problems in graph theory.Congressus Numerantium, 14:3–14, 1975

    1975

  8. [16]

    Erdős and M

    P. Erdős and M. Simonovits. A limit theorem in graph theory.Studia Scientiarum Mathemati- carum Hungarica, 1(51-57):51, 1966

    1966

  9. [17]

    Erdős and A

    P. Erdős and A. H. Stone. On the structure of linear graphs.Bulletin of the American Mathe- matical Society, 52:1087–1091, 1946

    1946

  10. [18]

    G. Exoo. Website with Regular Graphs of Given Degree and Girth.http://ginger.indstate. edu/ge/CAGES. Website no longer online

  11. [19]

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

    2011

  12. [20]

    Z. Füredi. Graphs without quadrilaterals.Journal of Combinatorial Theory, Series B, 34(2):187– 190, 1983

    1983

  13. [21]

    Füredi, A

    Z. Füredi, A. Naor, and J. Verstraëte. On the Turán number for the hexagon. Advances in Mathematics, 203(2):476–496, 2006

    2006

  14. [22]

    D. K. Garnick, Y. H. Kwong, and F. Lazebnik. Extremal graphs without three-cycles or four- cycles. Journal of Graph Theory, 17(5):633–645, 1993

    1993

  15. [23]

    D. K. Garnick and N. A. Nieuwejaar. Non-isomorphic extremal graphs without three-cycles or four-cycles. Journal of Combinatorial Mathematics and Combinatorial Computing, 12:33–56, 1992

    1992

  16. [24]

    Goedgebeur, J

    J. Goedgebeur, J. Jooken, and T. Van den Eede. Computational methods for finding bi-regular cages. arXiv preprint arXiv:2411.17351, 2024

    2024 arXiv

  17. [25]

    A. J. Hoffman and R. R. Singleton. On moore graphs with diameters 2 and 3.IBM Journal of Research and Development, 4(5):497–504, 1960

    1960

  18. [26]

    O. Janzer. The extremal number of the subdivisions of the complete bipartite graph. SIAM Journal on Discrete Mathematics, 34(1):241–250, 2020

    2020

  19. [27]

    Jooken and T

    J. Jooken and T. Van den Eede. searchMaxSizeMinGirth. https://github.com/AGT-Kulak/ searchMaxSizeMinGirth, 2025. GitHub repository

    2025

  20. [28]

    L. K. Jørgensen. Girth 5 graphs from relative difference sets.Discrete Mathematics, 293(1-3):177– 184, 2005

    2005

  21. [29]

    W. Mantel. Vraagstuk xxviii.Wiskundige Opgaven met de Oplossingen, 10(2):60–1, 1907

    1907

  22. [30]

    Marshall.Extremal networks and connectivity

    K. Marshall.Extremal networks and connectivity. PhD thesis, The University of Newcastle, 2011

    2011

  23. [31]

    Marshall, M

    K. Marshall, M. Miller, and J. Ryan. Extremal graphs without cycles of length 8 or less.Electronic Notes in Discrete Mathematics, 38:615–620, 2011

    2011

  24. [32]

    B. D. McKay and A. Piperno. Practical graph isomorphism, II.Journal of Symbolic Computation, 60:94–112, 2014

    2014

  25. [33]

    Mehrabian, A

    A. Mehrabian, A. Anand, H. Kim, N. Sonnerat, M. Balog, G. Comanici, T. Berariu, A. Lee, A. Ruoss, A. Bulanova, D. Toyama, S. Blackwell, B. R. Paredes, P. Veličković, L. Orseau, J. Lee, A. M. Naredla, D. Precup, and A. Z. Wagner. Finding increasingly large extremal graphs with ...

    2024

  26. [34]

    G. Royle. Website with Regular Graphs of Given Degree and Girth.http://school.maths.uwa. edu.au/~gordon/remote/cages/allcages.html, 2001. Website no longer online

    2001

  27. [35]

    Sudakov and I

    B. Sudakov and I. Tomon. Turán number of bipartite graphs with noKt,t. Proceedings of the American Mathematical Society, 148(7):2811–2818, 2020. 11

    2020

  28. [36]

    J. Tang, Y. Lin, C. Balbuena, and M. Miller. Calculating the extremal number ex(ν; C3, C4, . . . , Cn). Discrete Applied Mathematics, 157(9):2198–2206, 2009

    2009

  29. [37]

    P. Turán. On an extremal problem in graph theory.Matematikai és Fizikai Lapok, 48:436–452, 1941

    1941

  30. [38]

    Yuansheng and W

    Y. Yuansheng and W. Liang. The minimum number of vertices with girth 6 and degree set D = {r, m}. Discrete Mathematics, 269(1):249–258, 2003. 12

    2003

Pith tools

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