Lifts, discrepancy and nearly optimal spectral gap

DOI10.1007/S00493-006-0029-7zbMATH Open1121.05054arXivmath/0312022OpenAlexW2130270608WikidataQ105583356 ScholiaQ105583356MaRDI QIDQ879159FDOQ879159

Authors: Yonatan Bilu, Nathan Linial 

Publication date: 8 May 2007

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cited In (72)

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

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)