English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study how the spectral gap of the normalized Laplacian of a random graphchanges when an edge is added to or removed from the graph. There are knownexamples of graphs where, perhaps counterintuitively, adding an edge candecrease the spectral gap, a phenomenon that is analogous to Braess's paradoxin traffic networks. We show that this is often the case in random graphs in astrong sense. More precisely, we show that for typical instances ofErd\H{o}s-R\'enyi random graphs $G(n,p)$ with constant edge density $p \in(0,1)$, the addition of a random edge will decrease the spectral gap withpositive probability, strictly bounded away from zero. To do this, we prove anew delocalization result for eigenvectors of the Laplacian of $G(n,p)$, whichmight be of independent interest.

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