Expander graphs in pure and applied mathematics

DOI10.1090/S0273-0979-2011-01359-3zbMATH Open1232.05194arXiv1105.2389OpenAlexW2005644627WikidataQ105978537 ScholiaQ105978537MaRDI QIDQ3109810FDOQ3109810

Alexander Lubotzky

Publication date: 26 January 2012

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Abstract: Expander graphs are highly connected sparse finite graphs. They play an important role in computer science as basic building blocks for network constructions, error correcting codes, algorithms and more. In recent years they have started to play an increasing role also in pure mathematics: number theory, group theory, geometry and more. This expository article describes their constructions and various applications in pure and applied mathematics.

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

zbMATH Keywords

expander graphssparse finite graphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Cites Work

• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• The product replacement algorithm and Kazhdan's property (T)
• Random walks on the mapping class group
• Variants of Kazhdan's property for subgroups of semisimple groups
• A sum-product estimate in finite fields, and applications
• Expander codes
• Expander graphs and their applications
• Functoriality for the exterior square of 𝐺𝐿₄ and the symmetric fourth of 𝐺𝐿₂
• Geometry and spectra of compact Riemann surfaces
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• On group-theoretic models of randomness and genericity.
• Ramanujan graphs
• Explicit constructions of graphs without short cycles and low density codes
• Invariable generation and the Chebotarev invariant of a finite group.
• On subgroups of \(GL_ n(F_ p)\)
• Explicit construction of linear sized tolerant networks
• Ramanujan duals. II
• Counterexamples to the Baum-Connes conjecture
• The primes contain arbitrarily long arithmetic progressions
• Free subgroups in linear groups
• Le problème des groupes de congruence pour \(SL_2\)
• Generic complexity of undecidable problems
• On the full C*-algebras of arithmetic groups and the congruence subgroup problem
• Spectra of elements in the group ring of SU(2)
• Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).
• On the spectral gap for finitely-generated subgroups of \(\text{SU}(2)\)
• Quasirandom Groups
• Product decompositions of quasirandom groups and a Jordan type theorem.
• Property (T) and Kazhdan constants for discrete groups
• An inverse theorem for the Gowers \(U^{s+1}[N]\)-norm
• Linear equations in primes
• Singularities, expanders and topology of maps. I: Homology versus volume in the spaces of cycles
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Overlap properties of geometric expanders
• Congruence Properties of Zariski-Dense Subgroups I
• A proof of Alon’s second eigenvalue conjecture and related problems
• Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).
• Ramanujan complexes of type \(\widetilde A_d\)
• Expansion in finite simple groups of Lie type.
• Strong uniform expansion in \(\text{SL}(2,p)\).
• Démonstration de la conjecture \(\tau\). (Proof of the \(\tau\)-conjecture.)
• On the spectral gap for infinite index ``congruence subgroups of SL\(_2(\mathbb{Z})\)
• Expanders, rank and graphs of groups
• Subgroup growth.
• The probability of generating a finite simple group
• Free quotients and the first Betti number of some hyperbolic manifolds
• The probability of generating a finite classical group
• Almost prime Pythagorean triples in thin orbits
• Apollonian circle packings and closed horospheres on hyperbolic 3-manifolds
• Random Heegaard splittings
• Generalization of Selberg's \(\frac {3}{16} \) theorem and affine sieve
• Generating random elements of a finite group
• The probability of generating the symmetric group
• On representations of integers in thin subgroups of \(\text{SL}_2(\mathbb Z)\)
• Finite covers of random 3-manifolds
• Expansion in perfect groups.
• Hecke operators and distributing points on S<sup>2</sup>. II
• Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski
• Growth and generation in \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\).
• Growth in finite simple groups of Lie type
• A recursive approach to low complexity codes
• Symmetric LDPC Codes and Local Testing
• Finite simple groups as expanders
• Edge transitive ramanujan graphs and symmetric LDPC good codes
• Suzuki groups as expanders.
• Approximate subgroups of linear groups.
• Affine linear sieve, expanders, and sum-product
• Small-diameter Cayley graphs for finite simple groups
• Generic-case complexity, decision problems in group theory, and random walks.
• Cost of equivalence relations and groups
• On the cost of generating an equivalence relation
• A characterisation of large finitely presented groups.
• The rank gradient from a combinatorial viewpoint.
• Rank gradient, cost of groups and the rank versus Heegaard genus problem
• Expanders and dimensional expansion
• Apollonian circle packings: Number theory
• Dimension expanders
• Universal lattices and property \(\tau\)
• Integral Apollonian Packings
• A proof of the positive density conjecture for integer Apollonian circle packings
• A product decomposition for the classical quasisimple groups
• Some Experiments with Integral Apollonian Circle Packings
• Bounded generation and Kazhdan's property (T)
• Towards dimension expanders over finite fields
• Linear representations of the automorphism group of a free group.
• Property \((T)\) for noncommutative universal lattices
• On the girth of random Cayley graphs
• Expander graphs, gonality, and variation of Galois representations
• On conjugacy growth of linear groups
• Linear approximate groups.
• Strong approximation for Zariski-dense subgroups of semi-simple algebraic groups
• Golod-Shafarevich groups with property \((T)\) and Kac-Moody groups.
• Walks on generating sets of groups
• Large groups, property (τ) and the homology growth of subgroups
• Expansion and random walks in \(\text{SL}_d(\mathbb{Z}/p^n\mathbb{Z})\). II.
• Expansion and random walks in \(\text{SL}_d(\mathbb{Z}/p^n\mathbb{Z})\). I.
• Expanding graphs and invariant means
• Strong approximation for Zariski dense subgroups over arbitrary global fields
• Strongly dense free subgroups of semisimple algebraic groups.
• Growth in \(\mathrm{SL}_3(\mathbb Z/p\mathbb Z)\).
• Selberg's eigenvalue conjecture.
• Growth of Small Generating Sets in SLn(Z/pZ)
• Prym representations of mapping class groups
• Universal lattices and unbounded rank expanders.
• Heegaard genus and property τ for hyperbolic 3-manifolds
• Walks on groups, counting reducible matrices, polynomials, and surface and free group automorphisms
• Zariski Density and Genericity
• Sieve methods in group theory. II: The mapping class group
• On Genericity of Pseudo-Anosovs in the Torelli Group
• Sieve methods in group theory I: Powers in linear groups
• Average-case complexity and decision problems in group theory.
• Sur certaines hypothèses concernant les nombres premiers
• Growth in SL2 over finite fields
• Powers in Finitely Generated Groups
• The affine sieve
• Linnik's ergodic method and the distribution of integer points on spheres
• Finite simple groups of Lie type as expanders.
• Expanders in group algebras
• Symmetric groups and expander graphs.
• Sieving and expanders
• Prime and almost prime integral points on principal homogeneous spaces
• Heegaard splittings, the virtually Haken conjecture and property \((\tau)\)
• Eigenvalues of the Laplacian, the first Betti number and the congruence subgroup problem
• Covering Spaces of Arithmetic 3-Orbifolds
• Invariant measures and stiffness for non-Abelian groups of toral automorphisms
• On amenability of group algebras. I.
• The amenability of affine algebras
• Splitting fields of characteristic polynomials of random elements in arithmetic groups
• The Galois group of random elements of linear groups
• On Fibonacci numbers with few prime divisors
• An application of Ramanujan graphs to \(C^*\)-algebra tensor products
• LERF and the Lubotzky-Sarnak conjecture
• Amplification arguments for large sieve inequalities
• Addendum to ``Random walk in random groups by M. Gromov.
• A spectral proof of Rademacher's conjecture for congruence subgroups of the modular group.
• Statistical properties of subgroups of free groups
• Generalizations of the Kolmogorov-Barzdin embedding estimates
• 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?)
• 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?)
• 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?)
• 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?)
• 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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (93)

