Explicit near-fully X-Ramanujan graphs

arXiv2009.02595MaRDI QIDQ6348484FDOQ6348484

Authors: Ryan O'Donnell, Xinyu Wu 

Publication date: 5 September 2020

Abstract: Let $p(Y_1,dots,Y_d,Z_1,dots,Z_e)$ be a self-adjoint noncommutative polynomial, with coefficients from $mathbb{C}^{rimesr}$, 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^{\ast },dots,Z_e^{\ast }$. Suppose $Y_1,dots,Y_d$ are replaced by independent random $nimesn$ matching matrices, and $Z_1,dots,Z_e$ are replaced by independent random $nimesn$ 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 $noinfty$, 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 $2sqrtd-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.

This page was built for publication: Explicit near-fully X-Ramanujan graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348484)