Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Alon-Boppana theorem for powered graphs and generalized Ramanujan graphs
225
0
0.0
(
0
)
Added by
Peter Ralli
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
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$.
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.
This is the fourth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this paper we prove a {em Sidestepping Theorem} that is more general and easier to use than earlier theorems of this kind. Such theorems concerns a family probability spaces ${{mathcal{M}}_n}$ of $ntimes n$ matrices, where $n$ varies over some infinite set, $N$, of natural numbers. Many trace methods use simple Markov bounds to bound the expected spectral radius of elements of ${mathcal{M}}_n$: this consists of choosing one value, $k=k(n)$, for each $nin N$, and proving expected spectral radius bounds based on the expected value of the trace of the $k=k(n)$-power of elements of ${mathcal{M}}_n$. {em Sidestepping} refers to bypassing such simple Markov bounds, obtaining improved results using a number of values of $k$ for each fixed $nin N$. In more detail, if the $Min {mathcal{M}}_n$ expected value of ${rm Trace}(M^k)$ has an asymptotic expansion in powers of $1/n$, whose coefficients are well behaved functions of $k$, then one can get improved bounds on the spectral radius of elements of ${mathcal{M}}_n$ that hold with high probability. Such asymptotic expansions are shown to exist in the third article in this series for the families of matrices that interest us; in the fifth and sixth article in this series we will apply the Sidestepping Theorem in this article to prove the main results in this series of articles. This article is independent of all other articles in this series; it can be viewed as a theorem purely in probability theory, concerning random matrices or, equivalently, the $n$ random variables that are the eigenvalues of the elements of ${mathcal{M}}_n$.
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.
We show that the cop number of every generalized Petersen graph is at most 4. The strategy is to play a modified game of cops and robbers on an infinite cyclic covering space where the objective is to capture the robber or force the robber towards an end of the infinite graph. We prove that finite isometric subtrees are 1-guardable and apply this to determine the exact cop number of some families of generalized Petersen graphs. We also extend these ideas to prove that the cop number of any connected I-graph is at most 5.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
