Expansion in Distance Matrices

2025/03/13 by J. Byrne, Byrne, John, Carl Schildkraut +4
Computer Science · Mathematics · #Advanced Topics in Algebra #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.2503.10895

openalex publication_date 2025/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The normalized distance Laplacian matrix D^L(G) of a graph G is a natural generalization of the normalized Laplacian matrix, arising from the matrix of pairwise distances between vertices rather than the adjacency matrix. Following the motif that this matrix behaves quite differently to the normalized Laplacian matrix, we show that both the spectral gap and Cheeger constant of D^L(G) are bounded away from 0 independently of the graph G. The spectral result holds more generally for finite metric spaces.

Related

• The normalized distance Laplacian
• Extremal values for the spectral radius of the normalized distance Laplacian
• Spectra of variants of distance matrices of graphs and digraphs: a survey
• Distance matrix correlation spectrum of graphs
• On spectral spread of generalized distance matrix of a graph