2015/04/28 by Ronen Eldan, Eldan, Ronen, Miklós Z. Rácz +3
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Probability (math.PR) #Random Matrices and Applications #Spectral Theory (math.SP) #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1504.07669
openalex publication_date 2015/04/28 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
We study how the spectral gap of the normalized Laplacian of a random graph\nchanges when an edge is added to or removed from the graph. There are known\nexamples of graphs where, perhaps counterintuitively, adding an edge can\ndecrease the spectral gap, a phenomenon that is analogous to Braess's paradox\nin traffic networks. We show that this is often the case in random graphs in a\nstrong sense. More precisely, we show that for typical instances of\nErd Hos-R 'enyi random graphs G(n,p) with constant edge density p \∈\n(0,1), the addition of a random edge will decrease the spectral gap with\npositive probability, strictly bounded away from zero. To do this, we prove a\nnew delocalization result for eigenvectors of the Laplacian of G(n,p), which\nmight be of independent interest.\n