A Cheeger type inequality in finite Cayley sum graphs

Arindam Biswas; Jyoti Prakash Saha

arxiv: 1907.07710 · v2 · pith:AQC47XZJnew · submitted 2019-07-17 · 🧮 math.CO · math.GR

A Cheeger type inequality in finite Cayley sum graphs

Arindam Biswas , Jyoti Prakash Saha This is my paper

Pith reviewed 2026-05-24 20:11 UTC · model grok-4.3

classification 🧮 math.CO math.GR

keywords Cayley sum graphsexpander graphsCheeger constantspectral gapnormalized adjacency operatorfinite groupsgraph spectrum

0 comments

The pith

If a Cayley sum graph is a non-bipartite expander then its eigenvalues stay bounded away from -1.

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

The paper proves a Cheeger-type inequality for undirected Cayley sum graphs on finite groups. When the graph is an expander with positive Cheeger constant and is non-bipartite, the non-trivial eigenvalues of the normalized adjacency operator are shown to lie in a specific interval away from -1. The lower bound is proportional to the fourth power of the Cheeger constant divided by a term depending on the degree. This matters because it connects combinatorial expansion to spectral properties in group-generated graphs, and the authors also strengthen a related result for standard Cayley graphs.

Core claim

If the undirected Cayley sum graph C_Σ(G,S) is an expander graph and is non-bipartite, then the non-trivial eigenvalues of the normalised adjacency operator lie in the interval (-1 + h(G)^4 / η, 1 - h(G)^2 / (2d^2)] where η = 2^9 d^8, with h(G) the vertex Cheeger constant and d the degree.

What carries the argument

The vertex Cheeger constant h(G) of the d-regular Cayley sum graph, which is used to derive explicit bounds on the distance of the spectrum from -1.

Load-bearing premise

The graph must be non-bipartite, as bipartiteness permits an eigenvalue of exactly -1 even if the graph expands.

What would settle it

A counterexample would be a non-bipartite d-regular Cayley sum graph with Cheeger constant h where some eigenvalue λ satisfies λ ≤ -1 + h^4 / (512 d^8).

read the original abstract

Let $G$ be a finite group and $S$ be a symmetric generating set of $G$ with $|S| = d$. We show that if the undirected Cayley sum graph $C_{\Sigma}(G,S)$ is an expander graph and is non-bipartite, then the spectrum of its normalised adjacency operator is bounded away from $-1$. We also establish an explicit lower bound for the spectrum of these graphs, namely, the non-trivial eigenvalues of the normalised adjacency operator lies in the interval $\left(-1+\frac{h(G)^{4}}{\eta}, 1-\frac{h(G)^{2}}{2d^{2}}\right]$, where $h(G)$ denotes the (vertex) Cheeger constant of the $d$-regular graph $C_{\Sigma}(G,S)$ and $\eta = 2^{9}d^{8}$. Further, we improve upon a recently obtained bound on the non-trivial spectrum of the normalised adjacency operator of the non-bipartite Cayley graph $C(G,S)$.

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 main advance is explicit spectral bounds for Cayley sum graphs plus an improvement for ordinary Cayley graphs.

read the letter

The paper establishes explicit bounds on the spectrum of the normalized adjacency operator for undirected Cayley sum graphs that are expanders and non-bipartite. The non-trivial eigenvalues fall into the interval (-1 + h(G)^4 / (512 d^8), 1 - h(G)^2 / (2d^2)], where h(G) is the Cheeger constant. This is new for the sum graph case, and they also improve an existing bound for standard Cayley graphs. The work supplies concrete constants rather than asymptotic statements, which is useful for tracking dependence on the degree and the expansion. The proof appears to follow standard techniques in spectral graph theory applied to the group setting. There are no signs of circular reasoning or invented quantities. The non-bipartite assumption is clearly needed to keep the spectrum away from -1. One limitation is that the constants, particularly the 2^9 d^8 factor, are quite large. This makes the lower bound weak for graphs with moderate expansion, though such looseness is typical in Cheeger inequalities with explicit constants. The paper is for specialists in combinatorial group theory and spectral methods on Cayley graphs. A reader interested in algebraic constructions of expanders would get the most from the explicit forms. It deserves a serious referee because the claims are precise, the setting is well-defined, and the result adds to the literature on quantitative spectral control in these graphs. I would send it to peer review.

Referee Report

0 major / 2 minor

Summary. The paper claims that if the undirected Cayley sum graph C_Σ(G,S) on a finite group G with symmetric generating set S of size d is a non-bipartite expander, then the non-trivial eigenvalues of its normalized adjacency operator lie in the interval (-1 + h(G)^4 / η, 1 - h(G)^2 / (2d^2)] with η = 2^9 d^8, where h(G) is the vertex Cheeger constant. It further improves a recent explicit bound on the non-trivial spectrum of the normalized adjacency operator for non-bipartite Cayley graphs C(G,S).

Significance. If the derivation holds, the result supplies explicit (though large) constants relating the Cheeger constant directly to a spectral interval excluding -1 for these Cayley sum graphs, strengthening the link between vertex expansion and spectral gaps in this family. The explicit form of the bounds and the improvement on the prior bound for standard Cayley graphs are concrete strengths that could support applications in constructing or analyzing expanders from groups.

minor comments (2)

§2: The definition of the Cayley sum graph C_Σ(G,S) and its normalized adjacency operator should be restated explicitly when the main theorem is stated, to avoid any ambiguity for readers focused on the spectral claim.
The constant η = 2^9 d^8 is stated without a remark on whether it is expected to be sharp or improvable; adding a brief comment on this would clarify the result's optimality.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our results and the positive assessment of their significance. The recommendation for minor revision is noted. No specific major comments appear in the report, so there are no individual points requiring detailed rebuttal or revision.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper derives explicit spectral bounds for the normalized adjacency operator of non-bipartite expander Cayley sum graphs C_Σ(G,S) directly from the standard vertex Cheeger constant h(G) (defined independently via edge expansion ratios over subsets) and degree d. The interval (-1 + h(G)^4/η, 1 - h(G)^2/(2d^2)] with η = 2^9 d^8 follows from graph expansion assumptions without any fitted parameters, self-referential definitions, or load-bearing self-citations. The non-bipartite hypothesis is stated explicitly to exclude -1 and does not create circularity. No ansatz smuggling, uniqueness theorems from prior self-work, or renaming of known results occurs in the central claim. The result is a standard first-principles inequality proof and remains independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard definitions of finite groups, symmetric generating sets, Cayley sum graphs, the normalized adjacency operator, and the vertex Cheeger constant; no new free parameters or postulated entities are introduced.

axioms (2)

standard math Finite groups admit symmetric generating sets S of finite size d.
Used to construct the d-regular Cayley sum graph C_Σ(G,S).
standard math The vertex Cheeger constant h(G) is defined and positive for expander graphs.
Appears directly in the stated eigenvalue interval.

pith-pipeline@v0.9.0 · 5704 in / 1287 out tokens · 27440 ms · 2026-05-24T20:11:07.036893+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the non-trivial eigenvalues of the normalised adjacency operator lies in the interval (−1 + h(G)^4 / η, 1 − h(G)^2 / (2d^2)], where η = 2^9 d^8
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 2.5. The Cayley sum graph CΣ(G,S) is bipartite if and only if G contains a subgroup of index two which does not intersect S.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.