Beyond the expanders

DOI10.1155/2011/787596zbMATH Open1236.05122arXiv1101.5926OpenAlexW2166772092WikidataQ58655897 ScholiaQ58655897MaRDI QIDQ666522FDOQ666522

Authors: Marianna Bolla 

Publication date: 8 March 2012

Published in: International Journal of Combinatorics (Search for Journal in Brave)

Abstract: Expander graphs are widely used in communication problems and construction of error correcting codes. In such graphs, information gets through very quickly. Typically, it is not true for social or biological networks, though we may find a partition of the vertices such that the induced subgraphs on them and the bipartite subgraphs between any pair of them exhibit regular behavior of information flow within or between the subsets. Implications between spectral and regularity properties are discussed.

Full work available at URL: https://arxiv.org/abs/1101.5926

Recommendations

• Expander graphs in pure and applied mathematics
• Expander graphs and their applications
• scientific article; zbMATH DE number 7052900
• scientific article; zbMATH DE number 5010757
• On new expanders of unbounded degree for practical applications in informatics

zbMATH Keywords

random walkspectral walk

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10) Random walks on graphs (05C81) Network design and communication in computer systems (68M10)

Cites Work

• Title not available (Why is that?)
• Community structure in social and biological networks
• Eigenvalues and expanders
• Generalized quasirandom graphs
• Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
• Expander graphs and their applications
• Quasi‐random graphs with given degree sequences
• Noisy random graphs and their laplacians
• Szemerédi's lemma for the analyst
• Spectra and optimal partitions of weighted graphs
• The spectral gap of random graphs with given expected degrees
• Optimization problems for weighted graphs and related correlation estimates

Cited In (16)

• Extended rate, more GFUN
• Dimension expanders
• Spectra and structure of weighted graphs
• A continuum of expanders
• DEX: self-healing expanders
• Beyond the KdV: Post-explosion development
• Expanders -- how to find them, and what to find in them
• Bipartite multigraphs with expander-like properties
• Modularity spectra, eigen-subspaces, and structure of weighted graphs
• Extended Vuza canons
• Expander graphs in pure and applied mathematics
• 60/102 null boundary cellular automata based expander graphs
• Better expanders and superconcentrators
• On new expanders of unbounded degree for practical applications in informatics
• Expanders and dimensional expansion
• Löwner Expansions

This page was built for publication: Beyond the expanders

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