Garland's method for token graphs

The k-th token graph of a graph G=(V,E) is the graph Fk(G) whose vertices are the k-subsets of V and whose edges are all pairs of k-subsets A,B such that the symmetric difference of A and B forms an edge in G. Let L(G) be the Laplacian matrix of G, and Lk(G) be the Laplacian matrix of Fk(G). It was shown by Dalfó, Duque, Fabila-Monroy, Fiol, Huemer, Trujillo-Negrete, and Zaragoza Martínez that for any graph G on n vertices and any 0≤ℓ≤k≤⌊n/2⌋, the spectrum of Lℓ(G) is contained in that of Lk(G). Here, we continue to study the relation between the spectrum of Lk(G) and that of Lk−1(G). In particular, we show that, for 1≤k≤⌊n/2⌋, any eigenvalue λ of Lk(G) that is not contained in the spectrum of Lk−1(G) satisfiesk(λ2(L(G))−k+1)≤λ≤kλn(L(G)), where λ2(L(G)) is the second smallest eigenvalue of L(G) (also known as the algebraic connectivity of G), and λn(L(G)) is its largest eigenvalue. Our proof relies on an adaptation of Garland's method, originally developed for the study of high-dimensional Laplacians of simplicial complexes.