This is an item on Ramanujan Graphs for a planned encyclopedia on Ramanujan. The notion of Ramanujan graphs is explained, as well as the reason to name these graphs after …
This is an item on Ramanujan Graphs for a planned encyclopedia on Ramanujan. The notion of Ramanujan graphs is explained, as well as the reason to name these graphs after Ramanujan.
This is an item on Ramanujan Graphs for a planned encyclopedia on Ramanujan. The notion of Ramanujan graphs is explained, as well as the reason to name these graphs after …
This is an item on Ramanujan Graphs for a planned encyclopedia on Ramanujan. The notion of Ramanujan graphs is explained, as well as the reason to name these graphs after Ramanujan.
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
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 …
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, Alon's conjecture for random digraphs, and explicit constructions of almost-normal Ramanujan digraphs.
In this article we give an overview of the development of Ramanujan graphs. We explain how the subject started, the known explicit constructions of such graphs, the analogy between the …
In this article we give an overview of the development of Ramanujan graphs. We explain how the subject started, the known explicit constructions of such graphs, the analogy between the spectral analysis of graphs and Riemannian manifolds, the distribution of the spectra of regular graphs, and an application from graph theory to modular forms. 1991 Mathematics Subject Cassification: 05C75, 11F11, 11T23
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 …
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 [Ravichandran'16, Leake-Ravichandran'18]. 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 Godsil's 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 $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 …
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 $λ_2(G)$ is at most the spectral radius $ρ(X)$ of $X$, and more generally $k$-quasi-$X$-Ramanujan if $λ_k(G)$ is at most $ρ(X)$. In case $X$ is the infinite $Δ$-regular tree, this reduces to the well known notion of a finite $Δ$-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 $α(A_1, \dots, A_c;x)$ that we call the additive characteristic polynomial. It generalizes the well known matching polynomial $μ(G;x)$ in case the atoms $A_j$ are the single edges of $G$, and it generalizes the $r$-characteristic polynomial introduced in [Ravichandran'16, Leake-Ravichandran'18]. We show that $α(A_1, \dots, A_c;x)$ is real-rooted, and all of its roots have magnitude at most $ρ(\mathsf{AddProd}(A_1, \dots, A_c))$. This last fact is proven by generalizing Godsil's 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 construct an infinite family of (q+1)-regular Ramanujan graphs X_n of girth 1. We also give covering maps X_{n+1} --> X_n such that the minimal common covering of all the …
We construct an infinite family of (q+1)-regular Ramanujan graphs X_n of girth 1. We also give covering maps X_{n+1} --> X_n such that the minimal common covering of all the graphs is the universal covering tree.
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 …
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 λ2(G) is at most the spectral radius ρ(X) of X, and more generally k-quasi-X-Ramanujan if λk(G) is at most ρ(X). In case X is the infinite Δ-regular tree, this reduces to the well known notion of a finite Δ-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 A1 ⌖ ··· ⌖ Ac from finite atom graphs A1,...,Ac over a common vertex set. It generalizes the notion of the free product graph A1 * ··· * Ac when the atoms Aj are vertex-transitive, and it generalizes the notion of the universal covering tree when the atoms Aj are single-edge graphs. Key to our analysis is a new graph polynomial α(A1,...,Ac; x) that we call the additive characteristic polynomial. It generalizes the well known matching polynomial μ(G; x) in case the atoms Aj are the single edges of G, and it generalizes the r-characteristic polynomial introduced in [Rav16, LR18]. We show that α(A1,..., Ac; x) is real-rooted, and all of its roots have magnitude at most ρ(A1 ⌖ ··· ⌖ Ac). This last fact is proven by generalizing Godsil's notion of treelike walks on a graph G to a notion of freelike walks on a collection of atoms A1,..., Ac.
Ramanujan graphs are graphs whose spectrum is bounded optimally. Such graphs have found numerous applications in combinatorics and computer science. In recent years, a high dimensional theory has emerged. In …
Ramanujan graphs are graphs whose spectrum is bounded optimally. Such graphs have found numerous applications in combinatorics and computer science. In recent years, a high dimensional theory has emerged. In this paper these developments are surveyed. After explaining their connection to the Ramanujan conjecture we will present some old and new results with an emphasis on random walks on these discrete objects and on the Euclidean spheres. The latter lead to "golden gates" which are of importance in quantum computation.
A diagram D is a graph that is of finite volume with respect to a measure (weights) on the vertices and edges. The author gives the basic definitions for a …
A diagram D is a graph that is of finite volume with respect to a measure (weights) on the vertices and edges. The author gives the basic definitions for a diagram, and defines the cases where it is an expander. Let $\Delta $ be the Laplacian on $L_2 ( D )$, and let $\lambda $ be the infimum of its spectrum on the subspace of functions that are orthogonal to the constant function. The strong connection between $\lambda $ being large and D being a good expander is shown. For a k-regular infinite diagram, the largest possible $\lambda $ is $k - 2\sqrt {k - 1} $, and when this is achieved, it is called a Ramanujan diagram. Using representation theory of $PGL_2 $, many infinite families of infinite Ramanujan diagrams are explicitly constructed.
Ramanujan hypergraphs or bigraphs (bipartite biregular graphs) are to the biregular tree what Ramanujan graphs are to the homogeneous tree. A survey of the known constructions is given. Of special …
Ramanujan hypergraphs or bigraphs (bipartite biregular graphs) are to the biregular tree what Ramanujan graphs are to the homogeneous tree. A survey of the known constructions is given. Of special interest is the case when the bidegree (k, l) is non-symmetric, i.e. k ≠l. The case of r—partite graphs is sketched out and a connection with buildings and chamber systems is looked at. The concept of universal cover of a family of finite graphs by an infinite locally finite graph is emphasized.
This chapter is an introduction to the theory of expanders and Ramanujan graphs. It is based mainly on the exposition in the monograph by Davidoff- Sarnak-Valette [49] and the paper …
This chapter is an introduction to the theory of expanders and Ramanujan graphs. It is based mainly on the exposition in the monograph by Davidoff- Sarnak-Valette [49] and the paper [74]. First of all, we present the basic theorems of Alon-Milman and Dodziuk, and of Alon-Boppana-Serre, on the isoperimetric constant and the spectral gap of a (finite, undirected, connected) regular graph, and their connections. We discuss a few examples with explicit computations showing optimality of the bounds given by the above theorems. Then we give the basic definitions of expanders and describe three fundamental constructions due to Margulis, Alon-Schwartz-Schapira (based on the replacement product, cf. Section 8.12), and Reingold-Vadhan-Wigderson [128] (based on the zig-zag product, cf. Section 8.13). In these constructions, the harmonic analysis on finite Abelian groups (cf. Chapter 2) and finite fields (cf. Chapter 6) we developed so far, plays a crucial role.
Let [Formula: see text] denote a connected [Formula: see text]-regular undirected graph of finite order [Formula: see text]. The graph [Formula: see text] is called Ramanujan whenever [Formula: see text] …
Let [Formula: see text] denote a connected [Formula: see text]-regular undirected graph of finite order [Formula: see text]. The graph [Formula: see text] is called Ramanujan whenever [Formula: see text] for all nontrivial eigenvalues [Formula: see text] of [Formula: see text]. We consider the variant [Formula: see text] of the Ihara Zeta function [Formula: see text] of [Formula: see text] defined by [Formula: see text] The function [Formula: see text] satisfies the functional equation [Formula: see text]. Let [Formula: see text] denote the number sequence given by [Formula: see text] In this paper, we establish the equivalence of the following statements: (i) [Formula: see text] is Ramanujan; (ii) [Formula: see text] for all [Formula: see text]; (iii) [Formula: see text] for infinitely many even [Formula: see text]. Furthermore, we derive the Hasse–Weil bound for the Ramanujan graphs.
Mixing (or quasirandom) properties of the natural transition matrix associated to a graph can be quantified by its distance to the complete graph. Different mixing properties correspond to different norms …
Mixing (or quasirandom) properties of the natural transition matrix associated to a graph can be quantified by its distance to the complete graph. Different mixing properties correspond to different norms to measure this distance. For dense graphs, two such properties known as spectral expansion and uniformity were shown to be equivalent in seminal 1989 work of Chung, Graham and Wilson. Recently, Conlon and Zhao extended this equivalence to the case of sparse vertex transitive graphs using the famous Grothendieck inequality. Here we generalize these results to the non-commutative, or `quantum', case, where a transition matrix becomes a quantum channel. In particular, we show that for irreducibly covariant quantum channels, expansion is equivalent to a natural analog of uniformity for graphs, generalizing the result of Conlon and Zhao. Moreover, we show that in these results, the non-commutative and commutative (resp.) Grothendieck inequalities yield the best-possible constants.
Hypergraph expanders are hypergraphs with surprising, non-intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, of 3-uniform hypergraph expanders with polylogarithmic …
Hypergraph expanders are hypergraphs with surprising, non-intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, of 3-uniform hypergraph expanders with polylogarithmic degree. We generalize this construction, giving a simple construction of r-uniform hypergraph expanders for all r ⩾ 3 .
We derive several upper bounds on the spectral gap of the Laplacian with standard or Dirichlet vertex conditions on compact metric graphs. In particular, we obtain estimates based on the …
We derive several upper bounds on the spectral gap of the Laplacian with standard or Dirichlet vertex conditions on compact metric graphs. In particular, we obtain estimates based on the length of a shortest cycle (girth), diameter, total length of the graph, as well as further metric quantities introduced here for the first time, such as the avoidance diameter. Using known results about Ramanujan graphs, a class of expander graphs, we also prove that some of these metric quantities, or combinations thereof, do not to deliver any spectral bounds with the correct scaling.
We prove that all spaces of finite Assouad–Nagata dimension admit a good order for the travelling salesman problem, and provide sufficient conditions under which the converse is true. We formulate …
We prove that all spaces of finite Assouad–Nagata dimension admit a good order for the travelling salesman problem, and provide sufficient conditions under which the converse is true. We formulate a conjectural characterization of spaces of finite AN-dimension, which would yield a gap statement for the efficiency of orders on metric spaces. Under the assumption of doubling, we prove a stronger gap phenomenon about all orders on a given metric space.
We study the adjacency matrices of random d-regular graphs with large but fixed degree d. In the bulk of the spectrum $${[-2\sqrt{d-1}+\varepsilon, 2\sqrt{d-1}-\varepsilon]}$$ down to the optimal spectral scale, we …
We study the adjacency matrices of random d-regular graphs with large but fixed degree d. In the bulk of the spectrum $${[-2\sqrt{d-1}+\varepsilon, 2\sqrt{d-1}-\varepsilon]}$$ down to the optimal spectral scale, we prove that the Green's functions can be approximated by those of certain infinite tree-like (few cycles) graphs that depend only on the local structure of the original graphs. This result implies that the Kesten–McKay law holds for the spectral density down to the smallest scale and the complete delocalization of bulk eigenvectors. Our method is based on estimating the Green's function of the adjacency matrices and a resampling of the boundary edges of large balls in the graphs.
Abstract We study various classes of random processes defined on the regular tree T d that are invariant under the automorphism group of T d . The most important ones …
Abstract We study various classes of random processes defined on the regular tree T d that are invariant under the automorphism group of T d . The most important ones are factor of i.i.d. processes (randomized local algorithms), branching Markov chains and a new class that we call typical processes. Using Glauber dynamics on processes we give a sufficient condition for a branching Markov chain to be factor of i.i.d.
Let F be a nonarchimedean local field with a finite residue field. To a two-dimensional finite complex XΓ arising as the quotient of the Bruhat–Tits building X associated to Sp4(F) …
Let F be a nonarchimedean local field with a finite residue field. To a two-dimensional finite complex XΓ arising as the quotient of the Bruhat–Tits building X associated to Sp4(F) by a discrete torsion-free co-compact subgroup Γ of PGSp4(F), associate the zeta function Z(XΓ,u) which counts geodesic tailless cycles contained in the 1-skeleton of XΓ. Using a representation-theoretic approach, we obtain two closed-form expressions for Z(XΓ,u) as a rational function in u. Equivalent statements for XΓ being a Ramanujan complex are given in terms of vertex, edge, and chamber adjacency operators, respectively. The zeta functions of such Ramanujan complexes are distinguished by satisfying the Riemann hypothesis.
We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is linear in the size of the universe. Direct product tests belong to …
We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is linear in the size of the universe. Direct product tests belong to a family of tests called agreement tests that are important components in PCP constructions and include, for example, low degree tests such as line vs. line and plane vs. plane. For a generic hypergraph, we introduce the notion of agreement expansion, which captures the usefulness of the hypergraph for an agreement test. We show that explicit bounded degree agreement expanders exist, based on Ramanujan complexes.
Here we overview some of the methods and results of extremal graph and hypergraph theory. A few geometric applications are also given.
Here we overview some of the methods and results of extremal graph and hypergraph theory. A few geometric applications are also given.
The authors investigate the relation between the second eigen-value and the linear expansion of regular graphs. The spectral method is the best currently known technique to prove lower bounds on …
The authors investigate the relation between the second eigen-value and the linear expansion of regular graphs. The spectral method is the best currently known technique to prove lower bounds on the expansion. He improves this technique by showing that the expansion coefficient of linear-sized subsets of a k-regular graph G is at least k/2(1- square root max(0,1-/sub lambda 1(G)2//sup 4k-4/))/sup -/ , where lambda /sub 1/(G) is the second largest eigenvalue of the graph. In particular, the linear expansion of Ramanujan graphs, which have the property that the second largest eigenvalue is at most 2 square root k-1, is at least (k/2)/sup -/. This improves upon the best previously known lower bound of 3(k-2)/8. For any integer k such that k-1 is prime, he explicitly constructs an infinite family of k-regular graphs G/sub n/ on n vertices whose linear expansion is k/2 and such that lambda /sub 1/(G/sub n/)<or= square root k-1+0(1). Since the graphs G/sub n/ have asymptotically optimal second eigenvalue, this essentially shows the (k/2) is the best bound one can obtain using the second eigenvalue method.<<ETX>>
We give an explicit bound on the spectral radius in terms of the densities of short cycles in finite $d$-regular graphs. It follows that the a finite $d$-regular Ramanujan graph …
We give an explicit bound on the spectral radius in terms of the densities of short cycles in finite $d$-regular graphs. It follows that the a finite $d$-regular Ramanujan graph $G$ contains a negligible number of cycles of size less than $c\log\log\vert G\vert$. We prove that infinite $d$-regular Ramanujan unimodular random graphs are trees. Through Benjamini–Schramm convergence this leads to the following rigidity result. If most eigenvalues of a $d$-regular finite graph $G$ fall in the Alon–Boppana region, then the eigenvalue distribution of $G$ is close to the spectral measure of the $d$-regular tree. In particular, $G$ contains few short cycles. In contrast, we show that $d$-regular unimodular random graphs with maximal growth are not necessarily trees.
A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph H as a minor has the so-called Erdős–Pósa property; namely, there exists …
A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph H as a minor has the so-called Erdős–Pósa property; namely, there exists a function f depending only on H such that, for every graph G and every positive integer k , the graph G has k vertex-disjoint subgraphs each containing H as a minor, or there exists a subset X of vertices of G with | X | ≤ f(k) such that G − X has no H -minor (see Robertson and Seymour, J. Combin. Theory Ser. B 41 (1986) 92–114). While the best function f currently known is exponential in k , a O ( k log k ) bound is known in the special case where H is a forest. This is a consequence of a theorem of Bienstock, Robertson, Seymour and Thomas on the pathwidth of graphs with an excluded forest-minor. In this paper we show that the function f can be taken to be linear when H is a forest. This is best possible in the sense that no linear bound is possible if H has a cycle.
Abstract By means of a quaternion algebra over $\mathbb{F}$ q ( t ), we construct an infinite series of torsion free, simply transitive, irreducible lattices in PGL 2 ( $\mathbb{F}$ …
Abstract By means of a quaternion algebra over $\mathbb{F}$ q ( t ), we construct an infinite series of torsion free, simply transitive, irreducible lattices in PGL 2 ( $\mathbb{F}$ q (( t ))) × PGL 2 ( $\mathbb{F}$ q (( t ))). The lattices depend on an odd prime power q = p r and a parameter τ ∈ $\mathbb{F}$ q × , τ ≠ 1, and are the fundamental group of a square complex with just one vertex and universal covering T q +1 × T q +1 , a product of trees with constant valency q + 1. Our lattices give rise via non-archimedian uniformization to smooth projective surfaces of general type over $\mathbb{F}$ q (( t )) with ample canonical class, Chern numbers c 1 2 = 2 c 2 , trivial Albanese variety and non-reduced Picard scheme. For q = 3, the Zariski–Euler characteristic attains its minimal value χ = 1: the surface is a non-classical fake quadric.
David Cushinga, Riikka Kangaslampib* , Valtteri Lipiäinenc , Shiping Liud & George W. Staggea Department of Mathematical Sciences, Durham University, Durham, UKb Computing Sciences, Tampere University, Tampere, Finlandc Department of …
David Cushinga, Riikka Kangaslampib* , Valtteri Lipiäinenc , Shiping Liud & George W. Staggea Department of Mathematical Sciences, Durham University, Durham, UKb Computing Sciences, Tampere University, Tampere, Finlandc Department of Mathematics and Systems Analysis, Aalto University, Espoo, Finlandd School of Mathematical Sciences, University of Science and Technology of China, Hefei, Chinae School of Mathematics, Statistics and Physics, Newcastle University, Newcastle upon Tyne, UK
Abstract Random sampling is a technique for dealing with possible states or solutions having an exponentially large space. The best method of random sampling generally involves a random walk or …
Abstract Random sampling is a technique for dealing with possible states or solutions having an exponentially large space. The best method of random sampling generally involves a random walk or a Markov chain. A Markov chain requires a number of steps to approach equilibrium, and thus provide a good random sample of the state space. This number of steps is called mixing time, which can be calculated by thinking about how quickly its choices overwhelm the system’s memory of its initial state, the extent to which one part of a system influences another, and how smoothly probability flows from one part of the state space to another. This chapter explores random walks and rapid mixing, first by considering a classic example from physics: a block of iron. It then discusses transition matrices, ergodicity, coupling, spectral gap, and expanders, as well as the role of conductance and the spectral gap in rapid mixing. It concludes by showing that temporal mixing is closely associated with spatial mixing.
Abstract We prove upper bounds on the $L^p$ norms of eigenfunctions of the discrete Laplacian on regular graphs. We then apply these ideas to study the $L^p$ norms of joint …
Abstract We prove upper bounds on the $L^p$ norms of eigenfunctions of the discrete Laplacian on regular graphs. We then apply these ideas to study the $L^p$ norms of joint eigenfunctions of the Laplacian and an averaging operator over a finite collection of algebraic rotations of the two-sphere. Under mild conditions, such joint eigenfunctions are shown to satisfy for large $p$ the same bounds as those known for Laplace eigenfunctions on a surface of non-positive curvature.
A $k$-lift of an $n$-vertex base graph $G$ is a graph $H$ on $n\times k$ vertices, where each vertex $v$ of $G$ is replaced by $k$ vertices $v_1,\ldots,v_k$ and each …
A $k$-lift of an $n$-vertex base graph $G$ is a graph $H$ on $n\times k$ vertices, where each vertex $v$ of $G$ is replaced by $k$ vertices $v_1,\ldots,v_k$ and each edge $uv$ in $G$ is replaced by a matching representing a bijection $\pi_{uv}$ so that the edges of $H$ are of the form $(u_i,v_{\pi_{uv}(i)})$. Lifts have been investigated as a means to efficiently construct expanders. In this work, we study lifts obtained from groups and group actions. We derive the spectrum of such lifts via the representation theory principles of the underlying group. Our main results are 1. a uniform random lift by a cyclic group of order $k$ of any $n$-vertex $d$-regular base graph $G$, with the nontrivial eigenvalues of the adjacency matrix of $G$ bounded by $\lambda$ in magnitude, has the new nontrivial eigenvalues bounded by $\lambda+\mathcal{O}(\sqrt{d})$ in magnitude with probability $1-ke^{-\Omega(n/d^2)}$. The probability bounds as well as the dependency on $\lambda$ are almost optimal. As a special case, we obtain that there is a constant $c_1$ such that for every $k\leq 2^{c_1n/d^2}$, there exists a lift $H$ of every Ramanujan graph by a cyclic group of order $k$ such that $H$ is almost Ramanujan (nontrivial eigenvalues of the adjacency matrix at most $O(\sqrt{d})$ in magnitude). This result leads to a quasi-polynomial time deterministic algorithm to construct almost Ramanujan expanders; 2. there is a constant $c_2$ such that for every $k\geq 2^{c_2nd}$, there does not exist an abelian $k$-lift $H$ of any $n$-vertex $d$-regular base graph such that $H$ is almost Ramanujan. This can be viewed as an analogue of the well-known nonexpansion result for constant degree abelian Cayley graphs. Suppose $k_0$ is the order of the largest abelian group that produces expanding lifts. Our two results highlight lower and upper bounds on $k_0$ that are tight up to a factor of $d^3$ in the exponent, thus suggesting a threshold phenomenon.
Abstract We provide a deterministic algorithm that finds, in ɛ - O (1) n 2 time, an ɛ-regular Frieze–Kannan partition of a graph on n vertices. The algorithm outputs an …
Abstract We provide a deterministic algorithm that finds, in ɛ - O (1) n 2 time, an ɛ-regular Frieze–Kannan partition of a graph on n vertices. The algorithm outputs an approximation of a given graph as a weighted sum of ɛ - O (1) many complete bipartite graphs. As a corollary, we give a deterministic algorithm for estimating the number of copies of H in an n-vertex graph G up to an additive error of at most ɛn v(H) , in time ɛ - O H (1) n 2 .
Let p(Y1, ..., Yd, Z1, ..., Ze) be a self-adjoint noncommutative polynomial, with coefficients from C <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r×r</sup> , in the indeterminates Y1,..., Yd (considered to be self-adjoint), the …
Let p(Y1, ..., Yd, Z1, ..., Ze) be a self-adjoint noncommutative polynomial, with coefficients from C <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r×r</sup> , in the indeterminates Y1,..., Yd (considered to be self-adjoint), the indeterminates Z1, ..., Ze, and their adjoints Z1*, ..., Ze*. Suppose Y1, ..., Yd are replaced by independent random n x n matching matrices, and Z1, ..., Ze are replaced by independent random n x 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 goes to infinity, 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 , with high probability the spectrum of a random G will be eps-close in Hausdorff distance to the spectrum of X (once the suitably defined "trivial" eigenvalues are excluded). We say that G is "eps-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 eps 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) + eps). 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.
Abstract We construct a finitely generated group which is an extension of two finitely generated groups coarsely embeddable into Hilbert space but which itself does not coarsely embed into Hilbert …
Abstract We construct a finitely generated group which is an extension of two finitely generated groups coarsely embeddable into Hilbert space but which itself does not coarsely embed into Hilbert space. Our construction also provides a new infinite monster group: the first example of a finitely generated group that does not coarsely embed into Hilbert space and yet does not contain a weakly embedded expander.
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to [Wigderson and Xiao 06]. Our proof …
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to [Wigderson and Xiao 06]. Our proof is based on a new multi-matrix extension of the Golden-Thompson inequality which improves upon the inequality in [Sutter, Berta and Tomamichel 17], as well as an adaptation of an argument for the scalar case due to [Healy 08]. Our new multi-matrix Golden-Thompson inequality could be of independent interest. Secondarily, we also provide a generic reduction showing that any concentration inequality for vector-valued martingales implies a concentration inequality for the corresponding expander walk, with a weakening of parameters proportional to the squared mixing time.
Abstract A central problem in extremal graph theory is to estimate, for a given graph H, the number of H-free graphs on a given set of n vertices. In the …
Abstract A central problem in extremal graph theory is to estimate, for a given graph H, the number of H-free graphs on a given set of n vertices. In the case when H is not bipartite, Erd̋s, Frankl, and Rödl proved that there are 2(1+o(1))ex(n, H) such graphs. In the bipartite case, however, bounds of the form 2O(ex(n, H)) have been proven only for relatively few special graphs H. As a 1st attempt at addressing this problem in full generality, we show that such a bound follows merely from a rather natural assumption on the growth rate of n ↦ ex(n, H); an analogous statement remains true when H is a uniform hypergraph. Subsequently, we derive several new results, along with most previously known estimates, as simple corollaries of our theorem. At the heart of our proof lies a general supersaturation statement that extends the seminal work of Erd̋s and Simonovits. The bounds on the number of H-free hypergraphs are derived from it using the method of hypergraph containers.
Tartakowsky (1929) proved that a positive definite quadratic form, with integral coefficients, in 5 or more variables represents all but at most finitely many of the positive integers not excluded …
Tartakowsky (1929) proved that a positive definite quadratic form, with integral coefficients, in 5 or more variables represents all but at most finitely many of the positive integers not excluded by congruence considerations. Tartakowsky’s argument does not lead to any estimate for a positive integer which, though not so excluded, is not represented by the quadratic form. Here estimates for such an integer are obtained, in terms of the coefficients of the quadratic form. To simplify the argument and improve the estimates, the problem is slightly generalized (by considering a Diophantine equation with linear terms). A combination of analytical and arithmetical methods is needed.