arXiv preprint ·
Strong Convergence for Zig-Zag Products and Typical Spectra of Irregular Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We investigate the following: do existence bounds obtained by interlacing methods describe the spectra of typical random graphs? Depending on the model, we provide both positive and negative answers. We establish a Friedman-type theorem for zig-zag products of random regular graphs $G$ with a fixed vertex-transitive gadget $H$, where $G$ is sampled from independent permutations or matchings. We prove that the new spectrum converges in Hausdorff distance to that of the zig-zag product of the infinite regular tree with $H$. In particular, the new spectral radius converges to the sharp threshold established by Cohen, Cohen, and Maor. We establish the spectral limit using strong convergence and, drawing on quantitative estimates of Chen, Garza-Vargas, Tropp, and van Handel, obtain an $O(1/n)$ upper-tail bound in the permutation model. For the irregular configuration model, we show that the interlacing bound of Cohen and Maor, asymptotically $2\sqrt{μ-1}/μ$ for limiting average degree $μ$, is atypical: for uniformly bounded degree sequences with a nonconstant limiting degree law of minimum $δ\ge 2$, a random graph exceeds the interlacing bound by a positive constant with high probability. This gap is explained by the limiting spectral distribution, whose support edge is $2\sqrt{δ-1}/δ$. Strikingly, unlike the familiar behavior of random regular graphs, our experiments reveal second eigenvalues that remain far below this limiting edge even for the largest graphs tested. For $δ\ge3$, we propose that the scarcity of minimum-degree trees explains this behavior; estimates for their size suggest spectral witnesses within $O\left((\log\log n)^{-2}\right)$ of the limiting edge, which is consistent with our numerical observations.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Probability
Get the few papers worth your time in Probability every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.