Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry
For researchers in graph theory, spectral graph theory, and tensor networks, this paper provides fundamental spectral bounds on graph embedding congestion, with direct implications for the memory and time complexity of tensor network contraction.
This work establishes spectral bounds on the congestion of embedding arbitrary graphs into binary tree leaves, showing congestion lies between λ₂(G)·2n/9 and λₙ(G)·n/4, with an embedding achieving at most λₙ(G)·2n/9. Exact congestion is determined for hypercubes and lattices, and asymptotically tight bounds are given for random graphs. The results provide new spectral bounds on the complexity of tensor network contraction.
Embedding the vertices of arbitrary graphs into trees while minimizing some measure of overlap is an important problem with applications in computer science and physics. In this work, we consider the problem of bijectively embedding the vertices of an $n$-vertex graph $G$ into the \textit{leaves} of an $n$-leaf \textit{rooted binary tree} $\mathcal{T}$. The congestion of such an embedding is given by the largest size of the cut induced by the two components obtained by deleting any vertex of $\mathcal{T}$. We show that for any embedding, the congestion lies between $λ_2(G)\cdot 2n/9$ and $λ_n(G)\cdot n/4$, letting $0=λ_1(G)\le \cdots \le λ_n(G)$ be the Laplacian eigenvalues of $G$, and there is an embedding for which the congestion is at most $λ_n(G)\cdot 2n/9$. Beyond these general bounds, we determine the congestion exactly for hypercubes and lattice graphs, and obtain asymptotically tight bounds for random regular graphs and Erdős-Rényi graphs. We further introduce an efficient contraction procedure based on spectral ordering and dynamic programming, which produces low-congestion embeddings in practice. Numerical experiments on structured graphs, random graphs, and tensor network representations of quantum circuits validate our theoretical bounds and demonstrate the effectiveness of the proposed method. These results yield new spectral bounds on the memory and time complexity of exact tensor network contraction in terms of the underlying graph structure.