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
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
