Explicit near-fully X-Ramanujan graphs

Let ppY 1 , . . . , Y d , Z 1 , . . . , Z e q be a self-adjoint noncommutative polynomial, with coefficients from C rˆr , in the indeterminates Y 1 , . . . , Y d (considered to be self-adjoint), the indeterminates Z 1 , . . . , Z e , and their adjoints Z 1 , . . . , Z e . Suppose Y 1 , . . . , Y d are replaced by independent random n ˆn matching matrices, and Z 1 , . . . , Z e are replaced by independent random n ˆ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 Ñ 8, 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 ε ą 0, with high probability the spectrum of a random G will be ε-close in Hausdorff distance to the spectrum of X (once the suitably defined "trivial" eigenvalues are excluded). We say that G is "ε-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 ε 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 ?

d ´1 `ε). To give two simple examples:

‚ For any d ě c ě 2 we obtain explicit arbitrarily large pc, dq-biregular graphs whose spectrum (excluding 0, ˘?cd) is ε-close in Hausdorff distance to r´p ? d ´1 ?c ´1q, ´p? d ´1 ´?c ´1qs Y rp ? d ´1 ´?c ´1q, p ? d ´1 ?c ´1qs.

‚ We obtain explicit arbitrarily large graphs covered by the modular group -i.e., 3-regular graphs in which every vertex participates in a triangle -whose spectrum (excluding 3