{"id":"943d030e-12f3-4b86-a937-59e4e40d7c9d","arxiv_id":"2508.05562","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A new hill-climbing algorithm improves the best known lower bounds on ex(n;{C3,C4}) for all n in {74,...,198} except n = 96,97.","lead":"This paper uses a randomized search that reuses near-optimal graphs from neighboring sizes to construct graphs with no triangles or 4-cycles and many edges. It reports improved lower bounds on the extremal edge count for every n from 74 to 198 except n = 96 and 97.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Table 1 underreports known cage bounds at n=124 and n=154, so the claimed improvements rest on incorrect baselines.","rationale":"The reader's weakest assumption concerned the correctness of the output graphs themselves. That remains a valid verification concern, but the more immediately damaging issue is visible from the paper's own tables: the Previous column appears to understate known cage-based lower bounds at n=124 and n=154. Since the central advertised contribution is 'improvements over existing lower bounds', an inaccurate baseline directly affects the strength of the claim. The new graphs may still be valid and may still improve on the corrected bounds, so rejection is not warranted; however, the manuscript should not be accepted as-is without correcting Table 1 and re-confirming that the New entries are genuine improvements over the true best known bounds. The proposed test settles this by recomputing the Previous column from primary sources and from the regular graphs the authors themselves used as seeds.","tokens_in":7993,"tokens_out":24244,"duration_ms":241382,"concrete_test":"Reconstruct the Previous column from the references in Appendix A and compare with the edge counts of the (k,5)-graphs in Table 2. Specifically, retrieve the (10,5)-graph on 124 vertices and the (11,5)-graph on 154 vertices from source [18]; verify each is k-regular on the stated order (so edge counts are 620 and 847). Then check whether Table 1's Previous entries at n=124 and n=154 equal these values. Finally, for each n in {74,...,198}, compute the maximum of Table 1's Previous and all known cage-derived bounds, and verify that the New value still exceeds this maximum for every n except 96,97. If any New value does not exceed the corrected maximum, the abstract's claim is false.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central claim is that the New column in Table 1 improves on the best known lower bounds for ex(n;{C3,C4}) for every n in {74,...,198} except 96,97. The Previous column is therefore load-bearing. But Table 1 is internally inconsistent with Table 2: Table 2 lists a (10,5)-graph on 124 vertices and an (11,5)-graph on 154 vertices as seeds, and a (10,5)-graph is 10-regular, so the 124-vertex graph has 10·124/2 = 620 edges, while the 154-vertex graph has 11·154/2 = 847 edges. Table 1 gives Previous bounds of 611 (n=124) and 837 (n=154), both lower than the edge counts of graphs the paper itself cites. The surrounding entries (n=125: 620, n=126: 630; n=155: 847, n=156: 858) match vertex-deletions from the 126- and 156-vertex graphs, suggesting the Previous column was compiled from deletion-based bounds rather than the actual cages. If so, the claimed improvements at n=124 and n=154 are overstated (629 vs 620, and 860 vs 847), and the abstract's assertion of improvements over existing lower bounds needs re-benchmarking against the true best known values.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8303,"tokens_out":7012,"duration_ms":76017,"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":[{"comment":"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.","section":"Table 1 / Table 2 (Sections 1 and 2.2)"},{"comment":"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.","section":"Section 2.1 / Section 2.2"}],"minor_comments":[{"comment":"Typo: \"its size is its the number of edges\" should be \"its size is the number of edges\".","section":"Section 1"},{"comment":"The caption shows garbled text (\"initialize ���� in Algorithm 2\"); presumably this should be \"initialize best in Algorithm 2\".","section":"Table 2 caption"},{"comment":"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.","section":"References / Appendix A"},{"comment":"The phrase \"allow to `propagate' good patterns\" is awkward; consider \"allow good patterns to propagate\".","section":"Section 2.2"}],"recommendation":"major_revision","confidential_remarks":"The central claim—that the New column entries are valid lower bounds exceeding the true prior lower bounds—appears defensible, since even the corrected baselines at n=124 and n=154 (620 and 847) are still below the reported New values (629 and 860). The main problem is that the comparison table is inaccurate and the experimental parameters are underdocumented. This is fixable within the scope of the paper, but requires the authors to redo the benchmark comparison and to specify the exact algorithmic settings and girth-check procedure. I would not reject on the current evidence, but I do not think the manuscript is ready as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The paper does what it claims: it produces explicit n-vertex girth-5 graphs for every n between 74 and 198, and those graphs improve the known lower bounds for ex(n;{C3,C4}) for all but n=96 and 97. The graphs are on GitHub, so the central certificates are independently checkable. The algorithm is a real variant of the Exoo–McKay–Myrvold–Nadon hill-climbing: seeding each n with modified graphs from neighboring n and propagating good patterns across the range is a sensible and effective idea, and the randomized edge-choice is a reasonable twist. The double-digit improvements for larger n are genuinely useful for the benchmark tables.\n\nThe weak spot is the 'Previous' column in Table 1. The paper's own Table 2 lists a (10,5)-graph on 124 vertices and an (11,5)-graph on 154 vertices as seeds. Those graphs have 620 and 847 edges. But Table 1 gives previous bounds of 611 and 837 at those n. That looks like the authors compiled the previous column from vertex-deletion bounds and missed the known cages. The good news: the new bounds (629 and 860) still beat the true cages, so the headline claim 'improvements for all n except 96,97' survives. But the magnitude of the improvement is overstated, and more importantly it makes me want to double-check the rest of the previous column. The paper cites sources in Appendix A, but the inconsistency with its own seed table is a red flag that the comparison baseline wasn't carefully maintained.\n\nOther than that, the math is straightforward: lower bounds are explicit graphs, so no circularity. The lack of pseudo-code for the girth check is minor because the code is shipped. I'd like the authors to fix the baseline errors and either verify or hedge the exact stochastic parameters (p, iterations, kmax) for reproducibility, though the code is the real spec.\n\nOverall: a solid computational contribution worth publishing after a revision that corrects Table 1 and re-derives the improvement claims. It's not a field-level breakthrough, but it's a good data point for the extremal graph theory and cage-search communities. I'd send it to a competent referee; they should spot-check a few of the new graphs with an independent girth verifier and re-run the Table 1 comparisons against the cited sources.","headline":"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.","tokens_in":8808,"tokens_out":3757,"would_cite":true,"duration_ms":32957,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["extremal graph theory","Turán number","girth 5","cages","hill-climbing heuristic","local search","lower bounds","ex(n;{C3,C4})"],"falsifier":"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.","tokens_in":7893,"feed_emoji":"📈","tokens_out":23324,"duration_ms":189528,"temperature":0.7,"pith_summary":"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.","feed_headline":"123 of 125 girth-5 records raised by neighbor seeding","feed_subtitle":"New graphs beat every known record for triangle- and square-free graphs on 74–198 vertices; only n = 96, 97 tie","key_machinery":"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","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Theorem 1: Moore graphs of girth 5 are the extremal graphs of their order; motivates using small (k,5)-cages as seed graphs.","marker":"[3]"},{"why":"Extremal-graph data used to initialize the search pool: known extremal graphs up to order 53 and candidate graphs up to order 64.","marker":"[6]"},{"why":"Supplies the (10,5)- and (11,5)-graphs of orders 124/126 and 154/156 used as seeds in the initial pool.","marker":"[18]"},{"why":"The hill-climbing heuristic the local search modifies: legal-edge insertion with degree-sum priority, then edge deletions.","marker":"[19]"},{"why":"Source of the previous best lower bounds and of the asymptotic bounds framing the problem (lim sup between (1/2)√2 and 1/2).","marker":"[22]"},{"why":"The paper's repository: code and all output graphs in graph6 format, the certificates substantiating each claimed bound.","marker":"[27]"},{"why":"Supplies the smallest known (9,5)-graph, of order 96, used as a seed.","marker":"[28]"},{"why":"Supplies the smallest known (8,5)-graph, of order 80, used as a seed.","marker":"[34]"}],"fun_headline_variants":["Neighbor-seeded search sets 123 new girth-5 lower bounds","Algorithm lifts 123 girth-5 graph size bounds for 74-198","Record girth-5 graphs for 123 orders in 74-198 range","Seeding from adjacent n yields 123 new girth-5 records"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Neighbor-seeded search sets 123 new girth-5 lower bounds","Algorithm lifts 123 girth-5 graph size bounds for 74-198","Record girth-5 graphs for 123 orders in 74-198 range","Seeding from adjacent n yields 123 new girth-5 records"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000942,"raw_usage":{"total_tokens":3874,"prompt_tokens":771,"completion_tokens":3103,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":3031}},"tokens_in":515,"tokens_out":3103,"duration_ms":21711,"temperature":1.0,"reasoning_tokens":3031,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T23:14:40.739087+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Abajo and A","cited_arxiv_id":null,"evidence_quote":"Theorem 1: Moore graphs of girth 5 are the extremal graphs of their order; motivates using small (k,5)-cages as seed graphs."},{"cited_title":"Afzaly and B","cited_arxiv_id":null,"evidence_quote":"Extremal-graph data used to initialize the search pool: known extremal graphs up to order 53 and candidate graphs up to order 64."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the (10,5)- and (11,5)-graphs of orders 124/126 and 154/156 used as seeds in the initial pool."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The hill-climbing heuristic the local search modifies: legal-edge insertion with degree-sum priority, then edge deletions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the previous best lower bounds and of the asymptotic bounds framing the problem (lim sup between (1/2)√2 and 1/2)."},{"cited_title":"Jooken and T","cited_arxiv_id":null,"evidence_quote":"The paper's repository: code and all output graphs in graph6 format, the certificates substantiating each claimed bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the smallest known (9,5)-graph, of order 96, used as a seed."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the smallest known (8,5)-graph, of order 80, used as a seed."}],"review_version":1}