Pith. sign in

REVIEW 2 major objections 5 minor 26 references

Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284

T0 review · 2 major / 5 minor · reviewed 2026-07-31 · grok-4.5

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

Pith's one-line read WOW-284 is false: connected girth-at-least-five graphs can have minimum dual degree strictly larger than the negative of their least distance eigenvalue, with exact counterexamples from order 38 up through the 50-vertex Moore graph and a fu

desk verdict Clean explicit refutation of WOW-284 plus a real structural package; the easy Moore counterexample is old news, the rest is the paper. read the letter →

arxiv 2607.27452 v1 pith:BNVYZXBC submitted 2026-07-29 math.CO math.SP

Samuil Petkov This is my paper · ORCID
classification math.COmath.SP MSC 05C5005C1205C3505E30
keywords distancespectrumdualdegreeMooregraphWOW-284nonbacktrackingLPgirthfivedeletionstabilityslackmatrix
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 refutes a long-standing graph conjecture that tied two simple spectral-and-degree quantities: for every connected graph on at least three vertices with no triangles or 4-cycles, the smallest average-neighbour-degree was supposed never to exceed the negative of the smallest eigenvalue of the distance matrix. Explicit counterexamples exist at orders 38, 39, 40, 42 and 50, beginning from the classical diameter-two Moore graphs and their vertex deletions. For regular graphs the failure is completely characterized when the diameter is three: it is equivalent to every non-principal adjacency eigenvalue lying inside a fixed open interval around −1. From that identity the paper derives hard lower bounds on degree, upper bounds on diameter and order, an exact one-variable linear-programming ceiling, and a positive-semidefinite slack matrix whose integral excess forces a three-to-one order bound. It also proves that deleting up to five vertices from the 50-vertex Moore graph preserves the counterexample property, while some six-vertex deletion destroys it. The result matters because it replaces an attractive universal inequality with a sharp spectral window, quantitative order limits, and a deletion-stability radius that can be checked exactly.

What carries the argument

The diameter-three score identity D=3J+(k−3)I−2A−A², which converts the dual-degree-plus-distance-eigenvalue gap into a two-sided window on the adjacency eigenvalues, together with the optimal non-backtracking polynomial whose slack matrix is positive-semidefinite and whose integral excess quantizes to the three-to-one order bound.

What would settle it

Exhibit a single connected 5-regular graph of girth at least five whose distance matrix has least eigenvalue strictly greater than −5, or a 6-regular girth-five graph on more than 50 vertices whose non-principal adjacency eigenvalues all lie inside (−1−√10,−1+√10); either object would break the stated obstructions.

Watch

Extended reading notes

Core claim

WOW-284 fails: there exist connected graphs of girth at least five with Φ(G)=δ*(G)+λ_min(D(G))>0. For connected k-regular graphs of girth at least five and diameter three the score collapses to the closed formula Φ(G)=2k−2−max_{θ≠k}(θ+1)^2, so strict counterexamples are exactly those whose non-principal adjacency spectrum lies in the open interval (−1−√(2k−2),−1+√(2k−2)). Every regular strict counterexample has degree at least six and diameter at most four; diameter four forces degree at least ten. Regular degree-six counterexamples have order at most 50.

Load-bearing premise

The low-degree exclusion for regular counterexamples rests on complete external enumerations of a handful of small cages and on the classical classification of regular graphs whose smallest adjacency eigenvalue is at least −2; if either inventory is incomplete the degree-five and slack-graph arguments reopen.

Editorial extensions

If this is right

  • No regular strict counterexample of degree ≤5 exists, and every regular one has diameter 2, 3 or 4 (diameter 4 only for degree ≥10).
  • Regular diameter-three counterexamples obey the explicit order ceiling ⌊3(k+2)²(k²+3)/(18k+41)⌋, giving windows n≤50,74,108,150 in degrees 6–9.
  • Every deletion of at most five vertices from the 50-vertex degree-7 Moore graph remains a strict counterexample; the universal radius is exactly five.
  • At the unresolved 6-regular order-50 boundary the associated signed complement must be disconnected and the (−2)-multiplicity of the adjacency matrix is at most 20.
  • One- and two-vertex punctures of any Moore graph of diameter two have completely determined distance spectra and remain counterexamples for all realizable degrees ≥5 or ≥6 according to the puncture type.

