Eigenvalues of random lifts and polynomials of random permutation matrices (Q2334866): Difference between revisions

The authors prove, along with a number of other results, the following: suppose that \((\sigma_1,\dots,\sigma_d)\) is a finite sequence of independent random permutations, chosen uniformly among all permutations or among all matchings on \(N\) points. Then it is shown that, in probability, as \(N\to \infty\), these permutations viewed as operators on the \((N-1)\)-dimensional vector space \(\left\{(x_1,\dots,x_N)\in \mathbb{C}^N:\sum_{i=1}^Nx_i=0 \right\}\) are asymptotically strongly free. Moreover, as a byproduct, the authors obtain that the non-trivial eigenvalues of random \(N\)-lifts of a fixed base graph achieve, up to a vanishing term, the so-called Alon-Boppana lower bound with high probability as \(N\to \infty\). This settles a conjecture of \textit{J. Friedman} [Duke Math. J. 118, No. 1, 19--35 (2003; Zbl 1035.05058)]. The main contribution of this paper can in fact be understood as a novel use of non-backtracking operators, since the authors reduce the results above to establishing analogous ones for non-backtracking operators. Then, the strategy of proof of these results on non-backtracking operators is similar to the one followed by the first author to give a new proof of Friedman's theorem in [``A new proof of Friedman's second eigenvalue theorem and its extension to random lifts'', Preprint, \url{arXiv:1502.04482}], but with a number of significant refinements which require a very delicate analysis. Finally, extensions of the results mentioned above to tensor products of random permutation matrices are also discussed.