When Does Sublinear Nystr\"om Sampling Preserve Laplacian Spectral Gaps?

We study whether sublinear {Nystr\"om} sampling preserves the spectral gap of the symmetric normalized graph Laplacian. For a finite undirected graph with positive degrees, we work with the shifted positive semidefinite kernel $K=2I-L_{\mathrm{sym}}$ and evaluate the relative error in $\gamma_k=\lambda_{k+1}-\lambda_k$. A deterministic perturbation result shows that if the fixed-operator {Nystr\"om} residual satisfies $\|K_{\mathrm{Ny}}(S)-K\|_2\le 0.05\gamma_k$, then the relative gap error is at most $10\%$. The executed validation does not support the stronger sampling hypothesis: leverage-family policies reached the nominal target on only a small minority of eligible graph--dimension cells, and uniform sampling was often competitive at matched budgets. Coherence and vertex-resistance diagnostics help organize failure regimes but do not by themselves supply a gap-preservation law. The resulting contribution is a conditional theorem, an evidence-backed negative result for the tested regime, and a sharper specification of the residual-scale theory needed for reliable graph eigengap sketching.