Ramanujan complexes and high dimensional expanders

DOI10.1007/S11537-014-1265-ZzbMATH Open1302.05095arXiv1301.1028OpenAlexW2963265122MaRDI QIDQ466822FDOQ466822

Alexander Lubotzky

Publication date: 31 October 2014

Published in: Japanese Journal of Mathematics. 3rd Series (Search for Journal in Brave)

Abstract: Expander graphs in general, and Ramanujan graphs in particular, have been of great interest in the last three decades with many applications in computer science, combinatorics and even pure mathematics. In these notes we describe various efforts made in recent years to generalize these notions from graphs to higher dimensional simplicial complexes.

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

zbMATH Keywords

expanding graphshigh-dimensional expandersoverlapping propertyRamanujan complexesRamanujan graphs

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Connectivity (05C40) Density (toughness, etc.) (05C42) Hypergraphs (05C65) Analysis on (p)-adic Lie groups (22E35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Eigenvalues and expanders
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• The number of triangles covering the center of an \(n\)-set
• A generalization of Caratheodory's theorem
• Geometry and analysis on manifolds. Proceedings of the 21st inernational Taniguchi symposium held at Katata, Japan, Aug. 23-29 and the conference held at Kyoto, Aug. 31-Sep. 2, 1987
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• On discrete subgroups of the two by two projective linear group over \(p\)-adic fields
• Expansion of building-like complexes
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• High dimensional expanders and property testing
• Expander graphs in pure and applied mathematics
• Expander graphs and their applications
• Homological connectivity of random k -dimensional complexes
• A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem
• Random Latin squares and 2-dimensional expanders
• COBOUNDARY EXPANDERS
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• On Gromov's method of selecting heavily covered points
• Homological connectivity of random 2-complexes
• Ramanujan graphs
• Drinfeld shtukas and Langlands correspondence.
• Symmetric Random Walks on Groups
• Isoperimetric inequalities in simplicial complexes
• p-adic curvature and the cohomology of discrete subgroups of p-adic groups
• Explicit Concentrators from Generalized N-Gons
• A Cheeger-type inequality on simplicial complexes
• Mixing in High-Dimensional Expanders
• A family of \(\widetilde A_n\)-groups
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Zeta functions of complexes arising from \(\mathrm{PGL}(3)\)
• Overlap properties of geometric expanders
• Mixing Properties and the Chromatic Number of Ramanujan Complexes
• Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).
• The zeta functions of complexes from \(\mathrm{PGL}(3)\): a representation-theoretic approach
• Ramanujan complexes of type \(\widetilde A_d\)
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• On the second eigenvalue of a graph
• On multiplicative \(\lambda\)-approximations and some geometric applications
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Edge transitive ramanujan graphs and symmetric LDPC good codes
• Discrete subgroups acting transitively on vertices of a Bruhat-Tits building
• On Laplacians of random complexes
• A Tverberg-type result on multicolored simplices
• A Moore bound for simplicial complexes
• Proof of Peterson's conjecture for GL(2) over a global field of \(characteristic\quad p\).
• Ramanujan geometries of type \(\tilde A_{n}\)
• Natural bounded concentrators
• Ramanujan hypergraphs
• Spectrum and combinatorics of two-dimensional Ramanujan complexes
• Explicit construction of a Ramanujan \((n_1,n_2,\dots,n_{d-1})\)-regular hypergraph
• Finite quotients of Bruhat–Tits buildings as geometric expanders
• Simplicial complexes: Spectrum, homology and random walks
• THE IHARA–SELBERG ZETA FUNCTION FOR PGL₃ AND HECKE OPERATORS
• On non-uniform Ramanujan complexes
• On Finite Index Subgroups of Linear Groups
• Ramanujan Diagrams
• Higher Dimensional Cheeger Inequalities
• Ramanujan Type Buildings
• Minors in random and expanding hypergraphs
• The zeta function of a hypergraph
• Geometric zeta functions for higher rank \(p\)-adic groups

Cited In (28)

• Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders
• Ramanujan complexes and golden gates in \(PU(3)\)
• Expansion of building-like complexes
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Graphical designs and extremal combinatorics
• Random Steiner systems and bounded degree coboundary expanders of every dimension
• Spectral expansion of random sum complexes
• From Ramanujan graphs to Ramanujan complexes
• Simplicial complexes: Spectrum, homology and random walks
• Random Latin squares and 2-dimensional expanders
• Toric chordality
• Bounded degree cosystolic expanders of every dimension
• Expansion of random graphs: new proofs, new results
• Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).
• \(L^p\)-expander graphs
• The theta number of simplicial complexes
• Random walks on simplicial complexes and harmonics
• Cutoff on Ramanujan complexes and classical groups
• Discrete quantum walks on the symmetric group
• High dimensional Hoffman bound and applications in extremal combinatorics
• High Dimensional Random Walks and Colorful Expansion
• Good quantum LDPC codes with linear time decoders
• Spectrum of signless 1-Laplacian on simplicial complexes
• Hypergraph expanders from Cayley graphs
• The first Cheeger constant of a simplex
• Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
• Infinite series of quaternionic 1-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes
• Spectrum and combinatorics of two-dimensional Ramanujan complexes

This page was built for publication: Ramanujan complexes and high dimensional expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q466822)