Expander graphs in pure and applied mathematics

DOI10.1090/S0273-0979-2011-01359-3zbMath1232.05194arXiv1105.2389OpenAlexW2005644627WikidataQ105978537 ScholiaQ105978537MaRDI QIDQ3109810

Alexander Lubotzky

Publication date: 26 January 2012

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

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)

Related Items

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

Cites Work

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