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

random walkbipartite graphsorting networksdoubly-stochastic matricessuperconcentratorsExpander graphsconcentratornorm of a diffusion operator on an infinite discrete group

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3487716 (Why is no real title available?)
• scientific article; zbMATH DE number 3187168 (Why is no real title available?)
• 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.
• 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
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(6)

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

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)