Co-edge-regular graphs with four eigenvalues and unbounded coherent rank

Edwin R. van Dam; Hong-Jun Ge; Jack H. Koolen

arxiv: 2606.19981 · v1 · pith:D74JJRO2new · submitted 2026-06-18 · 🧮 math.CO

Co-edge-regular graphs with four eigenvalues and unbounded coherent rank

Edwin R. van Dam , Hong-Jun Ge , Jack H. Koolen This is my paper

Pith reviewed 2026-06-26 17:08 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5005C75

keywords co-edge-regular graphsfour eigenvaluescoherent rankstrongly regular graphsalgebraic graph theoryeigenvalue constructions

0 comments

The pith

Coherent rank is unbounded among co-edge-regular graphs with exactly four distinct eigenvalues.

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

The paper establishes that no finite upper bound exists on the coherent rank of co-edge-regular graphs having exactly four eigenvalues. It proves this by explicit construction: for each prime power q, an infinite family of such graphs is given whose smallest eigenvalue is -2q-1 and whose coherent rank reaches at least q+4. This shows that the equality between spectral complexity and coherent-algebraic complexity known for three-eigenvalue graphs fails to hold with any bound when four eigenvalues are allowed, even under the extra co-edge-regular condition. The result closes the question of uniform boundedness in this subclass.

Core claim

For every prime power q, infinitely many co-edge-regular graphs exist with exactly four distinct eigenvalues, smallest eigenvalue -2q-1, and coherent rank at least q+4. Consequently, coherent rank is unbounded among co-edge-regular graphs with exactly four distinct eigenvalues.

What carries the argument

An explicit construction, for each prime power q, that produces the infinite family of co-edge-regular graphs with the stated spectral and rank properties.

If this is right

The equality of three-eigenvalue graphs with strongly regular graphs does not extend to any uniform bound on coherent rank when four eigenvalues are permitted under co-edge-regularity.
Coherent rank can be made arbitrarily large while the number of distinct eigenvalues remains fixed at four.
The additional co-edge-regular condition does not restore a bound on coherent rank.
Similar constructions may exist for other forms of regularity that still allow unbounded coherent rank.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

It remains open whether coherent rank stays bounded among all regular graphs with four eigenvalues once the co-edge-regular condition is dropped.
The constructions might be adaptable to produce examples in distance-regular graphs or other structured families.
One could test whether the lower bound q+4 is sharp for the given eigenvalue -2q-1.

Load-bearing premise

The explicit constructions for each prime power q actually produce co-edge-regular graphs whose adjacency matrices have exactly four eigenvalues and whose coherent rank is at least q+4.

What would settle it

A single prime power q for which every graph in the claimed family either fails to be co-edge-regular, has more or fewer than four eigenvalues, or has coherent rank less than q+4.

Figures

Figures reproduced from arXiv: 2606.19981 by Edwin R. van Dam, Hong-Jun Ge, Jack H. Koolen.

**Figure 2.** Figure 2: Illustration of the replacements in (2)–(3) if PΠ is a projective plane. For 1 ≤ i ≤ ⌊q/2⌋ and 0 ≤ j ≤ i, define Ti,j := {(a, b) : 1 ≤ a < i, 1 ≤ b ≤ a} ∪ {(i, b) : 1 ≤ b ≤ j}. Also put T0,0 = ∅. Starting from L, twist every swappable pair indexed by Ti,j . The resulting line set is denoted by L− i,j . For convenience, set L− 0,0 = L. The order of the twists is irrelevant, since different indices correspon… view at source ↗

read the original abstract

In the regular three-eigenvalue setting, spectral complexity and coherent-algebraic complexity coincide: a connected regular graph has exactly three distinct eigenvalues if and only if it is strongly regular, its coherent rank is three. Although examples of regular graphs with four distinct eigenvalues and coherent rank larger than four are known, it was unknown whether coherent rank is uniformly bounded among regular graphs with four distinct eigenvalues. We show that no such bound exists, even under the additional assumption of co-edge-regularity. For every prime power \(q\), we construct infinitely many co-edge-regular graphs with exactly four distinct eigenvalues, smallest eigenvalue \(-2q-1\), and coherent rank at least \(q+4\). Consequently, coherent rank is unbounded among co-edge-regular graphs with exactly four distinct eigenvalues.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper constructs explicit infinite families showing coherent rank is unbounded among co-edge-regular graphs with four eigenvalues.