Reading between the lines

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

  • The same slack-matrix minors that recover 5-cycle counts should extend to a practical computational sieve for hunting (or ruling out) the remaining degree-6 order-50 candidates without full spectrum computation.
  • Because the LP optimum is rigid and graph-independent, the same one-variable certificate can be reused as a black-box filter inside any search for irregular or larger-girth distance-spectrum counterexamples.
  • The sharp five-vertex deletion radius for the 50-vertex Moore graph suggests a broader stability programme: measure how far other extremal cages can be punctured before their distance-score sign flips.
  • If a degree-10 diameter-4 regular counterexample exists, the endpoint-neighbourhood Rayleigh bound already forces it near the edge of feasibility, so a short computer search in that narrow band could finish the regular trichotomy.
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 / 5 minor

Summary. The paper refutes Fajtlowicz’s WOW-284 conjecture by exhibiting connected girth-at-least-five graphs with Φ(G)=δ*(G)+λ_min(D(G))>0 at orders 38, 39, 40, 42, and 50, anchored by the Hoffman–Singleton graph and explicit descendants (Anstee–Robertson cage, punctures, second subconstituents). For connected k-regular girth-≥5 diameter-3 graphs it proves the exact score identity Φ(G)=2k−2−max_{θ≠k}(θ+1)^2, so strict failure is equivalent to confinement of the nonprincipal adjacency spectrum in the open shifted window (−1−√(2k−2),−1+√(2k−2)). It then develops degree/diameter obstructions (regular strict counterexamples have k≥6 and diam≤4; diam 4 forces k≥10), solves the associated one-variable nonbacktracking LP exactly with optimizer rigidity, and derives an integral-slack three-to-one order bound, local cycle sieves, and a disconnected signed-complement constraint at the (6,50) boundary. Parallel sections give exact distance spectra of Moore punctures and a sharp Hoffman–Singleton deletion radius of five. Theorem-level numerics use exact arithmetic; Lean 4.31 kernel-checks the 50-vertex certificate, finite spectral certificates at 38–42, and the analytic LP optimum/rigidity for all k≥4.

Significance. If correct, this is a clean, constructive settlement of a recorded Graffiti/distance-spectrum conjecture, together with a usable structural calculus for when and why the inequality fails. The diameter-three score formula, exact LP ceiling B_k with rigidity, and integral-slack hierarchy are of independent interest beyond the conjecture. Strengths that raise the contribution above a bare counterexample list include: explicit coordinate models and exact spectra; reproducible exact-arithmetic certificates; a sharp deletion-stability theorem for Hoffman–Singleton; and a sorry-free Lean 4.31 development that kernel-checks the principal 50-vertex graph-level certificate, the small-order spectral certificates, and the LP optimum/rigidity for every integer k≥4. The work is carefully scoped about what is and is not formalized.

major comments (2)
  1. [Theorem 4.2] Theorem 4.2’s exclusion of degree 5 in diameter three rests on Meringer’s isomorph-free census of the four (5,5)-cages and exact distance spectra of fixed graph6 records (and, for n=32, a compressed-layer interlacing argument). The existence refutation does not need this step, but the paper’s stated main conclusion that every regular strict counterexample has degree ≥6 does. Please make the logical dependence explicit in the theorem statement or proof, pin the four graph6 strings (or canonical labels) in the text or a table, and state clearly that the degree-five case is certified by exhaustive check of that finite list rather than a classification-free argument.
  2. [Theorem 6.1] In the r≤0 analysis of Theorem 6.1, the argument invokes the Cameron–Goethals–Seidel–Shult / Cvetković–Rowlinson–Simić classification of connected regular graphs of order >28 with least eigenvalue ≥−2 (line graphs or cocktail-party graphs), then derives contradictions via irreducibility and dimension-mod-4 constraints. This underwrites the three-to-one excess bound and the degree-six order-≤50 corollary. The citations are appropriate, but the write-up should isolate this external classification as a named hypothesis in the proof tree (what fails if one only assumes the classification up to a larger order, etc.) so that the integral-slack consequences are auditable independently of the existence counterexamples.
minor comments (5)
  1. [Section 1 / Section 10] Section 10 already delimits the Lean scope well; a one-sentence cross-reference in the introduction (what is kernel-checked vs. only exactly audited in Python) would help readers who stop at the main theorems.
  2. [Theorem 2.4] In Theorem 2.4, the H_39 row reports an exact strict lower bound via positive-definiteness of 6D+35I rather than the exact least eigenvalue. The prose explains this, but the table header “λ_min(D(G))” is slightly misleading; consider “bound on λ_min” or a footnote mark in the table.
  3. [Corollary 6.7] Corollary 6.7 and the comparison table of unadjusted diameter-three bounds are useful; adding the parity improvements for odd k directly into that small table would avoid a second prose pass.
  4. [Section 10] Several script names are cited as independent audits (e.g., verify_proof_audit_02_two_sided_lp.py). For journal permanence, ensure the arXiv ancillary or a DOI-backed release tags the exact commit/release (v2.2.8 is mentioned) and that graph6/edge-list inputs are immutable.
  5. [Section 1] Minor notation: δ* and d* are introduced cleanly, but Φ(G) appears before it is formally defined in some readers’ skim path (abstract vs. §1). A parenthetical in the first paragraph of §1 is enough.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: refutation and structural bounds are derived from explicit graphs, distance-polynomial identities, and dual LP certificates, not from self-fitting or load-bearing self-citation.

