Lifts, discrepancy and nearly optimal spectral gap
From MaRDI portal
Publication:879159
DOI10.1007/s00493-006-0029-7zbMath1121.05054arXivmath/0312022WikidataQ105583356 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
05C35: Extremal problems in graph theory
05C80: Random graphs (graph-theoretic aspects)
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C22: Signed and weighted graphs
Related Items
Unnamed Item, Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes, Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian, Quasirandom Cayley graphs, Ramanujan graphs arising as weighted Galois covering graphs, On the Expansion of Group-Based Lifts, Twin-width II: small classes, Signatures, Lifts, and Eigenvalues of Graphs, Deterministic Tensor Completion with Hypergraph Expanders, Computational topology and the Unique Games Conjecture, Open problems in the spectral theory of signed graphs, On the Expansion of Group-Based Lifts, Trace of Products in Finite Fields from a Combinatorial Point of View, Mixing in High-Dimensional Expanders, Explicit Near-Ramanujan Graphs of Every Degree, Some regular signed graphs with only two distinct eigenvalues, 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, Equitable partition for some Ramanujan graphs, Relating multiway discrepancy and singular values of nonnegative rectangular matrices, Inverse expander mixing for hypergraphs, Sharp spectral bounds of several graph parameters using eigenvector norms, Sharp nonasymptotic bounds on the norm of random matrices with independent entries, Strong approximation in random towers of graphs., SVD, discrepancy, and regular structure of contingency tables, On regular hypergraphs of high girth, Discrete norms of a matrix and the converse to the expander mixing lemma, Expansion of random graphs: new proofs, new results, Frustration and isoperimetric inequalities for signed graphs, An isoperimetric constant for signed graphs, Spectra of lifted Ramanujan graphs, Cayley graph expanders and groups of finite width., Lifts, derandomization, and diameters of Schreier graphs of Mealy automata, Covers, orientations and factors, Expansion in matrix-weighted graphs, The Tracy-Widom law for some sparse random matrices, Ramanujan coverings of graphs, Discrepancy minimizing spectral clustering, Smooth and strong PCPs, Signed graphs with maximal index, Graph covers with two new eigenvalues, Combinatorial algorithms for distributed graph coloring, Cheeger constants, structural balance, and spectral clustering analysis for signed graphs, \(L^p\) norms and support of eigenfunctions on graphs, 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, Shift lifts preserving Ramanujan property, Isoperimetric inequalities in simplicial complexes, Explicit expanding expanders, Extremal results in sparse pseudorandom graphs, Expander spanning subgraphs with large girth, Discrepancy and eigenvalues of Cayley graphs, The chromatic number of random lifts of, Cryptographic hash functions from sequences of lifted Paley graphs, Word maps and spectra of random graph lifts, Minimal selectors and fault tolerant networks, Expander graphs and their applications, Expander graphs and gaps between primes, An Elementary Construction of Constant-Degree Expanders, A Spectral Approach to Analysing Belief Propagation for 3-Colouring, Eigenvalues of 2-edge-coverings
