Relative expanders or weakly relatively Ramanujan graphs

By Joel Friedman. 2003

111 citations recorded by the source corpus.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/26a24ca0d8e2520494648d261604cead164b2654

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Geometry and Topology

In Statistics and Probability

Citations in the corpus

THE NON-BACKTRACKING SPECTRUM OF THE UNIVERSAL COVER OF A GRAPH (2007, background): “As we shall see (and see [14]), for ﬁnite d -regular graphs each μ ∈ σ ( A ) corresponds to two λ ∈ σ ( B ) given by the solutions of λ In [13], Alon’s conjecture is relativized, meaning that for any graph, H (the “base graph”), we consider a random lift, π : G → H , of degree n .”
A new proof of Friedman's second eigenvalue theorem and its extension to random lifts (2015, background): “This class of models sheds a new light on Ramanujan-type properties, and, since the work of Amit and Linial [3, 4] and Friedman [10], it has attracted a substantial attention [15, 1, 16, 24, 12].”
Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, methodology): “One of them is the “trace method” [26, 28, 38, 35, 36] which consists of analyzing traces of high powers of the matrices under consideration.”
Expansion of random graphs: new proofs, new results (2012, methodology): “The adjacency-operator version is due to Friedman [20].”
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees (2013, methodology): “Friedman [14] has proved that almost every d -regular graph almost meets the Ramanujan bound: he shows that for every ε > 0, the absolute value of all the nontrivial eigenvalues of almost every suﬃciently large d -regular graph are at most 2 √ d − 1 + ε .”
Twice-ramanujan sparsifiers (2008, background): “It is well understood how to quickly approximate complete graphs: random d-regular graphs are almost as good as Ramanujan graphs [13].”
Eigenvalues of random lifts and polynomials of random permutation matrices (2018, background): “Since the work of Amit and Linial [3, 4] and Friedman [14], this class of random graphs has attracted a substantial attention [27, 1,”