{"id":"arxiv/2606.07459","url":"https://arxiv.org/abs/2606.07459","tags":["math.CO","cs.DS"],"score":0,"title":"Adjacency Spectral Radius Under Laplacian Sparsification: Deterministic and Probabilistic Bounds","domain":"math.CO","source":"arxiv","authors":["Joshua Steier"],"reviews":0,"subject":"math.CO","summary":"Spielman-Srivastava spectral sparsification preserves Laplacian quadratic forms to within (1 +/- epsilon), but does not directly control the adjacency spectral radius lambda_1, which governs the NIMFA epidemic threshold and arises in spectral clustering. We prove |lambda_1(A_H) - lambda_1(A_G)| <= epsilon(2 Delta - lambda_1) deterministically, with a sharp epsilon*lambda_1 bound for reweighting sparsifiers via Perron-Frobenius monotonicity. Under effective-resistance sampling, Matrix Bernstein gives O(epsilon Delta / sqrt(c)) with high probability. Combining eigenvector delocalization with…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-05","reactions":{}}