Pith. sign in

REVIEW 27 references

The maximum spectral gap among connected r-regular graphs with essential edge-connectivity at most t equals one of two explicit square-root expressions depending on the parity of t-r, for 6 ≤ r ≤ t ≤ 2r-3.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-27 06:32 UTC pith:U4SAHDHU

load-bearing objection The paper gives a closed-form maximum spectral gap for connected r-regular graphs with essential edge-connectivity at most t (in 6≤r≤t≤2r-3), split by parity of t-r, plus matching constructions.

arxiv 2606.12948 v1 pith:U4SAHDHU submitted 2026-06-11 math.CO

Maximum spectral gap of regular graphs with bounded essential edge-connectivity

Yu Wang , Sanming Zhou This is my paper
classification math.CO
keywords spectral gapregular graphsessential edge-connectivityeigenvaluesedge-cutsalgebraic graph theorygraph expansion
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper determines the largest possible spectral gap for connected r-regular graphs whose smallest essential edge-cut has size at most t. It proves the maximum equals ½(r+7−√((r+7)²−8t−32)) when t-r is odd and ½(r+6−√((r+6)²−8t−32)) when t-r is even. The result is stated for integers r and t in the range 6 ≤ r ≤ t ≤ 2r-3. The authors construct families of graphs that attain the stated values. A reader cares because the spectral gap controls expansion and mixing speed while essential edge-connectivity limits how the graph can be partitioned into large pieces.

Core claim

For any integers t and r with 6≤r≤t≤2r-3, the maximum spectral gap among all connected r-regular graphs with essential edge-connectivity at most t is equal to ½(r+7−√((r+7)²−8t−32)) when t-r is odd and ½(r+6−√((r+6)²−8t−32)) when t-r is even. The paper constructs a family of connected r-regular graphs achieving these bounds.

What carries the argument

The essential edge-connectivity, defined as the minimum size of an edge-cut that leaves at least two non-trivial components, which is used to derive and attain the algebraic upper bound on the difference between the largest and second-largest eigenvalues.

Load-bearing premise

The restriction that r and t are integers satisfying 6 ≤ r ≤ t ≤ 2r-3 together with the definition of an essential edge-cut as one whose removal leaves at least two components each having more than one vertex.

What would settle it

Exhibiting one connected r-regular graph with essential edge-connectivity at most t, for some r and t in the stated range, whose spectral gap strictly exceeds the corresponding formula would falsify the claimed maximum.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • No connected r-regular graph with essential edge-connectivity at most t can have a larger spectral gap than the given expression.
  • The bound is tight because explicit constructions reach it.
  • The choice of formula switches with the parity of t-r, reflecting distinct structural configurations that maximize the gap in each case.
  • The result supplies the exact maximum only inside the numerical window 6 ≤ r ≤ t ≤ 2r-3.

Where Pith is reading between the lines

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

  • The square-root expressions likely come from solving a quadratic equation that arises when the adjacency matrix is constrained by the size of the essential cut.
  • The same bounding technique might be adapted to obtain spectral-gap maxima under vertex-connectivity constraints instead of edge-connectivity.
  • The attaining graphs could serve as concrete examples when one wants to build regular networks that are as expansive as possible while keeping a prescribed upper limit on essential cut size.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 0 minor

Summary. The paper proves that for integers r and t satisfying 6 ≤ r ≤ t ≤ 2r-3, the maximum spectral gap among connected r-regular graphs with essential edge-connectivity at most t equals ½(r+7−√((r+7)²−8t−32)) when t-r is odd and ½(r+6−√((r+6)²−8t−32)) when t-r is even. Explicit constructions of r-regular graphs attaining these values are also supplied.

Significance. If the result holds, it supplies a sharp, closed-form characterization of the largest possible spectral gap under an upper bound on essential edge-connectivity for regular graphs in the given range. The matching constructions and the algebraic expressions constitute a concrete advance in spectral graph theory; the absence of free parameters or fitted quantities in the bound is a notable strength.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending acceptance. The report accurately summarizes the main result and its significance.

Circularity Check

0 steps flagged

No circularity: bound derived from explicit constructions and independent upper-bound proof

full rationale