read the letter

The core result is a construction, for every prime power q, of infinitely many co-edge-regular graphs with exactly four eigenvalues (smallest one -2q-1) and coherent rank at least q+4. This settles the open question of whether coherent rank stays bounded in the four-eigenvalue regular case, even after adding co-edge-regularity.

The new content is the explicit families themselves. The paper takes the known open question and supplies concrete graphs that push the coherent rank higher with q. If the eigenvalue multiplicities and the dimension of the coherent algebra are computed correctly in the full text, the argument is direct and avoids any circular parameter fitting.

The main soft spot is verification: the abstract states the properties hold, but the strength rests on whether the construction (likely some kind of geometry or design over finite fields) really produces co-edge-regularity and exactly four eigenvalues for each q. That step needs checking, but nothing in the setup suggests an obvious failure mode. The dependence of the smallest eigenvalue on q is not a flaw; it is part of how the rank grows.

This is for readers in algebraic and spectral graph theory who track the gap between number of eigenvalues and coherent-algebra dimension. Anyone who has worked on strongly regular graphs or coherent configurations will see the point immediately.

I would send it to peer review. The question is settled by construction, and the details are checkable.

Referee Report

0 major / 2 minor

Summary. The manuscript constructs, for every prime power q, infinitely many co-edge-regular graphs having exactly four distinct eigenvalues (with smallest eigenvalue -2q-1) and coherent rank at least q+4. This shows that no uniform upper bound on coherent rank exists among co-edge-regular graphs with four eigenvalues, in contrast to the three-eigenvalue case where the two notions of complexity coincide.

Significance. If the constructions are correct, the result answers an open question by exhibiting an explicit family of examples in which spectral complexity (four eigenvalues) and coherent-algebraic complexity (rank ≥ q+4) diverge arbitrarily. The constructions are parameter-free in the sense that they are given for each prime power q and yield infinitely many graphs per q; this supplies concrete, falsifiable instances rather than an existence proof by non-constructive means.

minor comments (2)

The abstract states that the graphs are co-edge-regular and have exactly four eigenvalues, but the verification steps (adjacency-matrix spectrum computation and coherent-algebra dimension count) are only referenced; a brief outline of these calculations in the introduction would improve readability.
Notation for the coherent rank and the smallest eigenvalue -2q-1 is introduced without an immediate cross-reference to the definition of co-edge-regularity; adding a short reminder in §1 would help readers unfamiliar with the coherent algebra.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report and the recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central result is an existence claim established by explicit construction: for each prime power q, infinitely many co-edge-regular graphs are built with exactly four eigenvalues and coherent rank at least q+4. No derivation chain reduces a claimed prediction or first-principles result to its own inputs by definition, fitting, or self-citation. The abstract and description contain no fitted parameters renamed as predictions, no self-definitional relations, and no load-bearing uniqueness theorems imported from the authors' prior work. The construction itself supplies the required verification of co-edge-regularity, eigenvalue multiplicity, and coherent-algebra dimension, making the argument self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the correctness of an explicit graph construction for each prime power q together with standard definitions of eigenvalues, co-edge-regularity, and coherent algebras from algebraic graph theory.

axioms (1)

standard math Standard definitions and algebraic properties of coherent algebras, eigenvalues of adjacency matrices, and co-edge-regular graphs
The paper invokes these background notions without re-deriving them.

pith-pipeline@v0.9.1-grok · 5659 in / 1115 out tokens · 52888 ms · 2026-06-26T17:08:56.720635+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references

[1]

Barber, D

B. Barber, D. K¨ uhn, A. Lo, D. Osthus, and A. Taylor. Clique decompositions of multipartite graphs and completion of Latin squares.J. Combin. Theory Ser. A, 151:146–201, 2017

2017
[2]

T. Beth, D. Jungnickel, and H. Lenz.Design Theory. Cambridge University Press, Cambridge, second edition, 1999

1999
[3]

A. E. Brouwer and H. Van Maldeghem.Strongly Regular Graphs. Cambridge University Press, Cambridge, 2022

2022
[4]

Dukes, E

P. Dukes, E. R. Lamken, and A. C. H. Ling. An existence theory for incomplete designs. Canad. Math. Bull., 59(2):287–302, 2016

2016
[5]

Ge and J

