ﻻ يوجد ملخص باللغة العربية
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 $2sqrt{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.
Let $X$ be an infinite graph of bounded degree; e.g., the Cayley graph of a free product of finite groups. If $G$ is a finite graph covered by $X$, it is said to be $X$-Ramanujan if its second-largest eigenvalue $lambda_2(G)$ is at most the spectral
For every constant $d geq 3$ and $epsilon > 0$, we give a deterministic $mathrm{poly}(n)$-time algorithm that outputs a $d$-regular graph on $Theta(n)$ vertices that is $epsilon$-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by $2sqr
We show that for every prime $d$ and $alphain (0,1/6)$, there is an infinite sequence of $(d+1)$-regular graphs $G=(V,E)$ with girth at least $2alpha log_{d}(|V|)(1-o_d(1))$, second adjacency matrix eigenvalue bounded by $(3/sqrt{2})sqrt{d}$, and man
Ramanujan graphs have fascinating properties and history. In this paper we explore a parallel notion of Ramanujan digraphs, collecting relevant results from old and recent papers, and proving some new ones. Almost-normal Ramanujan digraphs are shown
The r-th power of a graph modifies a graph by connecting every vertex pair within distance r. This paper gives a generalization of the Alon-Boppana Theorem for the r-th power of graphs, including irregular graphs. This leads to a generalized notion o