Mutasim Mim

mathjax.axby.world
Discrete Hodge theory · spectral graph theory · combinatorics
notes-first pages · MathJax everywhere · print-friendly

What “spectral gap” means here

Terminology varies across communities. This note pins down the quantities used on this site.

Graph spectral gap

For a $d$-regular graph with adjacency matrix $A$, the standard “expander gap” is $$d-\lambda_2(A),$$ equivalently the smallest positive eigenvalue of the vertex Laplacian $L_0=dI-A$.

Higher Laplacian gap

For a PSD operator $L_k$, the natural analogue is $$\lambda_{\min}^+(L_k),$$ the smallest eigenvalue on $(\ker L_k)^\perp$. In particular, for the 1-Laplacian on edges: $$L_1(T)=L_1^{\downarrow}+L_1^{\uparrow}(T).$$

Why the “$+$” matters
kernel-aware

The kernel of $L_k$ encodes harmonic forms / homology. When comparing complexes (changing $T$), the dimension of the kernel may change, so the smallest positive eigenvalue is the stable notion.

Two-piece intuition

Since $L_1=L_1^{\downarrow}+L_1^{\uparrow}$, a rough heuristic is that the smaller piece governs the bottleneck. Making $L_1^{\uparrow}$ strong enough that it no longer bottlenecks is a natural “saturation point.”

The hard part is rarely $L_1^{\downarrow}$ (it’s tied to $L_0$). The hard part is understanding how triangle selection controls $L_1^{\uparrow}$.