  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 $2\sqrt{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.
