论文标题
显式接近X-Ramanujan图
Explicit near-fully X-Ramanujan graphs
论文作者
论文摘要
令$ p（y_1，\ dots，y_d，z_1，\ dots，z_e）$为一个自动化的非共同多项式，具有$ \ mathbb {c}^{r \ times r} $的系数\ dots，z_e $及其伴随$ z_1^*，\ dots，z_e^*$。假设$ y_1，\ dots，y_d $被独立的随机$ n \ times n $匹配矩阵，$ z_1，\ dots，z_e $替换为独立的随机$ n \ times n $ permainoontuntrices。假设为简单起见，$ p $的系数为$ 0 $ - $ 1 $矩阵，则可以将结果视为一种随机的$ rn $ vertex图$ g $。作为$ n \ to \ infty $，将有一个自然限制的无限图$ x $，涵盖$ g $的任何有限结果。 Bordenave和Collins的最新里程碑结果表明，对于任何$ \ Varepsilon> 0 $，随机$ G $的频谱将为$ \ VAREPSILON $ - 在Hausdorff的距离上到达$ x $的光谱（一旦适当定义的“ Trivial” eigenvalues被排除在外）。我们说$ g $是“ $ \ varepsilon $ - 完全$ x $ -ramanujan”。我们的工作有两个贡献：首先，我们研究并阐明了可以以这种方式出现的无限图$ x $的类别。其次，我们将Bordenave-Collins的结果取代：对于任何$ x $，我们提供了$ x $覆盖的明确，任意的大图$ g $，并且在$ x $中最多可以在Hausdorff Desparion of Hausdorff Desparion（非平凡）频谱。这显着概括了Mohanty等人的最新工作，该工作为每个度$ d $ $ d $（意味着$ d $ ramanujan）的明确图形（意味着所有非平凡的特征值都以$ 2 \ sqrt {d-1} + \ varepsilon $的限制）。作为我们主要技术定理的应用，我们还能够确定一系列平均案例学位的“特征值放松价值” - $ 2 $约束满意度问题。
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.
