pith. sign in

arxiv: 2606.08061 · v1 · pith:7ZBXDL2Dnew · submitted 2026-06-06 · 🧮 math.CO · math.SP

Cheeger-type inequalities for the second largest spectral gap from 1 of the normalized Laplacian

Lies Beers , Raffaella Mulas , Jan Petr This is my paper

Pith reviewed 2026-06-27 19:29 UTC · model grok-4.3

classification 🧮 math.CO math.SP
keywords normalized LaplacianCheeger inequalitiesspectral gaptwo-step random walksgraph expansionexpander graphsRamanujan graphs
0
0 comments X

The pith

A new Cheeger-type constant defined by two-step random walks yields sharp bounds on the second largest gap from 1 in the normalized Laplacian spectrum.

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

The paper focuses on the second largest eigenvalue gap away from 1 for the normalized Laplacian of an undirected graph. It first relates this gap to the usual Cheeger constant and its dual version. The authors then define a fresh Cheeger-type quantity whose value equals the worst-case probability that a two-step random walk leaves a set or returns to it. For this quantity they prove inequalities that bound the spectral gap from above and below, with the same sharpness as the classical Cheeger inequalities. The relations give direct ways to translate expansion properties of two-step walks into spectral information and back.

Core claim

The authors introduce a Cheeger-type constant that admits a probabilistic interpretation in terms of two-step random walks and establish sharp inequalities that relate this constant to the second largest spectral gap from 1 of the normalized Laplacian, in exact analogy with the classical Cheeger inequalities.

What carries the argument

The new Cheeger-type constant measuring the minimum two-step escape probability over all vertex subsets.

If this is right

  • The second spectral gap is sandwiched between two multiples of the new constant, with explicit constants matching the classical case.
  • Bounds on the new constant immediately translate into bounds on the second gap for any graph.
  • The same constant controls expansion properties visible after exactly two steps of a random walk.
  • The inequalities remain valid for both regular and irregular graphs because the normalized Laplacian is used throughout.

Where Pith is reading between the lines

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

  • The construction may extend to higher-order Cheeger constants that track k-step walks for k greater than 2.
  • Numerical approximation of the new constant via short random-walk simulations could yield practical estimates of the second gap without full eigen-computation.
  • The same two-step view might connect the gap to mixing times of non-reversible or lifted Markov chains on the graph.

Load-bearing premise

The two-step random-walk interpretation of the new constant is sufficient by itself to produce the claimed sharp inequalities.

What would settle it

A concrete finite graph on which the proved upper or lower bound between the new constant and the second spectral gap fails to hold.

Figures

Figures reproduced from arXiv: 2606.08061 by Jan Petr, Lies Beers, Raffaella Mulas.