• Expansion in matrix-weighted graphs
• Some Properties of a Cayley Graph of a Commutative Ring
• Strong approximation in random towers of graphs.
• Expansion of building-like complexes
• Thin subgroups isomorphic to Gromov-Piatetski-Shapiro lattices
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Spectral expansion of random sum complexes
• From Ramanujan graphs to Ramanujan complexes
• On constructing expander families of G-graphs
• Generalized wreath products of graphs and groups
• Ramanujan complexes and high dimensional expanders
• Spectral gap in the group of affine transformations over prime fields
• Random Latin squares and 2-dimensional expanders
• Discrete fundamental groups of warped cones and expanders
• Brackets, superalgebras and spectral gap
• Spectra of the neighbourhood corona of two graphs
• The second eigenvalue of some normal Cayley graphs of highly transitive groups
• Braess's paradox in expanders
• On Compiling Structured CNFs to OBDDs
• Quantum expanders and growth of group representations
• Super-expanders and warped cones
• Quantitative aspects of acyclicity
• Expanding graphs and invariant means
• Growth in finite simple groups of Lie type
• A Novel Compressed Sensing Scheme for Photoacoustic Tomography
• Layouts of Expander Graphs
• Eigenvalues of Cayley graphs
• A product theorem in free groups.
• From Apollonius to Zaremba: Local-global phenomena in thin orbits
• Sieve methods in group theory I: Powers in linear groups
• Permutational powers of a graph
• Sieve methods in group theory. II: The mapping class group
• Maximizing algebraic connectivity for certain families of graphs
• Gonality of expander graphs
• Explicit Construction of Ramanujan Bigraphs
• Strong Isoperimetric Inequality for Tessellating Quantum Graphs
• Bounded degree cosystolic expanders of every dimension
• Levels of distribution and the affine sieve
• \(\mathrm{SL}_2\) homomorphic hash functions: worst case to average case reduction and short collision search
• Probabilistic and Asymptotic Aspects of Finite Simple Groups
• Fast scramblers and ultrametric black hole horizons
• Orbit equivalence and Borel reducibility rigidity for profinite actions with spectral gap
• Growth in groups: ideas and perspectives
• Finding structure in sequences of real numbers via graph theory: a problem list
• On compiling structured CNFs to OBDDs
• Square \((1,-1)\)-matrices with large determinants and near-Hadamard matrices
• Nonlinear spectral calculus and super-expanders
• Quantitative ergodic theorems and their number-theoretic applications
• Efficient and Reliable Overlay Networks for Decentralized Federated Learning
• On Cayley representations of central Cayley graphs over almost simple groups
• Fast scramblers, horizons and expander graphs
• Communicability angle and the spatial efficiency of networks
• Measure expanding actions, expanders and warped cones
• High Dimensional Random Walks and Colorful Expansion
• The Graph Curvature Calculator and the Curvatures of Cubic Graphs
• Isoperimetric inequalities in simplicial complexes
• RAMANUJAN CAYLEY GRAPHS OF FROBENIUS GROUPS
• On Constructing Expanders for Any Number of Vertices
• Hypergraph expanders from Cayley graphs
• The first Cheeger constant of a simplex
• Mixing time and eigenvalues of the abelian sandpile Markov chain
• Expansion in perfect groups.
• Spectral estimates for infinite quantum graphs
• Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
• Size biased couplings and the spectral gap for random regular graphs
• Mixing for progressions in nonabelian groups.
• Aldous’s spectral gap conjecture for normal sets
• Cryptographic Hash Functions and Expander Graphs: The End of the Story?
• Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition
• Spectrum and combinatorics of two-dimensional Ramanujan complexes
• Title not available (Why is that?)
• Toward super‐approximation in positive characteristic
• \(\operatorname{SL}_2\) representations and relative property (T)
• Balanced Subdivisions of a Large Clique in Graphs with High Average Degree
• Navigating directed Cayley graphs of small diameter: A potent Solovay–Kitaev procedure
• Paradigms for Unconditional Pseudorandom Generators
• Non-expander Cayley Graphs of Simple Groups
• Title not available (Why is that?)
• On the spectrum of the closed unit graphs
• Graphs with high second eigenvalue multiplicity
• Local and global expansion in random geometric graphs
• Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
• Title not available (Why is that?)
• Selected topics in spectral graph theory. (Abstract of thesis)
• Hypergraph expanders of all uniformities from Cayley graphs
• Attainable bounds for algebraic connectivity and maximally connected regular graphs
• Ramanujan graphs and expander families constructed from \(p\)-ary bent functions
• Connection of \(p\)-ary \(t\)-weight linear codes to Ramanujan Cayley graphs with \(t+1\) eigenvalues
• Book review of: N. M. Katz, Convolution and equidistribution. Sato-Tate theorems for finite fields Mellin transforms
• The second variation of the Hodge norm and higher Prym representations
• Operator norm localization property for equi-approximable families of projections
• Connectedness and isomorphism properties of the zig-zag product of graphs
• A Cheeger-Buser-type inequality on CW complexes

This page was built for publication: Expander graphs in pure and applied mathematics

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