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

Ronen Eldan, Miklós Z. Rácz, Tselil Schramm

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)584-611
Number of pages28
JournalRandom Structures and Algorithms
Volume50
Issue number4
DOIs
StatePublished - Jul 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • Braess's paradox
  • graph Laplacian
  • random graphs
  • spectral gap

Fingerprint Dive into the research topics of 'Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors'. Together they form a unique fingerprint.

Cite this