Explicit near-fully X-Ramanujan graphs
Let p(Y1,…,Yd,Z1,…,Ze) be a self-adjoint noncommutative polynomial, with coefficients from Cr×r, in the indeterminates Y1,…,Yd (considered to be self-adjoint), the indeterminates Z1,…,Ze, and their adjoints Z1∗,…,Ze∗. Suppose Y1,…,Yd are replaced by independent random n×n matching matrices, and Z1,…,Ze 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→∞, 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 2d−1+ε). 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.