full rationale

WOW-284 is refuted by concrete external objects (coordinate Hoffman–Singleton, Anstee–Robertson cage, Moore punctures) whose dual degrees and distance spectra follow from the Moore identity A²=(k−1)I−A+J and exact matrix certificates, including Lean 4.31 graph-level checks—not by defining Φ in terms of itself. The diameter-three score formula Φ(G)=2k−2−max(θ+1)² is the spectral transfer of the identity D=3J+(k−3)I−2A−A² under girth ≥5. The one-variable nonbacktracking LP ceiling B_k and optimizer rigidity are weak-duality statements with an explicit dual atomic measure; equality forces a non-graphical spectrum. Integral-slack and three-to-one excess bounds are consequences of PSD principal minors of that optimizer, not fitted parameters renamed as predictions. Internal lemma citations are ordinary forward dependency; external classifications (Meringer cages, CGSS/CRS λ_min≥−2 graphs) underwrite only low-degree obstruction side-results, not the existence refutation. No self-definitional loop, fitted-as-prediction step, or author-uniqueness import is present.

Assumptions & free parameters 0 free parameters · 6 assumptions · 2 invented entities

Pure combinatorial spectral theory: no fitted physical constants. Load-bearing background is standard linear algebra plus a few deep but standard classification theorems and one external cage census. Constructed matrices (optimal slack, signed complement) are derived objects, not free postulates. Explicit counterexamples rest on the classical Hoffman–Singleton / Moore identities and finite exact certificates rather than new ontological entities.

assumptions (6)
  • standard math Standard spectral graph theory: interlacing, Rayleigh quotients, Weyl inequalities, equitable partitions, and characteristic polynomials over Q.
    Used throughout §§3–8 for score transfer, diameter bounds, and puncture decompositions.
  • domain assumption Girth at least five implies unique nonbacktracking paths of length <g/2 and the distance-polynomial identities A_i=F_i(A) up to the diameter hypotheses (Prop. 3.3, Thm 3.1).
    Defines the conjecture’s domain and converts D into a quadratic/cubic in A; without it the score formula fails.
  • standard math Classification of connected regular graphs of order >28 with least eigenvalue ≥ −2 as line graphs or cocktail-party graphs (Cameron–Goethals–Seidel–Shult / CRS).
    Invoked as a black box inside the r≤0 and n>3r case analysis of Theorem 6.1.
  • domain assumption Meringer’s enumeration: exactly four (5,5)-cages up to isomorphism, with fixed graph6 records used for exact distance spectra.
    Closes the k=5 diameter-three case in Theorem 4.2; not re-derived in the paper.
  • standard math Root-system representation theorem for connected edge-signed graphs with smallest eigenvalue ≥ −2 (Greaves–Koolen–Munemasa–Sano–Taniguchi).
    Used in Theorem 6.11 to force disconnection of the order-50 signed complement.
  • standard math Existence and standard parameters of the Hoffman–Singleton graph (unique 7-regular Moore graph of diameter 2 on 50 vertices).
    Source of the primary counterexample and deletion family; coordinate model is re-verified in Lean.
invented entities (2)
  • Optimal slack matrix S_k / integral excess matrix E_k and excess parameter r independent evidence
    purpose: Turn the exact LP optimizer into a PSD certificate whose integrality yields the three-to-one order bound and cycle sieves.
    Defined from g_k(A) and J in Theorems 5.4 and 6.1; purely derived linear-algebraic objects with no extra ontology.
  • Signed complement adjacency T (order-50 degree-6 boundary) independent evidence
    purpose: Encode 2×2 minor constraints as a signed graph with λ_min≥−2 to prove disconnection at the n=50 boundary.
    Specialization of the slack construction in Remark 6.10 / Theorem 6.11; falsifiable by exhibiting a connected T for a putative counterexample.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284." pith.science (2026). https://pith.science/paper/BNVYZXBC

@misc{pith2026260727452,
  author       = {Pith},
  title        = {Pith review of: Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BNVYZXBC}},
  note         = {Machine review of arXiv:2607.27452}
}
abstract

