Premium
Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
Author(s) -
Eldan Ronen,
Rácz Miklós Z.,
Schramm Tselil
Publication year - 2017
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20696
Subject(s) - random graph , spectral gap , mathematics , eigenvalues and eigenvectors , delocalized electron , combinatorics , bounded function , random regular graph , laplace operator , enhanced data rates for gsm evolution , graph , laplacian matrix , discrete mathematics , chordal graph , 1 planar graph , physics , computer science , quantum mechanics , mathematical analysis , telecommunications
We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, perhaps counter‐intuitively, adding an edge can decrease the spectral gap, a phenomenon that is analogous to Braess's paradox in traffic networks. We show that this is often the case in random graphs in a strong sense. More precisely, we show that for typical instances of Erdős‐Rényi random graphs G ( n, p ) with constant edge density p ∈ ( 0 , 1 ) , the addition of a random edge will decrease the spectral gap with positive probability, strictly bounded away from zero. To do this, we prove a new delocalization result for eigenvectors of the Laplacian of G ( n, p ), which might be of independent interest. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 584–611, 2017