On the second eigenvalue of hypergraphs

DOI10.1007/BF01294459zbMath0843.05075OpenAlexW1979110822MaRDI QIDQ1842569

Avi Wigderson, Joel Friedman

Publication date: 4 May 1995

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01294459

zbMATH Keywords

hypergraphmultilinear formsfirst eigenvaluenormsuniform hypergraphssecond eigenvaluetrilinear formdirected edges

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Perfect packings in quasirandom hypergraphs. I., Tensors in computations, Inverse expander mixing for hypergraphs, Unnamed Item, Eigenvalues of non-regular linear quasirandom hypergraphs, Graph-theoretic design and analysis of key predistribution schemes, On the spectrum and linear programming bound for hypergraphs, A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting, Isoperimetric inequalities in simplicial complexes, On the Z-eigenvalues of the signless Laplacian tensor for an even uniform hypergraph, Simulating BPP using a general weak random source, Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs, Spectra of uniform hypergraphs, On the second eigenvalue of random bipartite biregular graphs, Expander graphs and their applications, On the Z-eigenvalues of the adjacency tensors for uniform hypergraphs, On the first and second eigenvalue of finite and infinite uniform hypergraphs, Size biased couplings and the spectral gap for random regular graphs, Hypergraphs and hypermatrices with symmetric spectrum, Deterministic Tensor Completion with Hypergraph Expanders, Analytic methods for uniform hypergraphs, Linear quasi-randomness of subsets of abelian groups and hypergraphs, Linear quasi-randomness of subsets of abelian groups and hypergraphs, Principal eigenvectors of general hypergraphs, Sparse random tensors: concentration, regularization and applications, Spectra of random regular hypergraphs, Random walks on simplicial complexes and harmonics, Adjacency spectra of random and complete hypergraphs, Diffusion operator and spectral analysis for directed hypergraph Laplacian, Spectra of cycle and path families of oriented hypergraphs, EIGENVALUES AND LINEAR QUASIRANDOM HYPERGRAPHS, Sparse SYK and traversable wormholes, Some graphs with small second eigenvalue

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Characteristic vectors of bordered matrices with infinite dimensions
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• On using deterministic functions to reduce randomness in probabilistic algorithms
• Eigenvalues and expanders
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• Some graphs with small second eigenvalue
• An Estimate for Character Sums
• Diameters and Eigenvalues