The paper states an upper bound on the spectral gap for r-regular graphs with essential edge-connectivity ≤ t (in the given range) and supplies matching constructions that attain the algebraic expressions. The derivation relies on the standard definition of essential edge-cuts and direct spectral analysis rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation. No step reduces the claimed equality to an input quantity by construction; the result is externally falsifiable via the constructions and the proof that no larger gap exists.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard definitions of r-regular graphs, adjacency eigenvalues, and essential edge-cuts from classical graph theory, plus the explicit numerical range on r and t. No free parameters, ad-hoc constants, or new postulated entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions and basic properties of graphs, adjacency matrices, eigenvalues, and edge-connectivity as used in spectral graph theory.
    Invoked to define the objects whose spectral gap is maximized.

pith-pipeline@v0.9.1-grok · 5701 in / 1502 out tokens · 28069 ms · 2026-06-27T06:32:37.816304+00:00 · methodology

0 comments
read the original abstract

An edge-cut of a graph is said to be essential if its removal results in a graph with at least two non-trivial components. The essential edge-connectivity of a graph $G$ is the minimum cardinality among all essential edge-cuts of $G$. The spectral gap of $G$ is the difference between its largest and second largest eigenvalues. In this paper, we prove that for any integers $t$ and $r$ with $6\leq r\leq t\leq 2r-3$, the maximum spectral gap among all connected $r$-regular graphs with essential edge-connectivity at most $t$ is equal to $\frac{1}{2}(r+7-\sqrt{(r+7)^2-8t-32})$ when $t-r$ is odd and $\frac{1}{2}(r+6-\sqrt{(r+6)^2-8t-32})$ when $t-r$ is even. We construct a family of connected $r$-regular graphs achieving these bounds.

Figures

Figures reproduced from arXiv: 2606.12948 by Sanming Zhou, Yu Wang.

