Skip to main content

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:
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.
Publication Date: 1-Jul-2017
Citation: Eldan, 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.20696
DOI: doi:10.1002/rsa.20696
ISSN: 1042-9832
EISSN: 1098-2418
Pages: 584 - 611
Type of Material: Journal Article
Journal/Proceeding Title: Random Structures and Algorithms
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.