2024/04/23 by Sooyeong Kim, Neal Madras, Kim, Sooyeong +1 · 1 citation
Computer Science · Engineering · Mathematics · #05C81 #60J10 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Probability (math.PR) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2404.15167
openalex publication_date 2024/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph on n vertices, with complement G. The spectral gap of the transition probability matrix of a random walk on G is used to estimate how fast the random walk becomes stationary. We prove that the larger spectral gap of G and G is Ω(1/n). Moreover, if all degrees are Ω(n) and n-Ω(n), then the larger spectral gap of G and G is Θ(1). We also show that if the maximum degree is n-O(1) or if G is a join of two graphs, then the spectral gap of G is Ω(1/n). Finally, we provide a family of connected graphs with connected complements such that the larger spectral gap of G and G is O(1/n3/4).