Expander graphs in pure and applied mathematics

By Alexander Lubotzky. 2011

241 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/70dfc54d6599aa9db6f3aec7dd086b4b38c37629

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Nonlinear spectral calculus and super-expanders (2012, background): “Note that if Y contains at least two points then (5) implies that {Xn}n=1 are necessarily also expanders in the classical sense (see [21, 36] for more on classical expanders).”
Growth in finite simple groups of Lie type of bounded rank (2010, background): “For an account of far reaching developments in this area (many of which rely on Theorem 2) see [42].”
From Apollonius To Zaremba: Local-Global Phenomena in Thin Orbits (2012, background): “ to N{ in the major arcs M.) To explain how this happens, we brie y discuss the notion of an expander. Rather than going into the general theory (for which we refer the reader to the beautiful survey [Lub12]; see also [Sar04]), we content ourselves with but one illustrative example of expansion. Fig”
Ramanujan complexes and high dimensional expanders (2012, background): “[Lub94, HLW06], and the references within) and in recent years even found numerous applications in pure mathematics ([Lub12]).”
Size biased couplings and the spectral gap for random regular graphs (2015, background): “Expander graphs were seen to be extraordinarily useful for a range of applications in computer science and beyond (see [37, 43] for good surveys).”
Tensor Products of C*-Algebras and Operator Spaces (2020, background): “See Lubotzky’s survey [174] for a more recent update.”
Resilient Asymptotic Consensus in Robust Networks (2013, result): “Note that the notions of robustness and fraction robustness are similar to the concept of vertex expanders6 [49], [50].”
Expansion in perfect groups (2011, result): “We are also in debt to Alex Lubotzky for his interest and permission to include Question 4.”
Growth in groups: ideas and perspectives (2013, unknown): “oups such as SL2(Z/pZ) is due to Sarnak-Xue [SX91]. We will go over this in detail in §5.5. Theorem1.3 hasfoundmanifold applications (see, e.g., [BGS10](the aﬃne sieve)); we refer again to [Kowb] and [Lub12]. Traditionally, such results as we had on expansion in SL2(Z/pZ) were deduced from results o”
Approximate Gradient Coding via Sparse Random Graphs (2017, unknown): “By taking a random s-regular graph, however, we can obtain can expander graph with high probability [15].”