Figure 1
Figure 1. Figure 1: A petal graph. Example 4.14. The m-petal graph on n = 2m + 1 vertices ( [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The graphs from Table 1. Cyan vertices form sets [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
read the original abstract

We study the second largest spectral gap from $1$ of the normalized Laplacian of a graph, a quantity that appears in the literature in connection with random walks, expander graphs, and Ramanujan graphs. We relate it to the classical Cheeger and dual Cheeger constants, and we introduce a new Cheeger-type constant admitting a probabilistic interpretation in terms of two-step random walks. For this constant, we establish sharp inequalities analogous to the classical Cheeger inequalities.

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.

Referee Report

0 major / 1 minor

Summary. The manuscript studies the second largest spectral gap from 1 of the normalized Laplacian, relating this quantity to the classical Cheeger and dual Cheeger constants. It introduces a new Cheeger-type constant with a probabilistic interpretation via two-step random walks and establishes sharp inequalities for the spectral gap that are analogous to the classical Cheeger inequalities.

Significance. If the claimed sharp inequalities hold with the stated probabilistic interpretation, the work would extend the classical Cheeger framework to a different spectral quantity relevant to random walks, expanders, and Ramanujan graphs. The two-step random walk device is a standard and potentially effective tool for deriving such bounds, and the paper's focus on sharpness mirrors successful prior results in spectral graph theory.

minor comments (1)
  1. The abstract asserts the existence of sharp inequalities but the provided text supplies no explicit definitions, statements of the new constant, or proof sketches; the full manuscript should include these to allow verification of the central claims.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their review of our manuscript. The provided summary correctly captures the paper's focus on relating the second largest spectral gap from 1 of the normalized Laplacian to classical Cheeger and dual Cheeger constants, as well as the introduction of a new constant with a two-step random walk interpretation and the derivation of sharp inequalities. No major comments appear in the report, so we have no specific points to address. We remain available to clarify any aspects that led to the 'uncertain' recommendation.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper relates the second-largest spectral gap of the normalized Laplacian to classical Cheeger constants, introduces a new constant via a two-step random walk interpretation, and proves sharp inequalities by direct analogy to the classical case. No load-bearing step reduces by definition, by fitting, or by self-citation chain to the paper's own inputs; the probabilistic interpretation is a standard device for bounding Rayleigh quotients and does not create a self-referential loop. The work is a standard extension in spectral graph theory whose central claims remain independent of any internal redefinition or renaming.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, axioms, or invented entities are stated in the provided text.

pith-pipeline@v0.9.1-grok · 5599 in / 1042 out tokens · 18326 ms · 2026-06-27T19:29:42.698881+00:00 · methodology

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

16 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    Bauer, B.B

    F. Bauer, B.B. Hua, and J. Jost. The dual Cheeger constant and spectra of infinite graphs. Adv. Math., 251:147–194, 2014

    2014

  2. [2]

    Bauer and J

    F. Bauer and J. Jost. Bipartite and neighborhood graphs and the spectrum of the normal- ized graph Laplace operator.Comm. Anal. Geom., 21(4):787–845, 2013

    2013

  3. [3]

    Beers and R

    L. Beers and R. Mulas. At the end of the spectrum: chromatic bounds for the largest eigenvalue of the normalized Laplacian.Journal of Physics: Complexity, 6(2):025006, 2025

    2025

  4. [4]

    Chang, S

    K.C. Chang, S. Shao, and D. Zhang. Spectrum of the signless 1-Laplacian and the dual Cheeger constant on graphs. arXiv:1607.00489

    work page arXiv

  5. [5]

    Chung.Spectral graph theory

    F. Chung.Spectral graph theory. American Mathematical Soc., 1997

    1997

  6. [6]

    Coutinho, R

    G. Coutinho, R. Grandsire, and C. Passos. Colouring the Normalized Laplacian.Electronic Notes in Theoretical Computer Science, 346:345–354, August 2019

    2019

  7. [7]

    Elphick and P

    C. Elphick and P. Wocjan. Unified spectral bounds on the chromatic number.Discuss. Math. Graph Theory, 35(4):773–780, 2015

    2015

  8. [8]

    Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)

    V. Guruswami. Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey). arXiv:1603.01512, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  9. [9]

    J. Jost, R. Mulas, and D. Zhang. Petals and books: the largest Laplacian spectral gap from 1.J. Graph Theory, 104(4):727–756, 2023

    2023

  10. [10]

    J. Jost, R. Mulas, and D. Zhang.Spectra of Discrete Structures. Number 221 in Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2026

    2026

  11. [11]

    Levin, Y

    D.A. Levin, Y. Peres, and E.L. Wilmer.Markov Chains and Mixing Times, volume 107. American Mathematical Soc., 2017

    2017

  12. [12]

    Lubotzky, R

    A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs.Combinatorica, 8(3):261–277, 1988

    1988

  13. [13]

    M.R. Murty. Ramanujan graphs.Journal of the Ramanujan Mathematical Society, 18(1):33–52, 2003. 26

    2003

  14. [14]

    Nikiforov

    V. Nikiforov. Chromatic number and spectral radius.Linear Algebra Appl., 426(2-3):810– 814, 2007

    2007

  15. [15]

    Sun and K.C

    S. Sun and K.C. Das. Normalized Laplacian eigenvalues with chromatic number and inde- pendence number of graphs.Linear and Multilinear Algebra, 68(1):63–80, 2020

    2020

  16. [16]

    Trevisan

    L. Trevisan. Lecture notes on graph partitioning, expanders and spectral methods.https: //lucatrevisan.github.io/books/expanders-2016.pdf, 2017. University of California, Berkeley. Accessed: May 2026. 27

    2016