Expanders and Diffusers

DOI10.1137/0607032MaRDI QIDQ3753504zbMATH OpenOpenAlexFDO

Authors 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 graphconcentratordoubly-stochastic matricesExpander graphsnorm of a diffusion operator on an infinite discrete grouprandom walksorting networkssuperconcentrators

Mathematics Subject Classification ID

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

Recommendations

• Better expanders and superconcentrators
• scientific article; zbMATH DE number 3864514
• Expander graphs and their applications
• Expanders that beat the eigenvalue bound: Explicit construction and applications
• Construction of expanders and superconcentrators using Kolmogorov complexity

Cites work

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

Cited in

(7)

• Relative expanders or weakly relatively Ramanujan graphs.
• The spectral geometry of \(k\)-regular groups
• The Ramanujan property for regular cubical complexes
• Better expanders and superconcentrators
• Diameters and Eigenvalues
• Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments
• On the heat kernel of a Cayley graph of \(\mathrm{PSL}_2 \mathbb{Z}\)

This page was built for publication: Expanders and Diffusers

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