H.-J. Ge and J. H. Koolen. On co-edge-regular graphs with 4 distinct eigenvalues.Electron. J. Combin., 32(3):#P3.55, 2025. 16

2025
[6]

Gebremichel, M.-Y

B. Gebremichel, M.-Y. Cao, and J. H. Koolen. Two characterizations of the grid graphs. Discrete Math., 344(11):112550, 2021

2021
[7]

C. D. Godsil and G. F. Royle.Algebraic Graph Theory, volume 207 ofGraduate Texts in Mathematics. Springer, New York, 2001

2001
[8]

Greaves and J

G. Greaves and J. Yip. The coherent rank of a graph with three eigenvalues. arXiv:2406.17395, 2024

arXiv 2024
[9]

J. B. Nation and J. Y. G. Seffrood. Dual linear spaces generated by a non-Desarguesian configuration.Contrib. Discrete Math., 6(1):98–141, 2011

2011
[10]

Terwilliger

P. Terwilliger. Lecture notes on Terwilliger algebra.https://icu-hsuzuki.github.io/ t-algebra/t-algebra.pdf, 2023. Edited by H. Suzuki

2023
[11]

E. R. van Dam. Three-class association schemes.J. Algebraic Combin., 10(1):69–107, 1999

1999
[12]

E. R. van Dam and W. H. Haemers. Which graphs are determined by their spectrum?Linear Algebra Appl., 373:241–272, 2003

2003
[13]

E. R. van Dam and E. Spence. Small regular graphs with four eigenvalues.Discrete Math., 189(1–3):233–257, 1998

1998
[14]

W. Wang, L. Qiu, and Y. Hu. Cospectral graphs, GM-switching and regular rational orthog- onal matrices of levelp.Linear Algebra Appl., 563:154–177, 2019. 17

2019

[1] [1]

Barber, D

B. Barber, D. K¨ uhn, A. Lo, D. Osthus, and A. Taylor. Clique decompositions of multipartite graphs and completion of Latin squares.J. Combin. Theory Ser. A, 151:146–201, 2017

2017

[2] [2]

T. Beth, D. Jungnickel, and H. Lenz.Design Theory. Cambridge University Press, Cambridge, second edition, 1999

1999

[3] [3]

A. E. Brouwer and H. Van Maldeghem.Strongly Regular Graphs. Cambridge University Press, Cambridge, 2022

2022

[4] [4]

Dukes, E

P. Dukes, E. R. Lamken, and A. C. H. Ling. An existence theory for incomplete designs. Canad. Math. Bull., 59(2):287–302, 2016

2016

[5] [5]

Ge and J

H.-J. Ge and J. H. Koolen. On co-edge-regular graphs with 4 distinct eigenvalues.Electron. J. Combin., 32(3):#P3.55, 2025. 16

2025

[6] [6]

Gebremichel, M.-Y

B. Gebremichel, M.-Y. Cao, and J. H. Koolen. Two characterizations of the grid graphs. Discrete Math., 344(11):112550, 2021

2021

[7] [7]

C. D. Godsil and G. F. Royle.Algebraic Graph Theory, volume 207 ofGraduate Texts in Mathematics. Springer, New York, 2001

2001

[8] [8]

Greaves and J

G. Greaves and J. Yip. The coherent rank of a graph with three eigenvalues. arXiv:2406.17395, 2024

arXiv 2024

[9] [9]

J. B. Nation and J. Y. G. Seffrood. Dual linear spaces generated by a non-Desarguesian configuration.Contrib. Discrete Math., 6(1):98–141, 2011

2011

[10] [10]

Terwilliger

P. Terwilliger. Lecture notes on Terwilliger algebra.https://icu-hsuzuki.github.io/ t-algebra/t-algebra.pdf, 2023. Edited by H. Suzuki

2023

[11] [11]

E. R. van Dam. Three-class association schemes.J. Algebraic Combin., 10(1):69–107, 1999

1999

[12] [12]

E. R. van Dam and W. H. Haemers. Which graphs are determined by their spectrum?Linear Algebra Appl., 373:241–272, 2003

2003

[13] [13]

E. R. van Dam and E. Spence. Small regular graphs with four eigenvalues.Discrete Math., 189(1–3):233–257, 1998

1998

[14] [14]

W. Wang, L. Qiu, and Y. Hu. Cospectral graphs, GM-switching and regular rational orthog- onal matrices of levelp.Linear Algebra Appl., 563:154–177, 2019. 17

2019