Expansion in Distance Matrices
John Byrne, Jacob Johnston, Carl Schildkraut, Michael Tait · 2025
Read Expansion in Distance Matrices by John Byrne, Jacob Johnston, Carl Schildkraut, Michael Tait (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-10895.txt.
Introduction
John Byrne, Jacob Johnston, Carl Schildkraut, and Michael Tait proved a spectral result in twenty twenty-five about a matrix built from distances in a graph. The normalized distance Laplacian replaces the usual neighbor links with all pairwise distances, then scales them. Prior work hinted this matrix behaves very unlike its classic cousin.
The authors show that both its spectral gap and its Cheeger constant stay away from zero, no matter which graph is fed in. In plain terms, this matrix always keeps a healthy spread in its spectrum, unlike the classic version whose gap can shrink toward zero. The spectral claim holds even more broadly, for any finite metric space. The result sharpens the contrast between distance-based and neighbor-based views of a network.
Catalog record
| CREATOR | John Byrne, Jacob Johnston, Carl Schildkraut, Michael Tait |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-10895
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Expansion in Distance Matrices John Byrne, Jacob Johnston, Carl Schildkraut, Michael Tait Abstract The normalized distance Laplacian matrix 𝒟 ℒ ( G ) \mathcal{D}^{\mathcal{L}}(G) of a graph G 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 𝒟 ℒ ( G ) \mathcal{D}^{\mathcal{L}}(G) are bounded away from 0 0 independently of the graph G G . The spectral result holds more generally for finite metric spaces. 1 Introduction Given a connected graph G , one may define the distance matrix \mathcal{D} for G where the ij ’th entry of \mathcal{D} is the distance in G from vertex i to vertex j . This matrix was popularized in seminal work by Graham and Lovász [ 11 ] that was motivated by a problem out of Bell Labs regarding telephone networks [ 12 ] . The origins of the distance matrix go back to sporadic work long before this popularization, for example [ 5 , 19 ] . Since then, the matrix has been widely studied; a nice survey is given by Aouchiche and Hansen [ 4 ] . One may think of \mathcal{D} as a weighted complete graph where the weights are determined by distances in the metric space induced by G . In this framework, problems on distance matrices of graphs arise as special cases of problems on distance matrices in arbitrary finite metric spaces. For some background on this approach, see the text [ 8 ] . One may also consider other matrices that capture information about graph distance besides \mathcal{D} . Motivated by various applications, matrices such as distance Laplacian and the signless distance Laplacian have been introduced [ 3 ] . In this paper, we will study the normalized distance Laplacian matrix of a graph G (or, more generally, of a finite metric space). This matrix was introduced by Reinhart [ 16 ] and can be thought of as the classical normalized Laplacian on a weighted complete graph with weights given by distances in G (formal definitions to follow). From this perspective, the study of the normalized distance Laplacian follows a long line of work on normalized Laplacian matrices on graphs and weighted graphs, see for example [ 6 ] . The study of normalized Laplacian matrices is a fundamental problem in spectral graph theory (the text [ 6 ] has been cited over ten thousand times). Thus, when specializing to this subproblem (where the weights must come from distances in a graph), an overarching question is how the subfamily behaves differently than the general setting. Recent work on distance matrices indicates that they behave quite differently from more classical matrices like the adjacency matrix or the normalized Laplacian. For example, in [ 17 ] , it is shown that the Perron vector of \mathcal{D} must be relatively “close” to a constant vector, which is of course very different from the Perron vector of an adjacency matrix for many graphs [ 7 ] . It is a classical result that the largest eigenvalue of the normalized Laplacian matrix is equal to 2 if and only if the graph has a bipartite component. In [ 16 ] , it was shown that for graphs on more than 2 vertices, the largest eigenvalue of the normalized distance Laplacian is always strictly less than 2 (see also [ 13 ] ). Our theorems follow the same theme: we show that the normalized distance Laplacian matrix behaves in a nonstandard way with respect to “expansion.” We now state our theorems formally, after giving relevant definitions. Given a connected graph G and u\in V(G) , let t(u)=\sum_{v\in V(G)}d(u,v) be the transmission of the vertex u , and let the transmission matrix T(G) be \mathrm{diag}(t(u):u\in V(G)) . Let \mathcal{D}(G) be the distance matrix as before with \mathcal{D}_{u,v}=d(u,v) . The normalized distance Laplacian of G is \mathcal{D}^{\mathcal{L}}(G)=T(G)^{-1/2}(T(G)-\mathcal{D}(G))T(G)^{-1/2}. We will denote the n (real) eigenvalues of \mathcal{D}^{\mathcal{L}}(G) by 0=\partial_{1}<\ldots<\partial_{n}\leq 2 , and we call \partial_{2} the spectral gap of \mathcal{D}^{\mathcal{L}} . Given S\subseteq V(G) , define the volume of S as \vol S=\sum_{u\in S}t(u) and define h(S)=\frac{\sum_{u\in S,v\in\overline{S}}d(u,v)}{\min\{\vol S,\vol\overline{S}\}}. The Cheeger constant of \mathcal{D}^{\mathcal{L}} is h_{G}=\min_{\emptyset\neq S\subseteq V}h(S) . Note that these definitions agree with the classical definitions of the second eigenvalue of the normalized Laplacian and with the Cheeger constant of the weighted complete graph with weights given by distances in G , where by classical Cheeger constant we mean with respect to edge-expansion as in [ 6 ] (this constant is sometimes called the conductance ). Our first theorem gives a lower bound on the Cheeger constant of \mathcal{D}^{\mathcal{L}} and characterizes the cases of equality. Theorem 1.1 . Let G be a connected graph on n vertices and let h_{G} be the Cheeger constant for \mathcal{D}^{\mathcal{L}} . (i) If n is even, then h_{G}\geq\frac{n}{3n-4} with equality if and only if G is isomorphic to K_{n/2,n/2} . (ii) If n is odd, then h_{G}\geq\frac{n+1}{3n-5} . For n\neq 5 , equality holds if and only if G is isomorphic to a graph obtained from K_{\lfloor n/2\rfloor,\lceil n/2\rceil} by embedding at most n-1 edges in the larger part. We have excluded the n=5 case from the equality characterization in part (ii) above because there are three additional equality cases, up to isomorphism. They are the path on five vertices, a four-cycle with an additional pendant edge, and a four-cycle uvwx with a pendant edge xy and an additional edge uw . Theorem 1.1 says that the Cheeger constant for \mathcal{D}^{\mathcal{L}} is always larger than 1/3 . In contrast, the classical Cheeger constant on a connected n -vertex graph can go to 0 with n . For example, two cliques of order n/3 joined by a path of length n/3 has a Cheeger constant that decays quadratically in n . There is an intimate relationship between the Cheeger constant and the spectral gap [ 6 ] . Cheeger’s inequality gives \frac{h_{G}^{2}}{2}\leq\partial_{2}\leq 2h_{G}. (1) Since classical Cheeger constants of connected graphs can go to 0 , Cheeger’s inequality implies that the spectral gap of the normalized Laplacian can also go to 0 . With the same example as before, two cliques joined by a path of length n/3 , the spectral gap of the normalized Laplacian is asymptotic to \frac{54}{n^{3}} (and in fact this is asymptotically the minimum possible [ 1 , 2 ] ). On the other hand, Theorem 1.1 with Cheeger’s inequality implies that the spectral gap of a normalized distance Laplacian matrix is always at least \frac{1}{18} . Our second theorem is the following improvement on this bound. Theorem 1.2 . Let G be a connected graph and \partial_{2} the spectral gap of its normalized distance Laplacian matrix. Then \partial_{2}\geq\frac{9-4\sqrt{2}}{7}\approx 0.478. In fact, we believe that this lower bound can be improved to 2/3 . Conjecture 1.3 . Let G be a connected graph and \partial_{2} the spectral gap of its normalized distance Laplacian matrix. Then \partial_{2}\geq 2/3. As evidence towards Conjecture 1.3 , we provide the following, which demonstrates a special case