Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExplicit near-Ramanujan graphs of every degree
103
0
0.0
(
0
)
Added by
Sidhanth Mohanty
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$).
rate research
Read More
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.
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.
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$.
Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unknown phylogenetic tree. BMGs are explained by unique least resolved trees. We prove that the property of a rooted, leaf-colored tree to be least resolved for some BMG is preserved by the contraction of inner edges. For the special case of two-colored BMGs, this leads to a characterization of the least resolved trees (LRTs) of binary-explainable trees and a simple, polynomial-time algorithm for the minimum cardinality completion of the arc set of a BMG to reach a BMG that can be explained by a binary tree.
A graph $G = (V,E)$ is a double-threshold graph if there exist a vertex-weight function $w colon V to mathbb{R}$ and two real numbers $mathtt{lb}, mathtt{ub} in mathbb{R}$ such that $uv in E$ if and only if $mathtt{lb} le mathtt{w}(u) + mathtt{w}(v) le mathtt{ub}$. In the literature, those graphs are studied as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs, which gives connections to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [COCOON 2018] ran in $O(n^6)$ time, where $n$ is the number of vertices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
