Explicit nonbipartite Ramanujan graphs of every degree

Theorem 1.1: for every $d\ge3$ there are $n_0(d)$, $k_d$ and a deterministic algorithm that, on every even $n\ge n_0(d)$, outputs the adjacency list of a simple connected nonbipartite $d$-regular graph on $n$ vertices whose nonconstant eigenvalues lie strictly between $\pm2\sqrt{d-1}$, in $O_d(n^{k_d})$ bit operations. The construction uses partial pairings, deterministic resolvent estimates, cleanup and an exact spectral repair step. It is not strongly explicit (no local adjacency queries), and the exponent may grow with $d$.

Theorem 1.1: for every $d\ge3$ there are $n_0(d)$, $k_d$ and a deterministic algorithm that, on every even $n\ge n_0(d)$, outputs the adjacency list of a simple connected nonbipartite $d$-regular graph on $n$ vertices whose nonconstant eigenvalues lie strictly between $\pm2\sqrt{d-1}$, in $O_d(n^{k_d})$ bit operations. The construction uses partial pairings, deterministic resolvent estimates, cleanup and an exact spectral repair step. It is not strongly explicit (no local adjacency queries), and the exponent may grow with $d$.