Let $p(Y_1, dots, Y_d, Z_1, dots, Z_e)$ be a self-adjoint noncommutative polynomial, with coefficients from $mathbb{C}^{r times r}$, in the indeterminates $Y_1, dots, Y_d$ (considered to be self-adjoint), the indeterminates $Z_1, dots, Z_e$, and their adjoints $Z_1^*, dots, Z_e^*$. Suppose $Y_1, dots, Y_d$ are replaced by independent random $n times n$ matching matrices, and $Z_1, dots, Z_e$ are replaced by independent random $n times n$ permutation matrices. Assuming for simplicity that $p$s coefficients are $0$-$1$ matrices, the result can be thought of as a kind of random $rn$-vertex graph $G$. As $n to infty$, there will be a natural limiting infinite graph $X$ that covers any finite outcome for $G$. A recent landmark result of Bordenave and Collins shows that for any $varepsilon > 0$, with high probability the spectrum of a random $G$ will be $varepsilon$-close in Hausdorff distance to the spectrum of $X$ (once the suitably defined trivial eigenvalues are excluded). We say that $G$ is $varepsilon$-near fully $X$-Ramanujan. Our work has two contributions: First we study and clarify the class of infinite graphs $X$ that can arise in this way. Second, we derandomize the Bordenave-Collins result: for any $X$, we provide explicit, arbitrarily large graphs $G$ that are covered by $X$ and that have (nontrivial) spectrum at Hausdorff distance at most $varepsilon$ from that of $X$. This significantly generalizes the recent work of Mohanty et al., which provided explicit near-Ramanujan graphs for every degree $d$ (meaning $d$-regular graphs with all nontrivial eigenvalues bounded in magnitude by $2sqrt{d-1} + varepsilon$). As an application of our main technical theorem, we are also able to determine the eigenvalue relaxation value for a wide class of average-case degree-$2$ constraint satisfaction problems.
Download