WOW-284 asserts that the minimum dual degree of every connected graph of order at least three and girth at least five does not exceed the negative of its least distance eigenvalue. We refute it with exact counterexamples of orders $38,39,40,42$, and $50$, and develop a structural theory of the failure. For a connected $k$-regular graph of girth at least five and diameter three, we prove $\delta^*(G)+\lambda_{\min}(D(G))=2k-2-\max_{\theta\ne k}(\theta+1)^2$. Here $\theta$ ranges over the nonprincipal adjacency eigenvalues. We further prove that every regular strict counterexample has degree at least six and diameter at most four, while diameter four forces degree at least ten. We solve the associated one-variable nonbacktracking linear program exactly, including optimizer rigidity. For regular strict counterexamples of diameter three, the optimizer yields a positive-semidefinite slack matrix whose integral excess gives the stronger bound $|V(G)|\le\left\lfloor 3(k+2)^2(k^2+3)/(18k+41)\right\rfloor$; this follows from a three-to-one quantization theorem for the integral excess. The slack matrix's principal minors also recover local cycle constraints. In particular, regular degree-six counterexamples have order at most $50$, and at the degree-six, order-$50$ boundary the associated signed complement is necessarily disconnected. We determine the distance spectra of one- and two-vertex punctures of Moore graphs and establish a uniform deletion-stability bound: every deletion of at most five vertices from the Hoffman--Singleton graph remains a strict counterexample, whereas an explicit six-vertex deletion does not. All theorem-level computations use exact arithmetic. Lean 4.31 kernel-checks the explicit $50$-vertex Hoffman--Singleton counterexample at graph level, finite spectral certificates at orders $38,39,40,42$, and the analytic LP optimum and rigidity for every integer $k\ge4$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 14 canonical work pages

  1. [1]

    Written on the wall: Conjectures derived on the basis of the program Galatea Gabriella Graffiti

    Siemion Fajtlowicz. Written on the wall: Conjectures derived on the basis of the program Galatea Gabriella Graffiti. Technical report, University of Houston, 1998

    1998

  2. [2]

    Distance spectra of graphs: A survey.Linear Algebra and its Applications, 458:301–386, 2014

    Mustapha Aouchiche and Pierre Hansen. Distance spectra of graphs: A survey.Linear Algebra and its Applications, 458:301–386, 2014. doi: 10.1016/j.laa.2014.06.010

    work page doi:10.1016/j.laa.2014.06.010 2014

  3. [3]

    On the distance spectrum of minimal cages and associated distance biregular graphs.Linear Algebra and its Applications, 636:115–133, 2022

    Aditi Howlader and Pratima Panigrahi. On the distance spectrum of minimal cages and associated distance biregular graphs.Linear Algebra and its Applications, 636:115–133, 2022. doi: 10.1016/j.laa.2021.11.014

    work page doi:10.1016/j.laa.2021.11.014 2022

  4. [4]

    Quotient-polynomial graphs.Linear Algebra and its Applications, 488:363–376, 2016

    Miquel Àngel Fiol. Quotient-polynomial graphs.Linear Algebra and its Applications, 488:363–376, 2016. doi: 10.1016/j.laa.2015.09.053

    work page doi:10.1016/j.laa.2015.09.053 2016

  5. [5]

    Linear programming bounds for regular graphs.Graphs and Combinatorics, 31(6):1973–1984, 2015

    Hiroshi Nozaki. Linear programming bounds for regular graphs.Graphs and Combinatorics, 31(6):1973–1984, 2015. doi: 10.1007/s00373-015-1613-7

    work page doi:10.1007/s00373-015-1613-7 1973

  6. [6]

    Cioabă, Jack H

    Sebastian M. Cioabă, Jack H. Koolen, Hiroshi Nozaki, and Jason R. Vermette. Maximizing the order of a regular graph of given valency and second eigenvalue.SIAM Journal on Discrete Mathematics, 30(3):1509–1525, 2016. doi: 10.1137/15M1030935

    work page doi:10.1137/15m1030935 2016

  7. [7]

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

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

    arXiv 2015

  8. [8]

    Paul R. Hafner. The Hoffman–Singleton graph and its automorphisms.Journal of Algebraic Combinatorics, 18(1):7–12, 2003. doi: 10.1023/A:1025136524481

    work page doi:10.1023/a:1025136524481 2003

