Expanders and Diffusers

DOI10.1137/0607032zbMATH Open0612.68061OpenAlexW2054624527MaRDI QIDQ3753504FDOQ3753504

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

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

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)

Cites Work

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

Cited In (6)

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

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)