Given a non-commutative polynomial $P$ in non-commuting unitary variables and their inverse, we consider a sequence of random matrices $P_n$ in the $n\times n$ matrices obtained by replacing the unitary variables by random i.i.d permutations on n points (viewed as unitary $n\times n$ matrices). Free probability predicts, with high probability in the large dimension limit, the behavior of most singular values of $P_n$. We will show that this prediction extends to the second largest singular value of $P_n$, i.e. that it converges with high probability to the operator norm of $P$ in the reduced C*-algebra of the free group. Time allowing, we will discuss some points of the proof (requiring the development of a non-commutative version of non-backtracking operator theory) and some applications to random graph theory. This talk is based on joint work with Charles Bordenave (CNRS).