Show all 26 references
  1. [9]

    O’Keefe and Pak-Ken Wong

    M. O’Keefe and Pak-Ken Wong. A smallest graph of girth 5 and valency 6.Journal of Combinatorial Theory, Series B, 26(2):145–149,

  2. [10]

    On the uniqueness of the smallest graph of girth 5 and valency 6.Journal of Graph Theory, 3(4):407–409, 1979

    Pak-Ken Wong. On the uniqueness of the smallest graph of girth 5 and valency 6.Journal of Graph Theory, 3(4):407–409, 1979. doi: 10.1002/jgt.3190030413

    1979 doi

  3. [11]

    Higmanian rank-5 association schemes on 40 points.Michigan Mathematical Journal, 58(1):255–284, 2009

    Mikhail Klin, Mikhail Muzychuk, and Matan Ziv-Av. Higmanian rank-5 association schemes on 40 points.Michigan Mathematical Journal, 58(1):255–284, 2009. doi: 10.1307/mmj/1242071692

    2009

  4. [12]

    van Dam and Willem H

    Edwin R. van Dam and Willem H. Haemers. Which graphs are determined by their spectrum?Linear Algebra and its Applications, 373: 241–272, 2003. doi: 10.1016/S0024-3795(03)00483-X

    2003 doi

  5. [13]

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

    Markus Meringer. Fast generation of regular graphs and construction of cages.Journal of Graph Theory, 30(2):137–146, 1999. doi: 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G

    1999 doi

  6. [14]

    Cameron, Jean-Marie Goethals, Johan J

    Peter J. Cameron, Jean-Marie Goethals, Johan J. Seidel, and Ernest E. Shult. Line graphs, root systems, and elliptic geometry.Journal of Algebra, 43(1):305–327, 1976. doi: 10.1016/0021-8693(76)90162-9

    1976 doi

  7. [15]

    Cambridge University Press, 2004

    Dragoš Cvetković, Peter Rowlinson, and Slobodan Simić.Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue -2. Cambridge University Press, 2004. doi: 10.1017/CBO9780511751752

    2004 doi

  8. [16]

    Koolen, Kefan Yu, Xiaoye Liang, Harrison Choi, and Greg Markowsky

    Jack H. Koolen, Kefan Yu, Xiaoye Liang, Harrison Choi, and Greg Markowsky. Non-geometric distance-regular graphs of diameter at least 3 with smallest eigenvalue at least -3.European Journal of Combinatorics, 126:104118, 2025. doi: 10.1016/j.ejc.2024.104118

    2025

  9. [17]

    Koolen, Akihiro Munemasa, Yoshio Sano, and Tetsuji Taniguchi

    Gary Greaves, Jack H. Koolen, Akihiro Munemasa, Yoshio Sano, and Tetsuji Taniguchi. Edge-signed graphs with smallest eigenvalue greater than -2.Journal of Combinatorial Theory, Series B, 110:90–111, 2015. doi: 10.1016/j.jctb.2014.07.006

    2015 doi

  10. [18]

    Smith and Roberto Montemanni

    Derek H. Smith and Roberto Montemanni. The Moore graph of diameter 2 and degree 57 via cyclic derangements.Axioms, 15(5):332,

  11. [19]

    Jørgensen

    Leif K. Jørgensen. Girth 5 graphs from relative difference sets.Discrete Mathematics, 293(1–3):177–184, 2005. doi: 10.1016/j.disc.2004. 08.029

    2005 doi

  12. [20]

    A family of regular graphs of girth 5.Discrete Mathematics, 308 (10):1810–1815, 2008

    Marién Abreu, Martin Funk, Domenico Labbate, and Vito Napolitano. A family of regular graphs of girth 5.Discrete Mathematics, 308 (10):1810–1815, 2008. doi: 10.1016/j.disc.2007.04.031

    2008 doi

  13. [21]

    SymPy: Symbolic computing in Python.PeerJ Computer Science, 3:e103, 2017

    Aaron Meurer et al. SymPy: Symbolic computing in Python.PeerJ Computer Science, 3:e103, 2017. doi: 10.7717/peerj-cs.103

    2017 doi

  14. [22]

    Hagberg, Daniel A

    Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference, pages 11–15, 2008. doi: 10.25080/TCWV9851

    2008 doi

  15. [23]

    The Lean 4 theorem prover and programming language

    Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. InAutomated Deduction—CADE 28, volume 12699 ofLecture Notes in Computer Science, pages 625–635. Springer, 2021. doi: 10.1007/978-3-030-79876-5_37

    2021 doi

  16. [24]

    The Lean mathematical library

    The mathlib Community. The Lean mathematical library. InProceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, pages 367–381. Association for Computing Machinery, 2020. doi: 10.1145/3372885.3373824. Department of Physics, École normale su...

    2020

  17. [1979]

    doi: 10.1016/0095-8956(79)90052-2

    doi

  18. [2026]

    doi: 10.3390/axioms15050332

    doi

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.