Lifts, discrepancy and nearly optimal spectral gap
From MaRDI portal
Publication:879159
DOI10.1007/s00493-006-0029-7zbMath1121.05054arXivmath/0312022OpenAlexW2130270608WikidataQ105583356 ScholiaQ105583356MaRDI QIDQ879159
Publication date: 8 May 2007
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0312022
Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Signed and weighted graphs (05C22)
Related Items (68)
Expansion in matrix-weighted graphs ⋮ Shift lifts preserving Ramanujan property ⋮ Inverse expander mixing for hypergraphs ⋮ Sharp spectral bounds of several graph parameters using eigenvector norms ⋮ Twin-width II: small classes ⋮ Sharp nonasymptotic bounds on the norm of random matrices with independent entries ⋮ Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes ⋮ Isoperimetric inequalities in simplicial complexes ⋮ Explicit expanding expanders ⋮ Ramanujan coverings of graphs ⋮ Strong approximation in random towers of graphs. ⋮ Twin-width can be exponential in treewidth ⋮ Impediments to diffusion in quantum graphs: Geometry-based upper bounds on the spectral gap ⋮ Induced subgraphs of product graphs and a generalization of Huang's theorem ⋮ SVD, discrepancy, and regular structure of contingency tables ⋮ On regular hypergraphs of high girth ⋮ Complete signed graphs with largest maximum or smallest minimum eigenvalue ⋮ Equitable partition for some Ramanujan graphs ⋮ The spectral property of hypergraph coverings ⋮ Expander spanning subgraphs with large girth ⋮ Spreading and Structural Balance on Signed Networks ⋮ Expander graphs and their applications ⋮ Interactions of computational complexity theory and mathematics ⋮ Morse theory for discrete magnetic operators and nodal count distribution for graphs ⋮ Mixing in High-Dimensional Expanders ⋮ Cayley graph expanders and groups of finite width. ⋮ Cryptographic hash functions from sequences of lifted Paley graphs ⋮ Signatures, Lifts, and Eigenvalues of Graphs ⋮ Expander graphs and gaps between primes ⋮ Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian ⋮ Extremal results in sparse pseudorandom graphs ⋮ Graph covers with two new eigenvalues ⋮ An Elementary Construction of Constant-Degree Expanders ⋮ Discrete norms of a matrix and the converse to the expander mixing lemma ⋮ Expansion of random graphs: new proofs, new results ⋮ A Spectral Approach to Analysing Belief Propagation for 3-Colouring ⋮ Quasirandom Cayley graphs ⋮ Eigenvalues of 2-edge-coverings ⋮ Lifts, derandomization, and diameters of Schreier graphs of Mealy automata ⋮ Frustration and isoperimetric inequalities for signed graphs ⋮ Discrepancy minimizing spectral clustering ⋮ Deterministic Tensor Completion with Hypergraph Expanders ⋮ Combinatorial algorithms for distributed graph coloring ⋮ An isoperimetric constant for signed graphs ⋮ Spectra of lifted Ramanujan graphs ⋮ Computational topology and the Unique Games Conjecture ⋮ Word maps and spectra of random graph lifts ⋮ Minimal selectors and fault tolerant networks ⋮ Cheeger constants, structural balance, and spectral clustering analysis for signed graphs ⋮ Smooth and strong PCPs ⋮ Open problems in the spectral theory of signed graphs ⋮ Signed graphs with maximal index ⋮ \(L^p\) norms and support of eigenfunctions on graphs ⋮ Discrepancy and eigenvalues of Cayley graphs ⋮ On the Expansion of Group-Based Lifts ⋮ The chromatic number of random lifts of ⋮ The Tracy-Widom law for some sparse random matrices ⋮ Trace of Products in Finite Fields from a Combinatorial Point of View ⋮ Covers, orientations and factors ⋮ Explicit Near-Ramanujan Graphs of Every Degree ⋮ Ramanujan graphs arising as weighted Galois covering graphs ⋮ On the Expansion of Group-Based Lifts ⋮ Some regular signed graphs with only two distinct eigenvalues ⋮ Unnamed Item ⋮ Median eigenvalues of bipartite graphs ⋮ Interlacing families. I: Bipartite Ramanujan graphs of all degrees ⋮ Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem ⋮ Relating multiway discrepancy and singular values of nonnegative rectangular matrices
This page was built for publication: Lifts, discrepancy and nearly optimal spectral gap
