We will discuss some recent developments in several directions of spectral graph theory, including spectral bounds for graphs with general degree distribution and some variations of Ramanujan graph, satisfying vertex and edge expansion properties.
Tag - Ramanujan graph
We will discuss the sharp transition in the time it takes simple random walk on regular Ramanujan graphs to approach the uniform distribution (known as the cutoff phenomenon), and geometric consequences (such as typical distances between vertices) that this implies for such graphs. We will then discuss how these ideas can be extended to regular Ramanujan digraphs, and consequently, to any d-dimensional Ramanujan complexes for d > 1 associated with a simple group, with analogous geometric implications for these objects.
Some thirty years ago, Lubotzky, Phillips and Sarnak used deep number-theoretic insights to construct the first Ramanujan graphs, as well as optimal pseudo-random generators for the rotation group SO(3). In the last decade their work has seen several developments: On the discrete side, in the study of Ramanujan complexes, which are finite simplicial complexes with the spectral behaviour of infinite buildings. On the continuous side, in the study of pseudo-random generators for U(n), motivated by the problem of constructing optimal gates for fault-tolerant quantum computation. Results on both the continuous and discrete sides draw on the study of Ramanujan digraphs, which seem to be of independent interest. Based on joint works with Eyal Lubetzky, Alex Lubotzky and Peter Sarnak.
This talk will review two different results regarding the existence of Ramanujan graphs. While both methods employ the method of interlacing polynomials, they are thematically quite different. The goal will be to highlight some of the commonalities and differences.
The breakthrough work of Marcus, Spielman, and Srivastava showed that every bipartite Ramanujan graph has a bipartite Ramanujan double cover. Chris Hall, Doron Puder, and I generalized this to covers of arbitrary degree. I will explain the proof, with emphasis on how group theory and representation theory are useful for this problem.
We explain what Ramanujan graphs are, and prove that there exist infinite families of bipartite Ramanujan graphs of every degree. Our proof follows a plan suggested by Bilu and Linial, and exploits a proof of a conjecture of theirs about lifts of graphs. Our proof of their conjecture applies the method of interlacing families of polynomials to Mixed Characteristic Polynomials. A bound on the roots of these polynomials will follow from a bound of Heilmann and Lieb on the roots of the matching polynomials of graphs. We also prove that there exist infinite families of irregular bipartite Ramanujan graphs.
Random graphs and expander graphs can be viewed as sparse approximations of complete graphs, with Ramanujan expanders providing the best possible approximations. We formalize this notion of approximation and ask how well an arbitrary graph can be approximated by a sparse graph. We prove that every graph can be approximated by a sparse graph almost as well as the complete graphs are approximated by the Ramanujan expanders: our approximations employ at most twice as many edges to achieve the same approximation factor. Our algorithms follow from the solution of a problem in linear algebra. Given an expression for a rank-n symmetric matrix A as a sum of rank-1 symmetric matrices, we show that A can be well approximated by a weighted sum of only O(n) of those rank-1 matrices.
You must be logged in to post a comment.