# Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors

## Author(s): Eldan, R; Rácz, Miklos Z; Schramm, T

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1328t
DC FieldValueLanguage
dc.contributor.authorEldan, R-
dc.contributor.authorRácz, Miklos Z-
dc.contributor.authorSchramm, T-
dc.date.accessioned2021-10-11T14:17:52Z-
dc.date.available2021-10-11T14:17:52Z-
dc.date.issued2017-07-01en_US
dc.identifier.citationEldan, R, Rácz, MZ, Schramm, T. (2017). Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors. Random Structures and Algorithms, 50 (4), 584 - 611. doi:10.1002/rsa.20696en_US
dc.identifier.issn1042-9832-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1328t-
dc.description.abstract© 2016 Wiley Periodicals, Inc. 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.en_US
dc.format.extent584 - 611en_US
dc.language.isoen_USen_US
dc.relation.ispartofRandom Structures and Algorithmsen_US
dc.rightsAuthor's manuscripten_US
dc.titleBraess's paradox for the spectral gap in random graphs and delocalization of eigenvectorsen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1002/rsa.20696-
dc.identifier.eissn1098-2418-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat
Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors.pdf325.63 kBAdobe PDF