Figure 1
Figure 1. Figure 1: |[S, S]| = t Set k = |[U1, U2]|, p = |[U3, U4]| [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references

  1. [1]

    M. Abdi, E. Ghorbani, Minimum algebraic connectivity and maximum diameter: Aldous-Fill and Guiduli-Mohar conjectures,J. Combin. Theory Ser. B167(2024) 164–188

    2024

  2. [2]

    M. Abdi, E. Ghorbani, W. Imrich, Regular graphs with minimum spectral gap,Eu- ropean J. Combin.95(2021), 103328

    2021

  3. [3]

    Abiad, B

    A. Abiad, B. Brimkov, X. Mart´ ınez-Rivera, O. Suil, J. Zhang, Spectral bounds for the connectivity of regular graphs with given order,Electron. J. Linear Algebra34 (2018), 428–443

    2018

  4. [4]

    Aldous, J

    D. Aldous, J. Fill, Reversible Markov chains and random walks on graphs, Univer- sity of California, Berkeley, 2002, available athttps://www.stat.berkeley.edu/ ~aldous/RWG/book.html

    2002

  5. [5]

    N. Alon, V. D. Milman.λ 1, isoperimetric inequalities for graphs, and superconcen- trators,J. Combin. Theory Ser. B38(1) (1985), 73–88

    1985

  6. [6]

    de Abreu, Old and new results on algebraic connectivity of graphs,Linear Algebra Appl.423(2007), 53–73

    N.M.M. de Abreu, Old and new results on algebraic connectivity of graphs,Linear Algebra Appl.423(2007), 53–73

    2007

  7. [7]

    Brouwer, W.H

    A.E. Brouwer, W.H. Haemers,Spectra of Graphs, Springer, New York, 2011

    2011

  8. [8]

    Chandran, Minimum cuts, girth and spectral threshold,Inform

    S.L. Chandran, Minimum cuts, girth and spectral threshold,Inform. Process. Lett. 89(2004), 105–110

    2004

  9. [9]

    Cioab˘ a, Eigenvalues and edge-connectivity of regular graphs,Linear Algebra Appl.432(2010), 458–470

    S.M. Cioab˘ a, Eigenvalues and edge-connectivity of regular graphs,Linear Algebra Appl.432(2010), 458–470

    2010

  10. [10]

    Ekstein, B

    J. Ekstein, B. Wu, L.M. Xiong, Connected even factors in the square of essentially 2-edge-connected graph,Electron. J. Combin.24(3) (2017), Paper 3.42, 9 pp

    2017

  11. [11]

    Fiedler, Algebraic connectivity of graphs,Czechoslovak Math

    M. Fiedler, Algebraic connectivity of graphs,Czechoslovak Math. J.23(1973), 298– 305

    1973

  12. [12]

    Gu, Packing spanning trees and spanning 2-connectedk-edge-connected essen- tially (2k−1)-edge-connected subgraphs,J

    X.F. Gu, Packing spanning trees and spanning 2-connectedk-edge-connected essen- tially (2k−1)-edge-connected subgraphs,J. Combin. Optim.33(2017), 924–933

    2017

  13. [13]

    X.F. Gu, R.R. Liu, G.X. Yu, Spanning tree packing and 2-essential edge-connectivity, Discrete Math.346(2023), 113132. 18

    2023

  14. [14]

    Godsil, G

    C. Godsil, G. Royle,Algebraic Graph Theory, in: Graduate Texts in Mathematics, Vol. 207, Springer-Verlag, New York, 2001

    2001

  15. [15]

    Hoory, N

    S. Hoory, N. Linial, A. Wigderson, Expander graphs and their applications,Bull. Amer. Math. Soc.43(2006), 439–561

    2006

  16. [16]

    Kirkland, J.J

    S. Kirkland, J.J. Molitierno, M. Neumann, B.L. Shader, On graphs with equal alge- braic and vertex connectivity,Linear Algebra Appl.341(2002), 45–56

    2002

  17. [17]

    Kothari, M.H

    N. Kothari, M.H. de Carvalho, C.L. Lucchesi, C.H.C. Little. On essentially 4-edge- connected cubic bricks,Electron. J. Combin.27(1) (2020), 22 pp

    2020

  18. [18]

    Krivelevich, B

    M. Krivelevich, B. Sudakov, Pseudo-random graphs, more sets, in: Graphs and Num- bers,15(2006), 199–262

    2006

  19. [19]

    Lai, J.A

    H.-J. Lai, J.A. Li, Packing spanning trees in highly essentially connected graphs, Discrete Math.342(2019), 1–9

    2019

  20. [20]

    F.L. Lu, X. Feng, Y. Wang,b-invariant edges in essentially 4-edge-connected near- bipartite cubic bricks,Electron. J. Combin.27(1) (2020), Paper 1.55, 10 pp

    2020

  21. [21]

    Mohar, Isoperimetric numbers of graphs,J

    B. Mohar, Isoperimetric numbers of graphs,J. Combin. Theory Ser. B47(3) (1989), 274–291

    1989

  22. [22]

    Mohar, Some applications of Laplace eigenvalues of graphs, in: G

    B. Mohar, Some applications of Laplace eigenvalues of graphs, in: G. Hahn, G. Sabidussi (Eds.),Graph Symmetry: Algebraic Methods and Applications497(1997), 225–275

    1997

  23. [23]

    O, The second largest eigenvalue and vertex-connectivity of regular multigraphs, Discrete Appl

    S. O, The second largest eigenvalue and vertex-connectivity of regular multigraphs, Discrete Appl. Math.279(2020), 118–124

    2020

  24. [24]

    S. O, J.R. Park, J. Park, W.Q. Zhang, Sharp spectral bounds for the edge- connectivity of regular graphs,European J. Combin.110(2023), 103713

    2023

  25. [25]

    A.A. Rad, M. Jalili, M. Hasler, A lower bound for algebraic connectivity based on the connection-graph-stability method,Linear Algebra Appl.435(2011), 186–192

    2011

  26. [26]

    Wu, Algebraic connectivity of directed graphs,Linear Multilinear Algebra53 (2005), 203–223

    C.W. Wu, Algebraic connectivity of directed graphs,Linear Multilinear Algebra53 (2005), 203–223

    2005

  27. [27]

    J.Q. Xu, Z.H. Chen, H.J. Lai, M. Zhang, Spanning trails in essentially 4-edge- connected graphs,Discrete Appl. Math.162(2014), 306–313

    2014