Lifts, discrepancy and nearly optimal spectral gap

DOI10.1007/S00493-006-0029-7MaRDI QIDQ879159zbMATH OpenOpenAlexWikidataFDO

Authors Yonatan Bilu, Nathan Linial

Publication date 8 May 2007

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0312022

zbMATH Keywords

expander graphsoptimal spectral gap

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22)

Abstract: We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let $G$ be a graph on $n$ vertices. A 2-lift of $G$ is a graph $H$ on $2n$ vertices, with a covering map $pi:HoG$. It is not hard to see that all eigenvalues of $G$ are also eigenvalues of $H$. In addition, $H$ has $n$ ``new eigenvalues. We conjecture that every $d$-regular graph has a 2-lift such that all new eigenvalues are in the range $[-2sqrtd-1,2sqrtd-1]$ (If true, this is tight, e.g. by the Alon-Boppana bound). Here we show that every graph of maximal degree $d$ has a 2-lift such that all ``new eigenvalues are in the range $[-csqrtdlo{g}^{3}d,csqrtdlo{g}^{3}d]$ for some constant $c$. This leads to a polynomial time algorithm for constructing arbitrarily large $d$-regular graphs, with second eigenvalue $O(sqrtdlo{g}^{3}d)$. The proof uses the following lemma: Let $A$ be a real symmetric matrix such that the $l_1$ norm of each row in $A$ is at most $d$. Let $alpha=ma{x}_{x,yin{0,1}^n,supp(x)capsupp(y)=emptyset}frac|xAy|||x||||y||$. Then the spectral radius of $A$ is at most $calphalog(d/alpha)$, for some universal constant $c$. An interesting consequence of this lemma is a converse to the Expander Mixing Lemma.

Recommendations

• A spectral gap estimate and applications
• Spectral gaps, symmetries and log-concave perturbations
• scientific article; zbMATH DE number 5217628
• scientific article; zbMATH DE number 1961223
• On a minimax principle in spectral gaps
• On construction of upper and lower bounds for the HOMO-LUMO spectral gap
• Publication:3475327
• Spectral bounds and distance-regularity
• Spectral gaps for sets and measures
• scientific article; zbMATH DE number 21662

Cited in

(71)

• Cryptographic hash functions from sequences of lifted Paley graphs
• Trace of products in finite fields from a combinatorial point of view
• Open problems in the spectral theory of signed graphs
• Curvature and higher order Buser inequalities for the graph connection Laplacian
• Word maps and spectra of random graph lifts
• Discrete norms of a matrix and the converse to the expander mixing lemma
• Mixing in high-dimensional expanders
• Shift lifts preserving Ramanujan property
• Median eigenvalues of bipartite graphs
• Computational topology and the unique games conjecture
• On construction of upper and lower bounds for the HOMO-LUMO spectral gap
• Quasirandom Cayley graphs
• Expander graphs and gaps between primes
• Signatures, lifts, and eigenvalues of graphs
• Some regular signed graphs with only two distinct eigenvalues
• Isoperimetric inequalities in simplicial complexes
• Signed graphs with maximal index
• Inverse expander mixing for hypergraphs
• Discrepancy and eigenvalues of Cayley graphs
• Equitable partition for some Ramanujan graphs
• Sharp spectral bounds of several graph parameters using eigenvector norms
• Expansion in matrix-weighted graphs
• Covers, orientations and factors
• Explicit Near-Ramanujan Graphs of Every Degree
• Smooth and strong PCPs
• Strong approximation in random towers of graphs.
• Expansion of random graphs: new proofs, new results
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
• Combinatorial algorithms for distributed graph coloring
• Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
• Interlacing families. IV: Bipartite Ramanujan graphs of all sizes
• A spectral approach to analysing belief propagation for 3-colouring
• Extremal results in sparse pseudorandom graphs
• Ramanujan coverings of graphs
• Expander spanning subgraphs with large girth
• Graph covers with two new eigenvalues
• On the expansion of group-based lifts
• Cayley graph expanders and groups of finite width.
• Expander graphs and their applications
• On regular hypergraphs of high girth
• Minimal selectors and fault tolerant networks
• On the expansion of group-based lifts
• \(L^p\) norms and support of eigenfunctions on graphs
• Relating multiway discrepancy and singular values of nonnegative rectangular matrices
• Impediments to diffusion in quantum graphs: Geometry-based upper bounds on the spectral gap
• The chromatic number of random lifts of \(K_5\setminus e\)
• Spectra of lifted Ramanujan graphs
• Discrepancy minimizing spectral clustering
• An Elementary Construction of Constant-Degree Expanders
• Eigenvalues of 2-edge-coverings
• An isoperimetric constant for signed graphs
• SVD, discrepancy, and regular structure of contingency tables
• Frustration and isoperimetric inequalities for signed graphs
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• The Tracy-Widom law for some sparse random matrices
• Ramanujan graphs arising as weighted Galois covering graphs
• Spreading and Structural Balance on Signed Networks
• Complete signed graphs with largest maximum or smallest minimum eigenvalue
• The power of unentangled quantum proofs with non-negative amplitudes
• Morse theory for discrete magnetic operators and nodal count distribution for graphs
• A unified framework for the expander mixing lemma for irregular graphs and its applications
• Twin-width II: small classes
• Local and global expansion in random geometric graphs
• The spectral property of hypergraph coverings
• Deterministic tensor completion with hypergraph expanders
• Induced subgraphs of product graphs and a generalization of Huang's theorem
• Twin-width can be exponential in treewidth
• Parallel repetition via fortification: analytic view and the quantum case
• Interactions of computational complexity theory and mathematics

This page was built for publication: Lifts, discrepancy and nearly optimal spectral gap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q879159)