Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHigh-girth near-Ramanujan graphs with localized eigenvectors
258
0
0.0
(
0
)
Added by
Nikhil Srivastava
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 many eigenvectors fully localized on small sets of size $O(|V|^alpha)$. This strengthens the results of Ganguly-Srivastava, who constructed high girth (but not expanding) graphs with similar properties, and may be viewed as a discrete analogue of the scarring phenomenon observed in the study of quantum ergodicity on manifolds. Key ingredients in the proof are a technique of Kahale for bounding the growth rate of eigenfunctions of graphs, discovered in the context of vertex expansion and a method of ErdH{o}s and Sachs for constructing high girth regular graphs.
rate research
Read More
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 radius $rho(X)$ of $X$, and more generally $k$-quasi-$X$-Ramanujan if $lambda_k(G)$ is at most $rho(X)$. In case $X$ is the infinite $Delta$-regular tree, this reduces to the well known notion of a finite $Delta$-regular graph being Ramanujan. Inspired by the Interlacing Polynomials method of Marcus, Spielman, and Srivastava, we show the existence of infinitely many $k$-quasi-$X$-Ramanujan graphs for a variety of infinite $X$. In particular, $X$ need not be a tree; our analysis is applicable whenever $X$ is what we call an additive product graph. This additive product is a new construction of an infinite graph $mathsf{AddProd}(A_1, dots, A_c)$ from finite atom graphs $A_1, dots, A_c$ over a common vertex set. It generalizes the notion of the free product graph $A_1 * cdots * A_c$ when the atoms $A_j$ are vertex-transitive, and it generalizes the notion of the universal covering tree when the atoms $A_j$ are single-edge graphs. Key to our analysis is a new graph polynomial $alpha(A_1, dots, A_c;x)$ that we call the additive characteristic polynomial. It generalizes the well known matching polynomial $mu(G;x)$ in case the atoms $A_j$ are the single edges of $G$, and it generalizes the $r$-characteristic polynomial introduced in [Ravichandran16, Leake-Ravichandran18]. We show that $alpha(A_1, dots, A_c;x)$ is real-rooted, and all of its roots have magnitude at most $rho(mathsf{AddProd}(A_1, dots, A_c))$. This last fact is proven by generalizing Godsils notion of treelike walks on a graph $G$ to a notion of freelike walks on a collection of atoms $A_1, dots, A_c$.
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.
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 $2sqrt{d-1} + epsilon$ (excluding the single trivial eigenvalue of~$d$).
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 of Ramanujan graphs, those for which the powered graph has a spectral gap matching the derived Alon-Boppana bound. In particular, we show that certain graphs that are not good expanders due to local irregularities, such as Erdos-Renyi random graphs, become almost Ramanujan once powered. A different generalization of Ramanujan graphs can also be obtained from the nonbacktracking operator. We next argue that the powering operator gives a more robust notion than the latter: Sparse Erdos-Renyi random graphs with an adversary modifying a subgraph of log(n)^c$ vertices are still almost Ramanujan in the powered sense, but not in the nonbacktracking sense. As an application, this gives robust community testing for different block models.
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 to be of special interest, as they are extreme in the sense of an Alon-Boppana theorem, and they have remarkable combinatorial features, such as small diameter, Chernoff bound for sampling, optimal covering time and sharp cutoff. Other topics explored are the connection to Cayley graphs and digraphs, the spectral radius of universal covers, Alons conjecture for random digraphs, and explicit constructions of almost-normal Ramanujan digraphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
