Expanders and Diffusers

DOI10.1137/0607032zbMath0612.68061OpenAlexW2054624527MaRDI QIDQ3753504

Marshall W. Buck

Publication date: 1986

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0607032

zbMATH Keywords

bipartite graphrandom walksorting networksdoubly-stochastic matricessuperconcentratorsExpander graphsconcentratornorm of a diffusion operator on an infinite discrete group

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Sums of independent random variables; random walks (60G50) Linear algebraic groups over finite fields (20G40) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15) Directed graphs (digraphs), tournaments (05C20) Stochastic matrices (15B51)

Related Items

Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments, Relative expanders or weakly relatively Ramanujan graphs., The spectral geometry of \(k\)-regular groups, The Ramanujan property for regular cubical complexes, Diameters and Eigenvalues

Cites Work

• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Sorting in \(c \log n\) parallel steps
• Eigenvalues and expanders
• Asymptotically optimal switching circuits
• Explicit constructions of linear-sized superconcentrators
• On the complexity of an optimal non-blocking commutation scheme without reorganization
• Convolutions, means, and spectra
• On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
• Explicit Concentrators from Generalized N-Gons
• Full Banach Mean Values on Countable groups.
• Symmetric Random Walks on Groups
• Limitations on Explicit Constructions of Expanding Graphs
• Better expanders and superconcentrators
• Superconcentrators