Sarah Timhadjelt

We consider a random bistochastic matrix of size $N$ of the form $(1-r)M + rQ$ where $0<r<1$, $M$ is a uniformly distributed permutation and $Q$ is a given bistochastic matrix. Under sparsity and regularity assumptions on the $*$-distribution of $Q$ (that is the normalized trace of polynomials in $Q$ and $Q^*$), we prove that the second largest eigenvalue of $(1-r)M + rQ$ is essentially bounded by an approximation of the spectral radius of a deterministic asymptotic equivalent given by free probability theory. This upper-bound has application in graph theory, for instance for the construction of graph expander.