On Near Optimal Spectral Expander Graphs of Fixed Size

2021/09/29 by Clark Alexander, Alexander, Clark
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Methodology (stat.ME)

paper · pdf · doi:10.48550/arxiv.2110.01407

openalex publication_date 2021/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a pair of heuristic algorithms. The first is to generate a random regular graph of fixed size. The second is the introduction of the Metropolis Coupled Simulated Annealer (MCSA) for optimizing spectral gaps in fixed size regular graphs.

Citations

• Bayesian Phylogenetic Inference via Markov Chain Monte Carlo Methods

Related

• Approximation Algorithms for Finding Maximum Induced Expanders
• Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
• Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
• Rounding Large Independent Sets on Expanders
• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time